Universal Cup Judging System

Universal Cup

実行時間制限: 0.5 s メモリ制限: 1024 MB 満点: 100 コミュニケーション
統計

これは通信問題です。

二つのプログラム 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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.