codeforces-scrape

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

2050E.md (2279B)


      1 Source: https://codeforces.com/problemset/problem/2050/E
      2 
      3 E. Three Strings
      4 
      5 time limit per test
      6 
      7 2.5 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 three strings: $a$, $b$, and $c$, consisting of lowercase Latin letters. The string $c$ was obtained in the following way:
     22 
     23 1. At each step, either string $a$ or string $b$ was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string $c$, until one of the strings ran out. After that, the remaining characters of the non-empty string were added to the end of $c$.
     24 2. Then, a certain number of characters in string $c$ were randomly changed.
     25 
     26 For example, from the strings $a=\color{red}{\text{abra}}$ and $b=\color{blue}{\text{cada}}$, without character replacements, the strings $\color{blue}{\text{ca}}\color{red}{\text{ab}}\color{blue}{\text{d}}\color{red}{\text{ra}}\color{blue}{\text{a}}$, $\color{red}{\text{abra}}\color{blue}{\text{cada}}$, $\color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}}$ could be obtained.
     27 
     28 Find the minimum number of characters that could have been changed in string $c$.
     29 
     30 Input
     31 
     32 The first line of the input contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.
     33 
     34 The first line of each test case contains one string of lowercase Latin letters $a$ ($1 \leq |a| \leq 10^3$) — the first string, where $|a|$ denotes the length of string $a$.
     35 
     36 The second line of each test case contains one string of lowercase Latin letters $b$ ($1 \leq |b| \leq 10^3$) — the second string, where $|b|$ denotes the length of string $b$.
     37 
     38 The third line of each test case contains one string of lowercase Latin letters $c$ ($|c| = |a| + |b|$) — the third string.
     39 
     40 It is guaranteed that the sum of $|a|$ across all test cases does not exceed $2 \cdot 10^3$. Also, the sum of $|b|$ across all test cases does not exceed $2 \cdot 10^3$.
     41 
     42 Output
     43 
     44 For each test case, output a single integer — the minimum number of characters that could have been changed in string $c$.
     45 
     46 Example
     47 
     48 Input
     49 
     50 ```
     51 7
     52 
     53 a
     54 
     55 b
     56 
     57 cb
     58 
     59 ab
     60 
     61 cd
     62 
     63 acbd
     64 
     65 ab
     66 
     67 ba
     68 
     69 aabb
     70 
     71 xxx
     72 
     73 yyy
     74 
     75 xyxyxy
     76 
     77 a
     78 
     79 bcd
     80 
     81 decf
     82 
     83 codes
     84 
     85 horse
     86 
     87 codeforces
     88 
     89 egg
     90 
     91 annie
     92 
     93 egaegaeg
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 1
    100 0
    101 2
    102 0
    103 3
    104 2
    105 3
    106 ```