codeforces-scrape

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

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.