33659번 - Strange Light Switches 스페셜 저지다국어

문제

You are the best electrician around and are now working on understanding the wiring in a customer’s house. But you aren’t able tomake heads or tails of it, or even turn them all off! You really want to turn them off so you can start rewiring the place.

All lights in the customer’s house are arranged in a circle. After working on it for a while, you notice a pattern; whenever you flip a switch, the light may or may not change its on/off status - it depends on it’s direct neighbours. That is, whenever the two neighbours of a light are in different on/off states, the switched light turns on (or reamins on if it was already on), and when the two neighbours are both on or both off, the switched light turns off (or remains off if it was already off). You recall is exactly the exclusive or (XOR) function.

Looking for a programmatic solution, you first represent the light switches as a binary string $a$ of length $N$ where each digit corresponds to a light. A 1 at index $i$ means light $i$ is initially on and a 0 at index $i$ means light $i$ is initially off. Now, you can characterize the switching behavior with performing the following operation on the string. For any index 0ドル≤i<N,ドル when you flip switch $i$ the following update occurs:

$$a[i]=a[i-1] \text{ XOR } a[i+1]$$

Here, the indexing is “wrap-around”, i.e. for $i=0$ we have that $a[i-1]$ really means $a[N-1]$ and for $i=N-1$ we have that $a[i+1]$ really means $a[0]$.

Your task is to write a program to determine if you can zero the string or not, and report the steps of a solution it is possible.

입력

The first line of input contains the integer $N$ (3ドル≤N≤10^3$), the number of lights in the house. The following line consists of a string of $N$ binary digits the initial on/off state of all the lights. A 1 denotes the light being on, and a 0 denotes the light being off. At least one light will initially be on.

출력

If it is possible to turn off all lights, you should output two lines. The first contains a single integer $M$ (at most 3ドル\cdot N$) indicating the number of steps in your solution. The second contains the space-separated indices $b_1,b_2,\dots ,b_M$ of the sequence of switches you flip. It must be that 0ドル≤b_i≤N-1$ for each index $b_i$ you output. This means you first flip $b_1,ドル then $b_2,ドル then $b_3,ドル etc to turn off all lights. You are guaranteed that if there is a solution, there is one that uses at most 3ドル\cdot N$ steps. If there are multiple solutions, you may output any.

If it is not possible to turn off all lights, you should output just a single line containing the integer $-1$.

제한

힌트