これは通信問題です。
二つのプログラム Alice と Bob が以下の協力ゲームを行います。
$0 \le A, B < 2^{64}$ を満たす整数 $A$ と $B$ が与えられます。最初、Alice だけが $A$ を知っており、Bob だけが $B$ を知っています。$C := \min(A, B)$ とします。目標は、Alice と Bob の両方が $C$ を出力できるようにすることです。
情報を交換するために、Alice と Bob は以下の関数を呼び出すことができます:
send(x):もう一方のプログラムに 1 ビットの値 $x$ を送信する。この呼び出しは、もう一方のプログラムがreceive()を呼び出すまで戻らない。receive():もう一方のプログラムから 1 ビットの値を受信し、それを返す。この呼び出しは、もう一方のプログラムがsend()を呼び出すまで戻らない。
Alice と Bob による send() の呼び出し回数の合計は $76$ を超えてはなりません。receive() についても同様です。
通信が終了した後、各プログラムは以下の関数をちょうど一度だけ呼び出さなければなりません:
answer(x):$C$ の値が $x$ であると宣言する。この関数を呼び出した直後に、プログラムは終了しなければならない。
Alice と Bob の両方が $C$ を正しく答えた場合、ゲームは成功となります。
常にゲームに成功する二つのプログラム Alice と Bob を作成してください。
入出力の方法
これはインタラクティブな通信問題です(あなたのプログラムとジャッジは標準入出力を介して通信します)。Alice として動作するあなたのプログラムと Bob として動作するあなたのプログラムが、ジャッジを介してゲームを行います。
プログラムの開始
あなたのプログラムは最初に以下の形式で入力を受け取ります:
Player X
ここで、Player は文字列 Alice または Bob であり、$X$ は $0 \le X < 2^{64}$ を満たす整数です。
PlayerがAliceの場合、$A = X$ です。これ以降、あなたのプログラムは Alice として振る舞わなければなりません。PlayerがBobの場合、$B = X$ です。これ以降、あなたのプログラムは Bob として振る舞わなければなりません。
その後、以下に説明するように send、receive、そして最後に answer を呼び出してください。
send
send(x) を呼び出すには、次のように出力してください:
send x
ここで、$x$ は $0$ または $1$ でなければなりません。
この呼び出しは、もう一方のプログラムが receive() を呼び出すまで戻りません。以下のいずれかが発生した場合、Wrong Answer と判定されます:
- 待機中にもう一方のプログラムが終了した場合、
- 待機中にもう一方のプログラムも
send()を呼び出した場合、 - Alice と Bob による
send()の呼び出し回数の合計が $76$ を超えた場合。
receive
receive() を呼び出すには、次のように出力してください:
receive
その後、受信したビット $x$ を標準入力から読み取ってください:
x
この呼び出しは、もう一方のプログラムが send() を呼び出すまで戻りません。以下のいずれかが発生した場合、Wrong Answer と判定されます:
- 待機中にもう一方のプログラムが終了した場合、
- 待機中にもう一方のプログラムも
receive()を呼び出した場合、 - Alice と Bob による
receive()の呼び出し回数の合計が $76$ を超えた場合。
やり取りの途中で Wrong Answer と判定された場合、与えられる入力は $-1$ になります。$-1$ を読み取った場合は直ちにプログラムを終了してください。そうしない場合、Time Limit Exceeded となる可能性があります。
answer
answer(x) を呼び出すには、次のように出力してください:
answer x
ここで、$x$ は $\min(A, B)$ と等しくなければなりません。この関数を呼び出した後、直ちにプログラムを終了してください。
ノート
- 各出力の後、プログラムは標準出力をフラッシュしなければなりません。そうしない場合、Time Limit Exceeded となる可能性があります。
- ジャッジプログラム、Alice として動作するあなたのプログラム、および Bob として動作するあなたのプログラムは同時に実行されます。実行時間制限とメモリ制限はこれらすべての合計として計測されるため、時間とメモリの両方に十分な余裕を持たせてください。
- ジャッジプログラムは最大で約 $50$ ms および $5$ MiB を消費します。
- $0$ から $2^{64} - 1$ の範囲の整数を扱います。オーバーフローに注意してください。
入出力例
入力例 1
Alice 31 1
出力例 1
send 0 receive send 1 answer 25
入力例 2
Bob 25 0 1
出力例 2
receive send 1 receive answer 25