codeforces-scrape

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

1381A1.md (2140B)


      1 Source: https://codeforces.com/problemset/problem/1381/A1
      2 
      3 A1. Prefix Flip (Easy Version)
      4 
      5 time limit per test
      6 
      7 1 second
      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 This is the easy version of the problem. The difference between the versions is the constraint on $n$ and the required number of operations. You can make hacks only if all versions of the problem are solved.
     22 
     23 There are two binary strings $a$ and $b$ of length $n$ (a binary string is a string consisting of symbols $0$ and $1$). In an operation, you select a prefix of $a$, and simultaneously invert the bits in the prefix ($0$ changes to $1$ and $1$ changes to $0$) and reverse the order of the bits in the prefix.
     24 
     25 For example, if $a=001011$ and you select the prefix of length $3$, it becomes $011011$. Then if you select the entire string, it becomes $001001$.
     26 
     27 Your task is to transform the string $a$ into $b$ in at most $3n$ operations. It can be proved that it is always possible.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1\le t\le 1000$)  — the number of test cases. Next $3t$ lines contain descriptions of test cases.
     32 
     33 The first line of each test case contains a single integer $n$ ($1\le n\le 1000$)  — the length of the binary strings.
     34 
     35 The next two lines contain two binary strings $a$ and $b$ of length $n$.
     36 
     37 It is guaranteed that the sum of $n$ across all test cases does not exceed $1000$.
     38 
     39 Output
     40 
     41 For each test case, output an integer $k$ ($0\le k\le 3n$), followed by $k$ integers $p_1,\ldots,p_k$ ($1\le p_i\le n$). Here $k$ is the number of operations you use and $p_i$ is the length of the prefix you flip in the $i$-th operation.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 2
     50 01
     51 10
     52 5
     53 01011
     54 11100
     55 2
     56 01
     57 01
     58 10
     59 0110011011
     60 1000110100
     61 1
     62 0
     63 1
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 3 1 2 1
     70 6 5 2 5 3 1 2
     71 0
     72 9 4 1 2 10 4 1 2 1 5
     73 1 1
     74 ```
     75 
     76 Note
     77 
     78 In the first test case, we have $01\to 11\to 00\to 10$.
     79 
     80 In the second test case, we have $01011\to 00101\to 11101\to 01000\to 10100\to 00100\to 11100$.
     81 
     82 In the third test case, the strings are already the same. Another solution is to flip the prefix of length $2$, which will leave $a$ unchanged.