atcoder#ABC278G. [ABC278G] Generalized Subtraction Game

[ABC278G] Generalized Subtraction Game

Score : 600600 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 NN, LL, and RR. You play the following game against the judge:

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

  • choose an integer pair (x,y)(x, y) satisfying 1xN1 \leq x \leq N, LyRL \leq y \leq R such that all of the yy cards x,x+1,,x+y1x, x+1, \dots, x+y-1 remain on the table, and remove cards x,x+1,,x+y1x, 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

  • 1N20001 \leq N \leq 2000
  • 1LRN1 \leq L \leq R \leq N
  • NN, LL, and RR 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 NN, LL, and RR, 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)(x, y) that you choose in the operation in the following format. If there is no (x,y)(x, y) that you can choose, print (x,y)=(0,0)(x, y) = (0, 0) instead.

x y

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

a b

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

  • If (a,b)=(0,0)(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)(a, b) = (-1, -1): you have chosen an illegal (x,y)(x, y) or printed (0,0)(0, 0). In other words, you have lost the game.
  • Otherwise: the judge has performed the operation with (x,y)=(a,b)(x,y) = (a,b). It is guaranteed that judge chooses valid (x,y)(x, y).

If the judge returns (a,b)=(0,0)(a,b)=(0,0) or (a,b)=(1,1)(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 WA or TLE verdict instead of a RE 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=1N = 6, L = 1, and R=2R = 2.

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