QOJ.ac

QOJ

Points totaux : 100 Interactif Indisponible

#11141. 小恶魔

Statistiques

巫师巴伊塔扎尔(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$。

ou importez des fichiers un par un

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.