自动搬运

查看原文

来自洛谷，原作者为

	Ian_NIE 以梦为马，不负韶华 || 坐标北京人大附中

搬运于2025-08-24 23:14:24，当前版本为作者最后更新于2025-06-01 11:22:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

0x00 前言

这是一道简单的交互题。

另外：没有必要和洛谷的帮助中心一样写 extern "C"，直接先输出再输入即可，毕竟原题没有给出固定的交互库。

关于题目已经给出的一个 Python 代码是 Special Judge，并不是交互库。

0x01 题目大意

现在有三个未知数 $a$，$b$ 和 $c$。现在你可以向评测提问五个式子，形如 $x_1a + x_2b + x_3c$，评测机会告诉你这个式子的结果。但是在五个回复中最多存在一个答案是错的，求 $a$，$b$，$c$。

0x02 算法设计（？）

准确来说是数学分析。

对于这个问题，我们可以先询问评测机 $a$，$b$，$c$。接下来我们需要一个检查这三个是否正确的式子，所以我们想到了 $a + b + c$。但是，我们不能够确定这个“试金石”是否正确，所以我们还需要一块完全不一样的：$a + 2b + 3c$。

注意，我们不可以把两块试金石造成 $a + b + c$ 和 $2a + 2b + 2c$ 这样的格式，否则如果这两个都是正确的，我们就无法分辨 $a$，$b$，$c$ 中错误的是哪一个了。所以，我们的“double check”必须和原来的那个不等价但是此时，我们的试金过程也变得复杂。

首先，我们先假设评测机回答的是这样五个式子：

$$\begin{cases} a = A\\ b = B\\ c = C\\ a + b + c = D\\ a + 2b + 3c = E \end{cases} $$

继续，如果 $A + B + C = D$ 或者 $A + 2B + 3C = E$，那么对应的四个式子一定是对的。因为如果有错的，那么那个错的结果和评测机给出的结果的两个式子全部都是错的，矛盾，所以都是对的。此时显然：

$$\begin{cases} a = A\\ b = B\\ c = C \end{cases}$$

如果上面的两个全部都是错的，那么证明 $D$ 和 $E$ 全部都是对的，因为如果有一个是错的，那么另一个和 $A$，$B$，$C$ 就都是对的，上面的式子就有一个会成立，矛盾，所以都是对的。现在我们继续检查 $A$，$B$，$C$ 当中谁是错的。

假设 $A$ 是错的，那么 $E - D = B + 2C$，因为剩下的都是对的。反过来，如果这个式子是对的，那么 $A$ 就是错的。和上面证明的逻辑相同，这个式子代表了 $B$，$C$，$D$，$E$ 全部都是对的，所以 $A$ 就是错的（显然 $A$，$B$，$C$ 中必须有一个是错的，所以 $A$ 不可能是对的）。此时：

$$\begin{cases} a = D - B - C\\ b = B\\ c = C \end{cases} $$

同理可得，当 $E - 2D = -A + C$ 时，$B$ 错，所以：

$$\begin{cases} a = A\\ b = D - A - C\\ c = C \end{cases} $$

第三种情况读者自证不难。

所以，代码就是 if else，没有难度了吧。

0x03 部分代码实现

下面的求答案的过程大家自己写吧，很简单。我就简单说一下输入输出，直接这样写就可以。

大家都是第一次做交互题吧，经验大佬请直接跳过。

/*
a = ans1;
b = ans2;
c = ans3;
a + b + c = ans4;
a + 2b + 3c = ans5;
*/ 
	cout << "1 0 0" << endl, cin >> ans1;
	cout << "0 1 0" << endl, cin >> ans2;
	cout << "0 0 1" << endl, cin >> ans3;
	cout << "1 1 1" << endl, cin >> ans4;
	cout << "1 2 3" << endl, cin >> ans5;

0x04 完整代码

一个整合没有解释。

0x05 后记

本人第一次写交互题。

AC 记录。