問題一覧 > 通常問題

No.1149 Coloring Game

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 （詳しくはこちら）
タグ : （AC するまで非表示） / 解いたユーザー数 209
作問者 : Kiri8128 / テスター : neterukun
お気に入りにしたユーザー ProblemId : 4650 / 自分の提出
問題文最終更新日: 2020-08-08 16:02:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 260 (Typical Game Contest) (順位表) の他の問題:

Problem Statement

This is an interactive problem.

Let's play the coloring game! The coloring game is a game in which $N$ cells arranged in a row are colored in turn. The cells are numbered from $1$ to $N$.
The flow and rules of the game are as follows.

  • Initially, no cell is colored.
  • Starting with you, the players alternately color cells.
  • In one turn, a player chooses one cell or two adjacent cells and colors them. However, cells that are already colored cannot be chosen. For $1\le i\le N-1$, cell $i$ and cell $i+1$ are adjacent. No other pairs are adjacent.
  • The player who has no cells to color on their turn loses, and the opponent wins.
Defeat your opponent, Kiri-kun!

Input and Output

First, an integer $N$ is given on one line. 
$N$

It is guaranteed that $N$ is an integer satisfying $1\le N \le 100$.


On your turn, print the number of cells to color $k$ and the smallest number $x$ among them, separated by a space.
$k\ x$
$k$ and $x$ must be integers satisfying the following.
  • $k=1$ or $k=2$
  • $1\le x \le N+1-k$

On Kiri-kun's turn, you are first given $t$, which represents the state.
$t$
$t$ is an integer between 0 and 3, inclusive. The meaning of each value is as follows.
  • $t=0$ indicates that Kiri-kun has no cells left to color and you have won.
  • $t=1$ indicates that your previous input was invalid. Specifically, it does not satisfy the constraints, or it attempts to color a cell that is already colored.
  • $t=2$ indicates that you will lose by Kiri-kun's upcoming move.
  • $t=3$ indicates that the game will continue after Kiri-kun's upcoming turn.
When $t=0$ or $t=1$, no further input is given. Terminate your program immediately.

When $t=2$ or $t=3$, the number of cells $k$ that Kiri-kun colors and the smallest number $x$ among them are then given, separated by a space. 
$k\ x$
This is guaranteed to be a valid move.
When $t=2$, terminate your program immediately after receiving this.
When $t=3$, it becomes your turn again.

(Supplement)
You get AC only if you receive $t=0$ and terminate your program correctly.
An AC solution never receives $t=1$ or $t=2$. Therefore, you can get AC even if you assume that only $t=0$ or $t=3$ is received. If you want to receive the correct judge verdict even when the result is not AC, you need to handle the cases $t=1$ and $t=2$ as well.


It can be shown that, under the constraints of this problem, a winning strategy always exists.

Notes

  • Flush standard output after each output.
  • Note that when the game ends, your program must terminate at that point.
  • If the above is not followed, the judge verdict is undefined (it may be TLE or RE).

Sample

The following is an example for explanation. It is not guaranteed that the actual test cases include a case that behaves the same way as this.

The "Input" and "Output" sections are arranged in chronological order. For $i=1,\ 2,\ \cdots$ in this order, line $i$ of either the Input section or the Output section (whichever is not empty) is executed. (For each $i$, line $i$ is an empty line in one of the "Input" and "Output" sections. The empty lines are only for aligning line numbers; no empty line is actually given as input or required as output.)

Sample 1
Input
7

3
2 3

3
1 7

0
Output

2 5


1 1


1 2

First, $N=7$ is given (line 1 of "Input"). The state of the cells is □□□□□□□ (the $i$-th character from the left is ■ if cell $i$ is colored, and □ if it is not).
You printed "2 5" (line 2 of "Output"). This means coloring 2 cells starting from cell 5 (that is, cell 5 and cell 6). The state of the cells becomes □□□□■■□.
Next, you receive "3" and "2 3" (lines 3 and 4 of "Input"). This indicates that Kiri-kun colored cell 3 and cell 4, and that the game continues. The state of the cells is □□■■■■□.
Next, you printed "1 1" (line 5 of "Output"). This means coloring cell 1. The state of the cells is ■□■■■■□.
Next, you receive "3" and "1 7" (lines 6 and 7 of "Input"). This indicates that Kiri-kun colored cell 7, and that the game continues. The state of the cells is ■□■■■■■.
Next, you printed "1 2" (line 8 of "Output"). This means coloring cell 2. The state of the cells is ■■■■■■■.
Next, you receive "0" (line 9 of "Input"). This indicates that Kiri-kun has no cells to color and you have won the game.
Terminate your program at this point.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。