No.2521 Don't be Same
タグ : / 解いたユーザー数 48
作問者 :
MasKoaTS
fky_
Problem Statement
This is an interactive problem.
There are $2$ plates: plate $1$ and plate $2$. Initially, plate $1$ holds $X$ stones and plate $2$ holds $Y$ stones.
The first player and the second player play a game against each other. Starting with the first player, they alternately perform exactly one of the following actions.
- Operation A: Choose $1$ plate that holds $1$ or more stones. Remove any number of stones, at least $1$, from that plate.
- Operation B: Remove all stones from both plates. This operation can be performed only if both plates hold $1$ or more stones and the numbers of stones on the two plates are equal.
The player who first becomes unable to perform an operation loses.
You and the judge play this game.
The judge uses the following strategy: if the judge can win from the current turn when both players operate appropriately, the judge performs an optimal operation in order to win (if there are multiple optimal operations, it chooses one of them uniformly at random and performs it). Otherwise, it chooses one of the possible operations uniformly at random and performs it.
You may choose whether to play as the first player or the second player. Actually play this game with the judge and win.
Constraints
- All inputs are integers.
- $1 \leq X, Y \leq 10^9$
Input and Output
All input and output is done through standard input and output.
First, $X, Y$ are given in the following format.
$X$ $Y$
You first choose either the first player or the second player. Print First to choose the first player, or Second to choose the second player.
An action is represented in the following format.
A $i$ $x$
- Operation A: Remove $x$ stones from plate $i$. It must satisfy $1 \leq i \leq 2$ and $1 \leq x$, and plate $i$ must hold $x$ or more stones.
B
- Perform operation B. In this case, both plates must hold $1$ or more stones, and the numbers of stones on the two plates must be equal.
When you perform an operation, print it following this format. When the judge performs an operation, it is given as input in the same format.
Also, on the judge's turn, if
C
is output, it means that you have won the game. Terminate your program immediately.
D
If this is output, it means that you have lost the game or that you made an invalid output. In this case as well, terminate your program immediately.
If it is determined that the judge will win under appropriate operations, D may be output even in the middle of the game.
Notes
The output is undefined if invalid input is made.
Flush standard input each time you make an input. Otherwise, you may get TLE.
Sample
| Input | Output | Explanation |
|---|---|---|
1 2 |
$X, Y$ are given. Here $X = 1, Y = 2$. | |
Second |
In this case, the second player has a winning strategy. You choose the second player. | |
A 2 1 |
The judge, as the first player, performs operation A and removes $1$ stone from plate $2$. The plates now hold $(1, 1)$ stones. | |
B |
You, as the second player, perform operation B and remove all stones. | |
C |
The judge, as the first player, cannot perform an operation, so you win. When the judge outputs C or D, your program must terminate immediately. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。