DMOPC '17 Contest 3 P2 - Towers of Hanoi - Olympiads Online Judge

DMOPC '17 Contest 3 P2 - Towers of Hanoi

Points: 7 (partial)

Time limit: 2.5s

Memory limit: 64M

Author:

Problem type

The city of Hanoi has $N$ $N$ towers, arranged in a line, numbered from $1$ $1$ to $N$ $N$ . 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 $1$ $1$ , only towers $1$ $1$ and $2$ $2$ are toggled. The situation is similar for tower $N$ $N$ : if you toggle tower $N$ $N$ , only towers $N$ $N$ and $N-1$ $N - 1$ are toggled.

You are given the task of emptying all $N$ $N$ towers. Can you accomplish this task in at most $10^6$ $10^{6}$ 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.

Constraints

Subtask 1 [20%]

$1 \le N \le 10$ $1 \leq N \leq 10$

Subtask 2 [30%]

$1 \le N \le 1000$ $1 \leq N \leq 1000$

Subtask 3 [50%]

$1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$

Input Specification

The first line of input will contain an integer $N$ $N$ .

The second line of input will contain $N$ $N$ space-separated integers. The $i^\text{th}$ $i^{th}$ integer will contain the state of tower numbered $i$ $i$ . 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 $10^6$ $10^{6}$ , 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

Copy

6
0 1 1 1 0 0

Sample Output 1

Copy

1
3

Sample Input 2

Copy

7
1 0 1 1 1 1 1

Sample Output 2

Copy

Comments

-1

b1l4l commented on Dec. 14, 2017, 9:43 p.m. ← edited →

In the problem set you said if you toggle $1$ $1$ you toggle $1$ $1$ & $2$ $2$ that means you toggle $N$ $N$ and $N+1$ $N + 1$ not $N$ $N$ and $N-1$ $N - 1$ ? or am i wrong ?

5

aeternalis1 commented on Dec. 14, 2017, 10:19 p.m.

The problem statement refers to the fact that toggling a tower also toggles those adjacent. Tower $1$ $1$ is only adjacent to tower $2$ $2$ , since there is no tower $0$ $0$ , and tower $N$ $N$ is only adjacent to tower $N-1$ $N - 1$ . This exception exists only for towers $1$ $1$ and $N$ $N$ , since all other towers have two others adjacent, one in front and one behind.