AT_stpc2025_1_k Two-Way Communication

$ 2 $ つのプログラム Alice, Bob が協力して以下のゲームを行います。 > $ 0 $ 以上 $ 2^{64} $ 未満の整数 $ A, B $ があります。はじめ Alice のみが $ A $ を、Bob のみが $ B $ を知っています。 > > $ C := \min(A, B) $ とします。ゲームの目的は、Alice と Bob の両方が $ C $ の値を答えられるようにすることです。 > > そのために、Alice と Bob は以下の関数を何度でも呼び出して情報をやりとりすることができます。 > > - `send(x)` : 相手のプログラムが `receive()` を呼び出すまで待機する。その後、 $ 1 $ bit の値 $ x $ を相手に送信する。 > - `receive()` : 相手のプログラムが `send()` を呼び出すまで待機する。その後、 $ 1 $ bit の値 $ x $ を相手から受け取って返り値とする。 > > 情報のやり取りが終了した後、各プログラムは以下の関数を $ 1 $ 度呼び出して $ C $ の値を回答する必要があります。 > > - `answer(x)` : $ C $ の値が $ x $ であると回答する。この関数を呼び出した後、ただちにプログラムを終了しなければならない。 > > Alice と Bob の両方が正しく $ C $ の値を回答したらゲームは成功となります。このとき、関数 `send()` の呼び出し回数の合計が少ないほど良い評価が得られます。 できるだけ少ない回数の関数の呼び出しでゲームを成功させるような $ 2 $ つのプログラム Alice, Bob を作成してください。 ### Input & Output Format この問題は**インタラクティブ問題**（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。 Alice として振る舞うあなたのプログラムと、Bob として振る舞うあなたのプログラムが、ジャッジプログラムを介してゲームを行います。 #### プログラムの開始 あなたのプログラムは、まず以下の形式で入力を受け取ってください。 > $ \text{Player} $ $ X $ ここで、 $ \text{Player} $ は文字列 `Alice` または文字列 `Bob` であり、 $ X $ は $ 0 $ 以上 $ 2^{64} $ 未満の整数です。 - $ \text{Player} = {} $ `Alice` である場合、 $ A = X $ であることを表します。また、**あなたのプログラムはこれ以降 Alice として振る舞わなければなりません。** - $ \text{Player} = {} $ `Bob` である場合、 $ B = X $ であることを表します。また、**あなたのプログラムはこれ以降 Bob として振る舞わなければなりません。** その後、以下に示す方法で `send()`, `receive()`, `answer()` の呼び出しを行ってください。 #### send send 関数を呼び出すには、以下の形式で出力してください。 > send $ x $ ここで、 $ x $ は $ 0 $ または $ 1 $ でなければなりません。 この関数は相手のプログラムが `receive()` を呼び出すまで待機しますが、待機中に相手のプログラムが停止したり、相手も send 関数を呼び出すと WA になります。 #### receive receive 関数を呼び出すには、以下の形式で出力してください。 ``` receive ``` その後、相手のプログラムから送られた値 $ x $ を以下の形式で読み取ってください。 > $ x $ この関数は相手のプログラムが `send()` を呼び出すまで待機しますが、待機中に相手のプログラムが停止したり、相手も receive 関数を呼び出すと WA になります。 やり取りの途中で WA となった場合、与えられる入力は `-1` になります。**この場合、ただちにプログラムを終了してください。** #### answer answer 関数を呼び出すには、以下の形式で出力してください。 > answer $ x $ ここで、 $ x $ は $ \min(A, B) $ と一致していなければなりません。**この関数を呼び出した後は、ただちにプログラムを終了してください。**

N/A

N/A

### 得点 あるテストケースにおける、 $ 2 $ つのプログラムの `send()` の呼び出し回数の合計を $ Q' $ とします。この問題のすべてのテストケースにわたる $ Q' $ の最大値を $ Q $ として、 - $ Q