310795: CF1889A. Qingshan Loves Strings 2
Description
Qingshan has a string $s$ which only contains $\texttt{0}$ and $\texttt{1}$.
A string $a$ of length $k$ is good if and only if
- $a_i \ne a_{k-i+1}$ for all $i=1,2,\ldots,k$.
For Div. 2 contestants, note that this condition is different from the condition in problem B.
For example, $\texttt{10}$, $\texttt{1010}$, $\texttt{111000}$ are good, while $\texttt{11}$, $\texttt{101}$, $\texttt{001}$, $\texttt{001100}$ are not good.
Qingshan wants to make $s$ good. To do this, she can do the following operation at most $300$ times (possibly, zero):
- insert $\texttt{01}$ to any position of $s$ (getting a new $s$).
Please tell Qingshan if it is possible to make $s$ good. If it is possible, print a sequence of operations that makes $s$ good.
InputThe 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.
The first line of each test case contains a single integer $n$ ($1 \le n\le 100$) — the length of string $s$, respectively.
The second line of each test case contains a string $s$ with length $n$.
It is guaranteed that $s$ only consists of $\texttt{0}$ and $\texttt{1}$.
OutputFor each test case, if it impossible to make $s$ good, output $-1$.
Otherwise, output $p$ ($0 \le p \le 300$) — the number of operations, in the first line.
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$.
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.
ExampleInput6 2 01 3 000 4 1111 6 001110 10 0111001100 3 001Output
0 -1 -1 2 6 7 1 10 -1Note
In the first test case, you can do zero operations and get $s=\texttt{01}$, which is good.
Another valid solution is to do one operation: (the inserted $\texttt{01}$ is underlined)
- $\texttt{0}\underline{\texttt{01}}\texttt{1}$
and get $s = \texttt{0011}$, which is good.
In the second and the third test case, it is impossible to make $s$ good.
In the fourth test case, you can do two operations:
- $\texttt{001110}\underline{\texttt{01}}$
- $\texttt{0011100}\underline{\texttt{01}}\texttt{1}$
and get $s = \texttt{0011100011}$, which is good.
Output
题目名为“晴山喜爱字符串2”。给定一个只包含字符 '0' 和 '1' 的字符串 `s`。定义一个长度为 `k` 的字符串 `a` 为好的字符串,当且仅当对于所有 `i=1,2,…,k`,满足 `a_i ≠ a_{k-i+1}`。例如,'10'、'1010' 和 '111000' 是好的字符串,而 '11'、'101'、'001' 和 '001100' 不是好的字符串。
晴山想要使 `s` 变为好的字符串。她可以进行以下操作,最多300次(也可能零次):
- 在 `s` 的任意位置插入 '01'(得到新的 `s`)。
需要判断是否可能使 `s` 变为好的字符串。如果可能,输出一系列操作使 `s` 变为好的字符串。
**输入数据格式:**
输入包含多个测试用例。第一行包含一个整数 `t`(`1≤t≤100`)——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 `n`(`1≤n≤100`)——字符串 `s` 的长度。第二行包含一个长度为 `n` 的字符串 `s`。保证 `s` 只包含 '0' 和 '1'。
**输出数据格式:**
对于每个测试用例,如果不可能使 `s` 变为好的字符串,输出 `-1`。
否则,首先在第一行输出 `p`(`0≤p≤300`)——操作的数量。然后在第二行输出 `p` 个整数,第 `i` 个整数是一个索引 `x_i`(`0≤x_i≤n+2i-2`)——在当前的 `s` 中插入 '01' 的位置。如果 `x_i=0`,则在 `s` 的开头插入 '01'。否则,在 `s` 的第 `x_i` 个字符后立即插入 '01'。
根据题目中的约束,如果存在答案,则总有一个答案需要最多300次操作。**题目大意:** 题目名为“晴山喜爱字符串2”。给定一个只包含字符 '0' 和 '1' 的字符串 `s`。定义一个长度为 `k` 的字符串 `a` 为好的字符串,当且仅当对于所有 `i=1,2,…,k`,满足 `a_i ≠ a_{k-i+1}`。例如,'10'、'1010' 和 '111000' 是好的字符串,而 '11'、'101'、'001' 和 '001100' 不是好的字符串。 晴山想要使 `s` 变为好的字符串。她可以进行以下操作,最多300次(也可能零次): - 在 `s` 的任意位置插入 '01'(得到新的 `s`)。 需要判断是否可能使 `s` 变为好的字符串。如果可能,输出一系列操作使 `s` 变为好的字符串。 **输入数据格式:** 输入包含多个测试用例。第一行包含一个整数 `t`(`1≤t≤100`)——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 `n`(`1≤n≤100`)——字符串 `s` 的长度。第二行包含一个长度为 `n` 的字符串 `s`。保证 `s` 只包含 '0' 和 '1'。 **输出数据格式:** 对于每个测试用例,如果不可能使 `s` 变为好的字符串,输出 `-1`。 否则,首先在第一行输出 `p`(`0≤p≤300`)——操作的数量。然后在第二行输出 `p` 个整数,第 `i` 个整数是一个索引 `x_i`(`0≤x_i≤n+2i-2`)——在当前的 `s` 中插入 '01' 的位置。如果 `x_i=0`,则在 `s` 的开头插入 '01'。否则,在 `s` 的第 `x_i` 个字符后立即插入 '01'。 根据题目中的约束,如果存在答案,则总有一个答案需要最多300次操作。