AT_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 翻译