← 返回题目列表

Codeforces · 753/C

C. 互动公牛和奶牛(困难)

中文机器翻译题面 查看原题

与上一个问题的唯一区别是请求数量的限制。在这个问题中,你的程序应该猜测最多 7 个请求的答案。

这个问题有点不寻常。您将在此处实现与测试系统的交互。这意味着您可以在在线模式下提出查询并获得答复。请确保在每个查询输出后使用流刷新操作,以免将部分输出留在某些缓冲区中。例如,在 C++ 中,您必须使用 fflush(stdout) 函数,在 Java 中,调用 System.out.flush(),在 Pascal 中,您必须使用 fflush(output)。

Bulls and Cows(也称为 Cows and Bulls 或 Pigs and Bulls 或 Bulls and Cleots)是一种古老的两人密码破译纸笔游戏,早于类似的商业化棋盘游戏 Mastermind。

在一张纸上,第一个玩家思考一个秘密字符串。该字符串仅由数字组成,长度为4。字符串中的数字必须全部不同,不允许有两个或多个相同的数字。

然后第二个玩家尝试猜测对手的字符串。对于每次猜测,第一位玩家都会给出匹配的数量。如果匹配的数字位于正确的位置,则它们是“公牛”,如果位于不同的位置,则它们是“母牛”。因此,响应是一对数字——“公牛”的数量和“奶牛”的数量。尝试可以包含相同的数字。

更正式地说,假设秘密字符串是 s,第二个玩家尝试用字符串 x 来猜测它。 “公牛”的数量是这样的位置 i (1 ≤ i ≤ 4) 的数量,其中 s[i] = x[i]。 “奶牛”的数量是这样的数字 c 的数量,即 s 在位置 i 处包含 c(即 s[i] = c),x 包含 c,但 x[i] ≠ c。

例如,秘密字符串是“0427”,对手的尝试是“0724”,那么答案是2头牛和2头牛(公牛是“0”和“2”,牛是“4”和“7”)。如果秘密字符串是“0123”,对手的尝试是“0330”,那么答案是1头牛和1头牛。

在本题中,您要猜测系统选择的字符串 s。您只知道所选字符串由 4 个不同的数字组成。

您可以向测试系统进行查询,每个查询都是单个4位字符串的输出。查询的答案是公牛的数量和奶牛的数量。如果系统的响应等于“4 0”,则意味着与问题的交互结束,程序必须终止。这可能有两个原因:程序要么猜测了数字 x,要么做出了无效的操作(例如,打印字母而不是数字)。

您的程序最多可以执行 7 个查询。

您可以破解其他参与者的解决方案,提供包含不同数字的 4 位数字字符串(秘密字符串)。

输入

要读取查询的答案,程序必须使用标准输入。

程序将在输入中接收非负整数对,每行一对。一对中的第一个数字是公牛的数量,第二个是程序打印的字符串 s 和字符串 xi 中的母牛的数量。如果系统响应等于“4 0”,那么您的解决方案应该终止。

仅当您的程序在输出中显示相应的系统查询后,测试系统才会让您的程序从输入中读取第i对整数:在一行中打印值 xi 并执行操作flush。

输出

程序必须使用标准输出来打印查询。

您的程序必须输出请求 — 4 位字符串 x1, x2, ...,每行一个。程序在每行输出后必须执行flush操作。程序应该从标准输入读取查询的答案。

您的程序最多可以执行 7 个查询。

示例

输入 #1

0 1
2 0
1 1
0 4
2 1
4 0

输出 #1

8000
0179
3159
3210
0112
0123

注意

示例中的秘密字符串 s 是“0123”。