30604번 - Intersegment Activation 다국어인터랙티브

문제

This is an interactive problem.

There is an array of $n$ cells, numbered from 1ドル$ to $n$. For each pair of integers $(i, j),ドル where 1ドル \le i \le j \le n,ドル there is a barrier covering all cells from $i$ to $j,ドル inclusive. Each barrier is either active or inactive. A cell is visible if there are no active barriers that cover it. Otherwise, the cell is invisible.

The state of each barrier is unknown to you. All you can observe is the number of visible cells. But you can flip the state of any barrier: if it's active, it turns inactive, and the other way around. Your task is to make all barriers inactive, so that all cells become visible.

인터랙션 프로토콜

First, read an integer $n,ドル denoting the number of cells (1ドル \le n \le 10$).

The following interaction will proceed in rounds. Your program should start each round by reading an integer $k,ドル denoting the number of currently visible cells (0ドル \le k \le n$).

• If $k = n,ドル then the task is done and your program must exit.
• If $k < n,ドル you can flip the state of any barrier. On a separate line, print two integers $i$ and $j$ to flip the state of the $(i, j)$ barrier (1ドル \le i \le j \le n$). After your query, the next round begins, and your program should read a new value of $k$.

Your solution must make all cells visible using at most 2500ドル$ flips. In the beginning, not all cells are visible ($k < n$ in the first round).

The interactor is not adaptive: in every test, the state of all barriers is chosen before the program execution.

입력

출력

제한

노트

In the example, initially, only two barriers, $(1, 2)$ and $(2, 3),ドル are active. These two barriers cover all three cells, so $k$ is equal to 0 in the first round.

• After flipping the $(2, 2)$ barrier, there are now three active barriers, and still $k = 0$ visible cells.
• After flipping the $(1, 2)$ barrier, cell 1ドル$ becomes visible, so now there is $k = 1$ visible cell.
• After flipping the $(2, 3)$ barrier, cell 3ドル$ also becomes visible. The only invisible cell now is 2ドル,ドル covered by the only active barrier, $(2, 2),ドル and there are $k = 2$ visible cells.
• After flipping the $(2, 2)$ barrier, all barriers are now inactive, and all cells are visible. After reading $k = 3,ドル the program terminates.