G - Generalized Subtraction Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

整数 N, L, R が与えられます。
あなたはジャッジシステムと次のゲームで対戦します。

1 から N までの番号がついた N 枚のカードが場に置かれています。
先攻から交互に以下の操作を繰り返します。

  • 1 \leq x \leq N, L \leq y \leq R かつカード x, x+1, \dots, x+y-1 の y 枚がすべて場に存在するような整数の組 (x, y) を 1 つ選び、カード x, x+1, \dots, x+y-1 を場から取り除く。

先に操作が行えなくなった方が負けで、そうでない方が勝ちです。

あなたは先攻か後攻の一方を選んでください。そして、選んだ方の手番でジャッジシステムとゲームをして勝利してください。

制約

  • 1 \leq N \leq 2000
  • 1 \leq L \leq R \leq N
  • N, L, R は整数

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが標準入出力を介して対話を行う形式の問題）です。

最初に、N, L, R が以下の形式で入力から与えられるので、これを受け取ってください。

N L R

まず、あなたは一方の手番を選びます。そして、選んだ手番が先攻ならば First を、後攻ならば Second を出力してください。

その後、あなたは出力した方の手番で、ジャッジシステムがそうでない方の手番でゲームが直ちに開始されます。あなたはゲームが終了するまで入出力を利用してジャッジシステムと対話をして、ゲームに勝利してください。

あなたは手番が回ってきたら、操作で選ぶ整数の組 (x, y) を次の形式で出力してください。ただし、選ぶことのできる (x, y) が存在しない場合は (x, y) = (0, 0) を出力してください。

x y

ジャッジシステムの手番では、ジャッジシステムが以下の形式で整数の組 (a, b) を出力します。

a b

ここで a, b は次の 3 種類のいずれかであることが保証されます。

  • (a, b) = (0, 0) の場合：ジャッジシステムは操作を行えなくなったことを意味します。つまり、あなたはゲームに勝利しました。
  • (a, b) = (-1, -1) の場合：あなたは 1 つ前に非合法な (x, y) を選んだか、あるいは (0, 0) を出力したことを意味します。つまり、あなたはゲームに敗北しました。
  • それ以外の場合：ジャッジシステムは (x,y) = (a,b) として操作を行ったことを意味します。ここでジャッジシステムが選んだ (x, y) は合法であることが保証されます。

ジャッジが (a,b)=(0,0) または (a,b)=(-1,-1) を返した場合、ゲームはすでに終了しています。この場合、プログラムをただちに終了してください。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った、あるいはプログラムが途中で終了した場合のジャッジ結果は不定です。 特に、プログラムの実行中に実行時エラーが起こった場合に、ジャッジ結果が ではなく や TLE になる可能性があることに注意してください。
  • ゲームが終了したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。

入出力例

以下は、N = 6, L = 1, R = 2 の場合の入出力例です。

入力 出力 説明
6 1 2 まず整数 N, L, R が与えられます。
First 先攻を選び、ゲームを開始します。
2 1 (x, y) = (2, 1) を選び、カード 2 を取り除きます。
3 2 (x, y) = (3, 2) を選び、カード 3, 4 を取り除きます。
6 1 (x, y) = (6, 1) を選び、カード 6 を取り除きます。
5 1 (x, y) = (5, 1) を選び、カード 5 を取り除きます。
1 1 (x, y) = (1, 1) を選び、カード 1 を取り除きます。
0 0 ジャッジシステムは操作を行うことができなくなったので、あなたの勝ちです。

Score : 600 points

Problem Statement

This is an interactive task (where your program interacts with the judge's program via Standard Input and Output).

You are given integers N, L, and R.
You play the following game against the judge:

There are N cards numbered 1 through N on the table.
The players alternately perform the following operation:

  • choose an integer pair (x, y) satisfying 1 \leq x \leq N, L \leq y \leq R such that all of the y cards x, x+1, \dots, x+y-1 remain on the table, and remove cards x, x+1, \dots, x+y-1 from the table.

The first player to become unable to perform the operation loses, and the other player wins.

Choose whether to go first or second, and play the game against the judge to win.

Constraints

  • 1 \leq N \leq 2000
  • 1 \leq L \leq R \leq N
  • N, L, and R are integers.

Input and Output

This is an interactive task (where your program interacts with the judge's program via Standard Input and Output).

Initially, receive N, L, and R, given from the input in the following format:

N L R

First, you choose whether to go first or second. Print First if you choose to go first, and Second if you choose to go second.

Then, the game immediately starts. If you choose to go first, the judge goes second, and vice versa. You are to interact with the judge via input and output until the game ends to win the game.

In your turn, print an integer pair (x, y) that you choose in the operation in the following format. If there is no (x, y) that you can choose, print (x, y) = (0, 0) instead.

x y

In the judge's turn, the judge print an integer pair (a, b) in the following format:

a b

Here, it is guaranteed that (a, b) is of one of the following three kinds.

  • If (a, b) = (0, 0): the judge is unable to perform the operation. In other words, you have won the game.
  • If (a, b) = (-1, -1): you have chosen an illegal (x, y) or printed (0, 0). In other words, you have lost the game.
  • Otherwise: the judge has performed the operation with (x,y) = (a,b). It is guaranteed that judge chooses valid (x, y).

If the judge returns (a,b)=(0,0) or (a,b)=(-1,-1), the game has already ended. In that case, terminate the program immediately.

Notes

  • After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
  • If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate. Especially, note that if a runtime error occurs during the execution of the program, you may get a or TLE verdict instead of a verdict.
  • Terminate the program immediately after the game ends. Otherwise, the verdict will be indeterminate.

Sample Interaction

The following is a sample interaction where N = 6, L = 1, and R = 2.

Input Output Description
6 1 2 Initially, you are given integers N, L, and R.
First You choose to go first and start the game.
2 1 (x, y) = (2, 1) is chosen to remove card 2.
3 2 (x, y) = (3, 2) is chosen to remove cards 3, 4.
6 1 (x, y) = (6, 1) is chosen to remove card 6.
5 1 (x, y) = (5, 1) is chosen to remove card 5.
1 1 (x, y) = (1, 1) is chosen to remove card 1.
0 0 The judge is unable to perform the operation, so you win.