1733D1.md (2220B)
1 Source: https://codeforces.com/problemset/problem/1733/D1 2 3 D1. Zero-One (Easy Version) 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is the easy version of the problem. In this version, $n \le 3000$, $x \ge y$ holds. You can make hacks only if both versions of the problem are solved. 22 23 You are given two binary strings $a$ and $b$, both of length $n$. You can do the following operation any number of times (possibly zero). 24 25 * Select two indices $l$ and $r$ ($l \lt r$). 26 * Change $a_l$ to $(1 - a_l)$, and $a_r$ to $(1 - a_r)$. 27 * If $l + 1 = r$, the cost of the operation is $x$. Otherwise, the cost is $y$. 28 29 You have to find the minimum cost needed to make $a$ equal to $b$ or say there is no way to do so. 30 31 Input 32 33 The first line contains one integer $t$ ($1 \le t \le 600$) — the number of test cases. 34 35 Each test case consists of three lines. The first line of each test case contains three integers $n$, $x$, and $y$ ($5 \le n \le 3000$, $1 \le y \le x \le 10^9$) — the length of the strings, and the costs per operation. 36 37 The second line of each test case contains the string $a$ of length $n$. The string only consists of digits $0$ and $1$. 38 39 The third line of each test case contains the string $b$ of length $n$. The string only consists of digits $0$ and $1$. 40 41 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3000$. 42 43 Output 44 45 For each test case, if there is no way to make $a$ equal to $b$, print $-1$. Otherwise, print the minimum cost needed to make $a$ equal to $b$. 46 47 Example 48 49 Input 50 51 ``` 52 4 53 54 5 8 7 55 56 01001 57 58 00101 59 60 5 7 2 61 62 01000 63 64 11011 65 66 7 8 3 67 68 0111001 69 70 0100001 71 72 5 10 1 73 74 01100 75 76 01100 77 ``` 78 79 Output 80 81 ``` 82 8 83 -1 84 6 85 0 86 ``` 87 88 Note 89 90 In the first test case, selecting indices $2$ and $3$ costs $8$, which is the minimum possible cost. 91 92 In the second test case, we cannot make $a$ equal to $b$ using any number of operations. 93 94 In the third test case, we can perform the following operations: 95 96 * Select indices $3$ and $6$. It costs $3$, and $a$ is 0101011 now. 97 * Select indices $4$ and $6$. It costs $3$, and $a$ is 0100001 now. 98 99 The total cost is $6$. 100 101 In the fourth test case, we don't have to perform any operations.