巫师巴伊塔扎尔(Bajtazar)在多年后终于找到了仪式文本,通过该仪式,他可以召唤伟大的二进制小妖精(Chochlik),以回答人类的永恒问题:$P = NP$ 吗?然而,为了完成仪式,必须念出小妖精的全名,而巴伊塔扎尔并不知道这个名字。已知该名字是一个恰好由 100 个字符组成的字符串。正如二进制小妖精的身份所示,这些字符仅由 0 和 1 组成。
巴伊塔扎尔可以多次尝试仪式(但不得超过 222 次,否则他那古老的炼金设备最终会罢工)。如果他能有一次念出小妖精的正确名字,仪式就会成功,世界计算机科学将永远改变。凭借他的魔法直觉,巴伊塔扎尔在每次尝试后都能准确知道这次他念对了多少个字符。然而,还有一个额外的复杂情况:小妖精是一个极其反复无常的生物,有时会改变主意,更改自己的名字。更准确地说,在巴伊塔扎尔的每次失败尝试后,小妖精会从集合 $\{0, 1, \dots, 99\}$ 中均匀随机地抽取一个数字 $k$。如果巴伊塔扎尔在这次尝试中恰好猜对了第 $k$ 个字符,小妖精会立即将其名字中的该字符更改为相反值(0 变为 1,1 变为 0)。
作为巫师倒霉的学生,你必须帮助他猜出小妖精的名字——动作要快,否则愤怒的巴伊塔扎尔可能会把你变成……嗯,变成某种糟糕的东西。比如消防栓。而且你应该庆幸他现在没有尝试召唤“非常伟大的十六进制小妖精”。
交互
为了解决此问题,你需要在程序开头包含以下指令:
#include "cho.h"
该库仅提供一个函数:
int recytuj(const std::string& proba);
该函数的作用如上所述——如果字符串 proba 与小妖精的真实名字完全相同,你的程序将立即终止并被判定为通过。如果不同,该函数将返回一个数字(介于 0 到 99 之间),等于与真实名字匹配的字符数,此外还会执行类似于以下的代码片段:
int k = rand() % 100; // 库的真实实现不使用 rand() 函数。
if(proba[k] == prawdziwe_imie[k])
flip(prawdziwe_imie[k]);
其中 prawdziwe_imie 表示小妖精的(秘密)名字,而 flip() 会将对应的字符从 0 变为 1,反之亦然。
对于每次查询,proba 必须是一个恰好由 100 个字符组成的字符串,每个字符为 0 或 1。你调用 recytuj() 的次数不得超过 222 次——如果你违反了任何这些规则,你将收到“错误答案”(Wrong Answer)的判决。
小妖精的初始名字在每个测试用例开始时确定。
样例
为了简化,假设小妖精的名字长度为 6。此假设仅适用于此示例,此类测试不会出现在测试集中(提交的解决方案不会在此类测试上运行)。设小妖精的名字为 42(即 101010)。假设在第一次调用中抽取的 $k$ 为 3,第二次为 0。
| 名字 | 调用 | 结果 | $k$ | 注释 |
|---|---|---|---|---|
| 101010 | recytuj("010010") |
3 | 3 | 字符串 101010 和 010010 在最后三个位置上一致,因此返回结果为 3。抽取的 $k$ 也是 3。由于第三个(从零开始计数)位在我们的查询中是正确的,它在小妖精的名字中被改变,名字变为 101110。 |
| 101110 | recytuj("001111") |
4 | 0 | 这次我们发现我们在第 $k$ 个位置($k=0$)猜错了,因此名字保持不变。 |
| 101110 | recytuj("101110") |
6 | - | 我们猜对了小妖精的名字。你的程序将自动终止。不会再抽取新的 $k$。 |