题目背景
小 E 和小 F 是一对好闺蜜。
题目描述
这是一道通信题。
小 E 有一些很重要的信息要传给小 F。信息的内容可以用一个不超过
但是小 E 现在只有鸽子。好多好多的鸽子。黑色和白色的鸽子。
小 E 可以让不同颜色的鸽子按一定的顺序起飞,飞到小 F 那里,这样小 F 就可以根据降落的鸽子的颜色顺序来知道信息的具体内容了。当然鸽子的数量是需要约定好且固定的,不然小 F 可能会在看到所有鸽子之前误以为所有的鸽子都已经飞过来了。
但是众所周知,“鸽子”一词总是和“时间”联系在一起。鸽子会放鸽子。不过小 E 的鸽子还算守时,起飞和降落的顺序之差不会超过一个正整数
小 E 自然是考虑到了这些情况,并提前与小 F 约定好了。请问如果你是小 E 你要怎样做下约定以及发送信息呢?
实现细节
你不需要也不应该实现主函数。你需要实现三个函数 pigeon_num
,send
和 receive
。
函数 pigeon_num
的接口如下:
int pigeon_num(int Taskid, int k);
- 该函数传入子任务编号
Taskid
和题目中参数k
的值。 - 该函数需要返回小 E 需要放飞的鸽子数量
。
函数 send
的接口如下:
std::string send(int Taskid, int n, int k, __uint128_t msg);
- 该函数传入子任务编号
Taskid
,pigeon_num
函数的返回值n
,题目中的参数k
以及需要发送的信息msg
。 - 该函数需要返回一个长度恰好为
的字符串,其中下标为 的位置表示小 E 放飞的第 只鸽子的颜色,0
表示黑色,1
表示白色。
函数 receive
的接口如下:
__uint128_t receive(int Taskid, int k, const std::string &msg);
- 该函数传入子任务编号
Taskid
,题目中的参数k
以及小 F 看到的鸽子的降落顺序msg
。 msg
为一个长度为 的字符串,其中下标为 的位置表示小 F 看到的第 只降落的鸽子的颜色,0
表示黑色,1
表示白色。msg
的值与某次调用send
函数的返回值有着题目描述中所满足的关系。- 该函数需要正确返回小 E 发送的信息的内容。
你可以参考下发的样例程序 pigeon.cpp
,也可以从头开始写一个程序。
在评测时,交互库会被运行两次,两次运行独立计算时间和空间。
在第一次运行时,交互库会先调用一次 pigeon_num
函数,然后调用不超过 send
函数。
在第二次运行时,交互库会调用不超过 receive
函数。
保证在题目限制下,评测交互库的运行时间不超过
测试程序方式
将样例交互库 grader.cpp
和你的代码 pigeon.cpp
置于同一目录下并在终端中输入如下命令进行编译:
g++ pigeon.cpp grader.cpp -o grader -g -Wall --std=c++11
然后运行 ./grader
即可。样例交互库使用标准输入和标准输出,只需要运行一次。
注意下发的交互库与实际评测时使用的交互库的实现不同。比如在下发的交互库中,通过 send
函数修改的全局变量的值能够被 receive
函数查看。
样例交互库输入格式
第一行三个非负整数
接下来
样例交互库输出格式
如果你的程序在该测试点上是正确的,对于每一条信息,交互库会输出四行内容。
- 第一行
Message
为小 E 想要发送的信息,即send
函数中参数msg
的内容。 - 第二行
Taking off
为鸽子起飞的顺序,即send
函数的返回值。 - 第三行
Landing
为鸽子降落的顺序,即receive
函数中参数msg
的内容。 - 第四行
Received
为小 F 解读出来的信息,即receive
函数的返回值。 - 最后一行输出
Accepted using <num> pigeon(s).
,其中<num>
是小 E 放飞的鸽子的数量,即pigeon_num
函数的返回值。
否则如果程序正常退出,交互库会输出以下内容之一:
Invalid number of pigeons.
:输出这句话说明pigeon_num
函数的返回值不在 之间。Invalid color of pigeon.
:输出这句话说明send
函数的返回值中有非0
或1
的字符。Too few or too many pigeons taking off.
:输出这句话说明send
函数的返回值的长度不等于pigeon_num
函数的返回值。Received wrong message.
:输出这句话说明receive
函数的返回值与send
函数中的参数msg
不相等。
一旦交互库输出了报错语句,交互库程序就会立即停止运行。
样例一
输入
0 6 1
97429867398990605044182047185430790478
输出
Message: 97429867398990605044182047185430790478
Taking off: 10101
Landing: 10011
Received: 97429867398990605044182047185430790478
Accepted using 5 pigeons.
解释
这是样例交互库在下发样例程序 pigeon.cpp
在样例输入下的输出。
对于小 E 来说,
子任务
子任务 pigeon.cpp
能够通过样例。该子任务的评测结果会显示在评测结果中。
子任务
子任务
子任务
评分方式
评测时,你只需在 OJ 上提交你的源程序,修改下发的其他文件不会对评测结果产生影响。
本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得
对于每个子任务,如果你的程序有以下行为,将会被判为
pigeon_num
函数的返回值不在 之内;send
函数的返回值的长度不等于pigeon_num
函数的返回值;send
函数的返回值的内容包含0
或1
之外的字符;receive
函数没有正确地返回小 E 发送的信息内容。
此外,对于每个子任务,你的得分与小 E 放飞的鸽子的数量,即 pigeon_num
函数的返回值有关。设这个值为
在子任务
在子任务
- 如果
,那么你可以得到该测试点的满分。 - 若
,那么在此范围内 的值每多 ,你就会失去该测试点满分乘以 的分数。 - 若
,那么在此范围内 的值每多 ,你就会额外失去该测试点满分乘以 的分数。 - 若
,那么在此范围内 的值每多 ,你就会额外失去该测试点满分乘以 的分数。 - 若你的答案正确,你至少可以得到
分。
换句话说,你在一个测试点的得分等于
- 两个拐点的横坐标分别为
和 。 - 被两个拐点分割所形成的三段区间的斜率依次为
, 和 。
你的每个子任务的得分是子任务中所有测试点得分的最小值。
通过访问输入输出文件、攻击评测系统或攻击评测库等方式得分属于作弊行为,所得分数无效。
时间限制: 3s
空间限制: 2GB