C - Yamanote Line Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

高橋君と青木君は 2 人で次の対戦ゲームをします。

高橋君が先手でゲームを始め、ゲームが終了するまでの間、 2 人は交互に 1 以上 2N+1 以下の整数を 1 つずつ宣言します。 どちらかが一度でも宣言した整数は、それ以降どちらも二度と宣言することが出来ません。 先に整数を宣言することが出来なくなった方のプレイヤーの負けとなり、負けなかった方のプレイヤーの勝ちとなります。

このゲームでは必ず高橋君が勝ちます。 高橋君の立場で実際にゲームを行い、ゲームに勝ってください。

制約

  • 1 \leq N \leq 1000
  • N は整数

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。
あなたのプログラムが高橋君の立場で、ジャッジプログラムが青木君の立場でゲームを行います。

まず、あなたのプログラムに標準入力から正の整数 N が与えられます。 その後、ゲームが終了するまで下記の手順を繰り返します。

  1. あなたのプログラムが、高橋君が宣言する整数として、1 以上 2N+1 以下の整数を標準出力に出力します。（どちらかのプレイヤーによってすでに宣言されている整数を出力することは出来ません。）
  2. ジャッジプログラムによって、青木君が宣言する整数があなたのプログラムに標準入力から与えられます。（どちらかのプレイヤーによってすでに宣言されている整数が入力されることはありません。） ただし、青木君が宣言できる整数が残っていない場合は、代わりに 0 が与えられ高橋君の勝ちでゲームが終了します。

注意点

  • 出力を行うたびに標準出力をflushしてください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 高橋君の勝ちでゲームが終了したあと、あなたのプログラムは直ちに終了しなければなりません。そうしなかった場合、ジャッジ結果が AC とならない可能性があります。
  • ゲームの途中で不正な出力を行った場合（例えば、すでにどちらかのプレイヤーによって宣言されている整数を出力した場合）は不正解となりますが、そのときのジャッジ結果は不定です。WA になるとは限りません。

入出力例

入力 出力 説明
2 まず整数 N が与えられます。
1 高橋君が 1 を宣言します。
3 青木君が 3 を宣言します。
2 高橋君が 2 を宣言します。
4 青木君が 4 を宣言します。
5 高橋君が 5 を宣言します。
0 青木君が宣言できる整数が残っていないため、高橋君の勝ちでゲームが終了します。

Score : 300 points

Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

  • 1 \leq N \leq 1000
  • N is an integer.

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

  1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
  2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

  • After each output, you must flush Standard Output. Otherwise, you may get TLE.
  • After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
  • If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Input Output Description
2 First, an integer N is given.
1 Takahashi declares an integer 1.
3 Aoki declares an integer 3.
2 Takahashi declares an integer 2.
4 Aoki declares an integer 4.
5 Takahashi declares an integer 5.
0 Aoki has no more integer to declare, so Takahashi wins, and the game ends.