codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1506C.md (2275B)


      1 Source: https://codeforces.com/problemset/problem/1506/C
      2 
      3 C. Double-ended Strings
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given the strings $a$ and $b$, consisting of lowercase Latin letters. You can do any number of the following operations in any order:
     22 
     23 * if $|a| \gt 0$ (the length of the string $a$ is greater than zero), delete the first character of the string $a$, that is, replace $a$ with $a_2 a_3 \ldots a_n$;
     24 * if $|a| \gt 0$, delete the last character of the string $a$, that is, replace $a$ with $a_1 a_2 \ldots a_{n-1}$;
     25 * if $|b| \gt 0$ (the length of the string $b$ is greater than zero), delete the first character of the string $b$, that is, replace $b$ with $b_2 b_3 \ldots b_n$;
     26 * if $|b| \gt 0$, delete the last character of the string $b$, that is, replace $b$ with $b_1 b_2 \ldots b_{n-1}$.
     27 
     28 Note that after each of the operations, the string $a$ or $b$ may become empty.
     29 
     30 For example, if $a=$"hello" and $b=$"icpc", then you can apply the following sequence of operations:
     31 
     32 * delete the first character of the string $a$ $\Rightarrow$ $a=$"ello" and $b=$"icpc";
     33 * delete the first character of the string $b$ $\Rightarrow$ $a=$"ello" and $b=$"cpc";
     34 * delete the first character of the string $b$ $\Rightarrow$ $a=$"ello" and $b=$"pc";
     35 * delete the last character of the string $a$ $\Rightarrow$ $a=$"ell" and $b=$"pc";
     36 * delete the last character of the string $b$ $\Rightarrow$ $a=$"ell" and $b=$"p".
     37 
     38 For the given strings $a$ and $b$, find the minimum number of operations for which you can make the strings $a$ and $b$ equal. Note that empty strings are also equal.
     39 
     40 Input
     41 
     42 The first line contains a single integer $t$ ($1 \le t \le 100$). Then $t$ test cases follow.
     43 
     44 The first line of each test case contains the string $a$ ($1 \le |a| \le 20$), consisting of lowercase Latin letters.
     45 
     46 The second line of each test case contains the string $b$ ($1 \le |b| \le 20$), consisting of lowercase Latin letters.
     47 
     48 Output
     49 
     50 For each test case, output the minimum number of operations that can make the strings $a$ and $b$ equal.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 5
     58 a
     59 a
     60 abcd
     61 bc
     62 hello
     63 codeforces
     64 hello
     65 helo
     66 dhjakjsnasjhfksafasd
     67 adjsnasjhfksvdafdser
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 0
     74 2
     75 13
     76 3
     77 20
     78 ```