問題一覧 > 通常問題

No.2521 Don't be Same

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / リアクティブ問題 (詳しくはこちら
タグ : / 解いたユーザー数 47
作問者 : ShirotsumeShirotsume / テスター : MasKoaTSMasKoaTS fky_fky_
2 ProblemId : 10166 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-10-27 18:13:11

問題文

これはインタラクティブな問題です。

皿 $1$ 、皿 $2$ の $2$ つの皿があります。はじめ、皿 $1$ には $X$ 個の石が、皿 $2$ には $Y$ 個の石が置かれています。

先手と後手が対戦ゲームをします。先手から先に次のうちいずれかひとつの行動を交互に行います。

  • 操作A: 石が $1$ 個以上置いてある皿を $1$ つ選ぶ。その皿から $1$ 個以上の任意の個数石を取り除く。
  • 操作B: 両方の皿からすべての石を取り除く。この操作は、両方の皿に石が $1$ 個以上置かれていて、かつ両方の皿の石の個数が等しい場合にのみ行える。

先に操作が行えなくなったほうの負けです。

あなたとジャッジがこのゲームをプレイします。

ジャッジは次のような戦法をとります:現在の手番からお互いが適切に操作した結果ジャッジが勝利できるなら、ジャッジは勝利するために最適な操作を行う(最適な操作が複数存在するなら、最適な操作からランダムに等確率でひとつ選択し、行う)。そうでないなら、可能な操作からランダムな操作を等確率にひとつ選択して行う。

先手と後手のどちらでプレイするかをあなたが選ぶことができます。ジャッジとこのゲームを実際に行い、勝利してください。

制約

  • 入力はすべて整数
  • $1 \leq X, Y \leq 10^9$

入出力

入出力はすべて標準入出力から行われる。

初めに、次の形式で $X, Y$ が与えられる。

$X$ $Y$

あなたは、先手または後手のどちらかを最初に選ぶことができます。先手を選ぶなら First、後手を選ぶなら Second と出力してください。

行動は次の形式で表されます。

A $i$ $x$
  • 操作A: 皿 $i$ から $x$ 個の石を取り除く。$1 \leq i \leq 2$ かつ $1 \leq x$ を満たし、かつ皿 $i$ に $x$ 個以上の石が存在する必要がある。
B
  • 操作 B を行う。このとき、両方の皿に石が $1$ 個以上置かれていて、かつ両方の皿の石の個数が等しくなければならない。

あなたが操作を行うとき、この形式に従って出力を行ってください。ジャッジが操作を行うときは、同様の形式で入力を行います。

また、ジャッジの手番において、

C

と出力されたとき、これはあなたがゲームに勝利したことを表します。プログラムを直ちに終了してください。

D

と出力されたとき、あなたがゲームに敗北したか、不正な出力をしたことを表します。この場合も、プログラムを直ちに終了してください。

ジャッジが適切な操作の下勝利することが確定した場合、ゲームの途中でも D を出力する場合があります。

注意

不正な入力が行われた場合の出力は不定です。

入力を行うたびに標準入力をflushしてください。そうしない場合、TLEとなることがあります。

サンプル

入力出力説明
1 2 $X, Y$ が与えられる。$X = 1, Y = 2$ である。
Second この場合、後手必勝である。あなたは後手を選択する。
A 2 1 先手であるジャッジが操作 A を行い、皿 $2$ から $1$ 個の石を取り除いた。現在、皿の石の個数は $(1, 1)$ である。
B 後手であるあなたは操作 B を行い、すべての石を取り除いた。
C 先手のジャッジは操作を行えないため、あなたの勝利である。ジャッジがCDを出力したとき、あなたのプログラムは直ちに終了しなければならない。

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