Public Judge

pjudge

Time Limit: 1 s Memory Limit: 256 MB Total points: 75 Communication

# 21679. 【PER #3】别急 2

Statistics

这是一道通信题。

在 P 国主办的 Pb 学奥林匹克竞赛结束后,你被安排解决一个重要的问题:向选手邮寄他的竞赛分数。

在本次 Pb 学奥林匹克竞赛中,每位选手的分数都可以表示成一个在 $[0, 10^{10})$ 内的非负整数 $S$。为了向一位选手发送信息,你可以指定不超过 $M$ 只鸽子,并将这些鸽子发送给选手。你可以在每只鸽子上写上恰好一位数字(即一直格子上可以写着 0123456789 中的任意一个数字),这样选手在看到鸽子后就可以得到一位信息。

虽然你让主办方别急,但是主办方还是很急,不能忍受让鸽子一个接着一个发送出去,因此他要求必须同时将所有鸽子发送给选手。由于每只鸽子的顺序是不固定的,因此选手在收到所有鸽子的信息后,所有鸽子的顺序关系都将丢失。

现在,你需要给主办方和选手制定恰当的策略,使得选手能够顺利得到自己的分数。

形式化的题意

程序 Host 有一个严格小于 $10^{10}$ 的非负整数 $S$,它可以向程序 Participant 发送至少一个、至多 $M$ 个 $0 \sim 9$ 内的整数,但是发送的顺序会被交互库打乱。使用恰当的策略使得 Participant 可以复原出整数 $S$。

实现细节

这是一道通信题,本题仅支持 C++ 语言。

你需要提交两个程序,其中程序 Host 描述主办方 Host 向选手 Participant 发送信息的策略,程序 Participant 描述 Participant 复原信息的策略。

请注意,每个测试点中可能包含多组测试数据。在一个测试点中,两个程序会被要求回答独立的 $T$ 次询问。

Host

你所提交的第一个程序为 Host,描述 HostParticipant 发送信息的策略。

你需要包含头文件 Host.h,并实现以下函数:

std::string Send(long long S);
  • 在每个测试点中,该函数会被调用 $T$ 次。
  • 参数 $\texttt{S}$ 的含义即为题目中的 $S$。
  • 你需要返回一个只由数字 $0 \sim 9$ 组成的字符串,描述主办方向选手发送的信息。请注意,不能返回空串。

Participant

你所提交的第二个程序为 Participant,描述 Participant 复原信息的策略。

你需要包含头文件 Participant.h,并实现以下函数:

long long Restore(std::string X);
  • 在每个测试点中,该函数会被调用 $T$ 次。
  • 参数 $\texttt{X}$ 的含义即为主办方发送的字符串,但顺序可能被打乱。
  • 你需要返回一个整数 $S$,描述选手复原出的得分。

样例交互库

本题下发文件中含有样例交互库 grader.cpp,选手可使用以下命令编译得到可执行文件:

g++ Host.cpp Participant.cpp grader.cpp -o answer -O2 -std=c++14

可执行文件将从标准输入中通过以下格式读取输入数据:

  • 输入的第一行包含一个整数 $T$,表示测试的数据组数。
  • 对于每组数据,输入只有一行,包含一个整数 $S$。

可执行文件将向标准输出中输出以下数据:

  • 若通信过程出现了错误,则输出对应的错误信息。
  • 否则,输出的第一行包含一个字符串 OK,第二行包含你在所有询问中的返回的串的长度的最大值 $L$。

需要注意的是:

  1. 样例交互库不会检查选手的程序是否使用了非法手段传递信息。
  2. 样例交互库中,随机打乱 Send 函数返回的字符串的策略在每次运行中不是固定的。如果你想要更改为固定策略,你可以将随机数生成器 rng 的种子修改为固定的值,例如修改为:
std::mt19937 rng(123456);

在最终评测时,程序 HostParticipant 将被分别编译并在两个不同的进程中运行。本题的时间限制(1.0 秒)与空间限制(256 MiB)均指每个进程所能使用的时间与空间的最大值。在任意一个进程中超过该限制都会导致发生相应的错误。保证在最终评测时,三个程序各自的交互库使用的时间不超过 0.2 秒,空间不超过 16 MiB,即选手至少有 0.8 秒的时间与 240 MiB 的空间可用。

请注意,你不需要,也不能从标准输入中读取任何数据,也不能向标准输出中输出任何信息,否则可能导致通信的过程出现异常。

样例数据

样例输入

7
0
1
2
42
998244353
1000000007
2333333333

样例输出

OK
L = 42

需要注意输出的第二行表示的是选手所返回的串的长度的最大值,其可能根据你使用的策略不同而变化。

子任务

请注意,本题满分为 75 分。

对于所有数据,$1 \le T \le 10^3$,$0 \le S < 10^{10}$。

子任务编号 特殊性质 分值
$1$ $75$

在每个测试点中,如果你在任意一组询问中返回了错误的 $S$,或发生了其他错误,则你的得分为 $0$。

否则, 记 $L$ 为你在所有询问中返回的串的长度的最大值,则你的得分与 $L$ 的值有关:

$L$ 的范围 分值
$L \le 50$ $75$
$50 < L \le 105$ $22.5(11 - \sqrt{L})-15$
$105 < L$ $0$

Hack

Hack 功能在本题中不可用。