这是一道交互题。
一年过去了,阿尔塔尔站在曾被他摧毁的祭坛面前。祭坛上的宝石早已失去了原有的光泽。
“解铃还须系铃人,是这样吗?”他喃喃自语。
祭坛呈正
宝石之间存在着能量流动关系,这使得激活一些宝石之后可以更容易地激活其他宝石。对于每一对宝石
为了激活祭坛,阿尔塔尔需要激活所有的宝石。为此,阿尔塔尔需要首先选择
由于能量传递需要耗费大量体力,阿尔塔尔希望找到一个宝石,将其初始激活之后可以使用最少次数的能量传递激活所有宝石。为此,阿尔塔尔可以进行若干次能量感知:给出
你需要帮助阿尔塔尔使用尽可能少的能量感知操作,确定初始激活的宝石编号。可以证明总是存在一个宝石,将其初始激活后使用有限次能量传递即可激活所有宝石。
实现细节
请确保你的程序开头有 #include "altar.h"
你不需要也不应该实现主函数。你需要实现以下函数:
int altar(int n);
其中
表示祭坛上的宝石数量。你需要返回一个整数
,表示阿尔塔尔需要初始激活宝石 。你需要保证 ,且在所有宝石中初始激活 可以让阿尔塔尔使用最少次数的能量传递激活所有宝石。在最终测试时,交互库会在一次运行中调用
次altar
函数。
你可以调用以下函数进行能量感知:
bool sense(int i, int j);
你需要保证
且 。若
与 的能量流动为 向 ,其返回true
,否则返回false
。你需要保证在一次
altar
的调用中sense
的调用次数不超过 。
在满足题目条件和数据范围的情况下,最终测试时交互库的运行时间不会超过
交互库不是自适应的,即能量流动关系是固定的,不会随着交互过程改变。
测试程序方式
试题目录下的 grader.cpp
是我们提供的交互库参考实现。最终测试的交互库与样例交互库有一定不同,故你的实现不应该依赖样例交互库实现。
你需要在本题目录下使用如下命令编译得到可执行程序:
g++ grader.cpp sample.cpp -o sample -O2 --std=c++14 -lm
对于编译得到的可执行程序:
可执行文件将从标准输入读入以下格式的数据:
– 第一行一个整数
– 接下来 01
字符串,其中第 1
表示能量流动从 1
另一个为 0
,样例交互库并不会判断输入是否满足条件。
读入完成之后,交互库将调用恰好一次函数 altar
。
在 altar
函数退出后,如果你给出了正确的宝石编号,交互库将在标准输出流输出 Correct. X
,其中 sense
的调用次数,并在标准错误流输出你返回的宝石编号以及对应的能量传递次数;否则交互库将在标准输出流输出 Wrong Answer
并在标准错误流输出对应错误信息。
样例 #1
样例输入 #1
4 0011 1010 0000 0110
样例输出 #1
Correct. 1 You report 2, with number of energy propagations to be 2
【样例 1 解释】
该样例输出为下发的样例程序在该组样例下的输出。该样例中,altar
返回
子任务
对于所有测试数据,单个测试点中 altar
函数的调用次数
子任务
评分方式
本题首先会受到和传统题相同的限制,例如编译错误会导致整道题目得
对于每个测试点,如果你的程序出现了非法的函数调用,或没有在所有测试数据中都返回正确的宝石,你将获得该测试点 altar
调用中的 sense
调用次数的平均值
若
,你可以获得 的分数;若
,你可以获得 的分数;若
,你可以获得 的分数;若
,你可以获得该测试点 的分数;
每个子任务的分数为该子任务中所有测试点的得分占比的最小值与该子任务满分的乘积。
选手不应通过非法方式获取交互库的内部信息,如试图与标准输入、输出流进行交互。此类行为将被视为作弊。