1889A.md (2760B)
1 Source: https://codeforces.com/problemset/problem/1889/A 2 3 A. Qingshan Loves Strings 2 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 Qingshan has a string $s$ which only contains $\texttt{0}$ and $\texttt{1}$. 22 23 A string $a$ of length $k$ is good if and only if 24 25 * $a_i \ne a_{k-i+1}$ for all $i=1,2,\ldots,k$. 26 27 For Div. 2 contestants, note that this condition is different from the condition in problem B. 28 29 For example, $\texttt{10}$, $\texttt{1010}$, $\texttt{111000}$ are good, while $\texttt{11}$, $\texttt{101}$, $\texttt{001}$, $\texttt{001100}$ are not good. 30 31 Qingshan wants to make $s$ good. To do this, she can do the following operation at most $300$ times (possibly, zero): 32 33 * insert $\texttt{01}$ to any position of $s$ (getting a new $s$). 34 35 Please tell Qingshan if it is possible to make $s$ good. If it is possible, print a sequence of operations that makes $s$ good. 36 37 Input 38 39 The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The description of the test cases follows. 40 41 The first line of each test case contains a single integer $n$ ($1 \le n\le 100$) — the length of string $s$, respectively. 42 43 The second line of each test case contains a string $s$ with length $n$. 44 45 It is guaranteed that $s$ only consists of $\texttt{0}$ and $\texttt{1}$. 46 47 Output 48 49 For each test case, if it impossible to make $s$ good, output $-1$. 50 51 Otherwise, output $p$ ($0 \le p \le 300$) — the number of operations, in the first line. 52 53 Then, output $p$ integers in the second line. The $i$-th integer should be an index $x_i$ ($0 \le x_i \le n+2i-2$) — the position where you want to insert $\texttt{01}$ in the current $s$. If $x_i=0$, you insert $\texttt{01}$ at the beginning of $s$. Otherwise, you insert $\texttt{01}$ immediately after the $x_i$-th character of $s$. 54 55 We can show that under the constraints in this problem, if an answer exists, there is always an answer that requires at most $300$ operations. 56 57 Example 58 59 Input 60 61 ``` 62 6 63 64 2 65 66 01 67 68 3 69 70 000 71 72 4 73 74 1111 75 76 6 77 78 001110 79 80 10 81 82 0111001100 83 84 3 85 86 001 87 ``` 88 89 Output 90 91 ``` 92 0 93 94 -1 95 -1 96 2 97 6 7 98 1 99 10 100 -1 101 ``` 102 103 Note 104 105 In the first test case, you can do zero operations and get $s=\texttt{01}$, which is good. 106 107 Another valid solution is to do one operation: (the inserted $\texttt{01}$ is underlined) 108 109 1. $\texttt{0}\underline{\texttt{01}}\texttt{1}$ 110 111 and get $s = \texttt{0011}$, which is good. 112 113 In the second and the third test case, it is impossible to make $s$ good. 114 115 In the fourth test case, you can do two operations: 116 117 1. $\texttt{001110}\underline{\texttt{01}}$ 118 2. $\texttt{0011100}\underline{\texttt{01}}\texttt{1}$ 119 120 and get $s = \texttt{0011100011}$, which is good.