## DMOPC '17 Contest 3 P2 - Towers of Hanoi

View as PDF

Points: 7 (partial)
Time limit: 2.5s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The city of Hanoi has towers, arranged in a line, numbered from to . Each one of the towers can be in one of two states: occupied or empty.

You have the ability to toggle the state of a tower of your choice (i.e. empty an occupied tower or occupy an empty tower). But when you do so, towers that are directly adjacent also toggle their state indirectly. Note that if you toggle tower , only towers and are toggled. The situation is similar for tower : if you toggle tower , only towers and are toggled.

You are given the task of emptying all towers. Can you accomplish this task in at most steps?

It is guaranteed that this task is possible for the test cases given.

If there are multiple ways to do so, output any one of them.

#### Input Specification

The first line of input will contain an integer .

The second line of input will contain space-separated integers. The integer will contain the state of tower numbered . A 1 indicates the tower is occupied and a 0 indicates the tower is empty.

#### Output Specification

On the first line, print the total number of steps that you will take. If this number is larger than , the judge will not accept your output.

On the following lines, print the steps that you will take in order, one on each line. For each step, output the number of the tower that should be directly toggled on that step.

#### Sample Input 1

6
0 1 1 1 0 0

#### Sample Output 1

1
3

#### Sample Input 2

7
1 0 1 1 1 1 1

#### Sample Output 2

3
1
3
6