AT_1_stpc2025_1_k.Two-Way Communication

有两个程序 Alice 和 Bob 协作进行如下游戏。

存在两个整数 $A, B$，满足 $0 \leq A, B < 2^{64}$。最初只有 Alice 知道 $A$，只有 Bob 知道 $B$。

令 $C := \min(A, B)$。游戏的目标是让 Alice 和 Bob 都能够回答出 $C$ 的值。

为此，Alice 和 Bob 可以多次调用下列函数进行信息交流。

• send(x) ：等待对方程序调用 receive()。随后，向对方发送 $1$ 个比特的值 $x$。
• receive() ：等待对方程序调用 send()。随后，接收来自对方的 $1$ 个比特值 $x$，并返回该值。

交流结束后，每个程序需调用以下函数一次，输出 $C$ 的值。

• answer(x) ：回答 $C$ 的值为 $x$。调用该函数后，程序必须立即退出。

若 Alice 和 Bob 均正确输出了 $C$，则本次游戏成功。此时，send() 函数的总调用次数越少，得分越高。

请设计两个程序 Alice 与 Bob，在尽量少的函数调用次数下使游戏成功。

本题为【交互题】（你的程序需要与评测程序通过标准输入输出进行交互）。
你的程序将分别作为 Alice 或 Bob 运行，通过评测程序协同完成游戏。

程序启动

你的程序首先会收到如下格式的输入：

$\text{Player}$ $X$

其中，$\text{Player}$ 是字符串 Alice 或 Bob，$X$ 是 $0 \leq X < 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。若在交互过程中收到 $-1$，表明判为 WA，请立即退出程序。

answer

调用 answer 函数时，请输出：

answer $x$

其中 $x$ 必须等于 $\min(A, B)$。调用后需立即退出程序。

评分

对于一个测试用例，Alice 与 Bob 的两程序调用 send() 的总次数为 $Q'$。取所有测试用例中 $Q'$ 的最大值 $Q$，得分计算如下：

• 若 $Q \leq 76$，得 $100$ 分；
• 若 $76 < Q \leq 128$，得 $\left\lfloor 100 - 27 \cdot \ln\left(\frac{Q-74}{2}\right)\right\rfloor$ 分；
• 若 $Q > 128$，得分为 $0$（即判为 WA）；

注意事项

• 每次输出都要以换行结尾并 flush 标准输出，否则可能因 TLE 被判失败。
• 测评时，Alice、Bob 程序与评测程序将一同运行。你的程序的时间与内存消耗为三者之和，请注意预留空间。
  • 评测程序大约消耗 50ms、5MiB。
• 本题运行中不可新建文件，否则会判为 WA。例如 C# 需使用 C# AOT 替代标准 C# 环境。
• 所有整数均在 $[0, 2^{64})$ 范围之内，注意防止溢出。

输入输出样例

Alice 的输入	Alice 的输出	Bob 的输入	Bob 的输出	说明
Alice 31	send 0 receive 1 send 1 receive answer 25	Bob 25	receive 0 send 1 receive 1 answer 25	例子

由 ChatGPT 5 翻译