codeforces-scrape

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

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.