这是一道交互题
V 君、I 君和 Y 君是好朋友。
I 君最近开了一家商店,商店里准备了
V 君想知道每个物品的价格,他已经通过某种超自然力量知道,这
然而, V 君并不想自己去问 I 君,他选择了这样一种方法:他准备了
带着很多物品跑腿是一个很累的事情,因此,我们定义一次跑腿的体力消耗是
你的任务是:写一个程序,帮助 V 君决定如何合理地让 Y 君跑腿,从而推算出每种物品的价值。Y 君的体力有限,你当然不能让他过于劳 累,也即,你不能让他的总体力消耗超过某个预设的阈值
实现细节
你不需要,也不应该实现主函数,你只需要实现下列函数:
find_price(task_id, N, K, ans)
- 其中
task_id
表示子任务编号(见限制与约定)。 表示物品个数, 的意义为:- 若
,表示有偶数个物品价值为 ; - 若
,表示有奇数个物品价值为 。
- 若
- 你需要将计算出的物品价格放在数组
中,其中 表示编号为 的物品的价格。
你可以通过调用如下函数来向交互库发出询问:
query(S, nS, T, nT)
- 这里
, 数组 和数组 分别描述两个集合,你需要保证: ; ; ; 的意思是:「对于任意的」。例如: 的意思是:「对于任意的在 内的 , 在 内」。
- 调用此函数一次的时间复杂度为
。它的返回值为 或 ,返回值的意义为:- 若集合
的物品价格和更大,返回 ; - 若集合
的物品价格和更大,返回 ; - 否则,按照某种未知规则返回
或 。
- 若集合
- 如题面所述,我们定义这样一次调用的代价为
。
评测时,交互库可能会调用 find_price
多次(不超过
可执行文件将从标准输入读入以下格式的数据:
第一行一个整数
- 第一行包含两个整数
; - 接下来一行一个长度为
的 串 ,其中 表示物品 的价格。你需要保证至少有一个物品价格为 。
读入完成之后,交互库将调用 find_price
函数。
接下来交互库会判断你的函数每次计算是否正确,若全部正确则会输出 Correct
,否则会输出相应的错误信息。
评分标准
最终评测时只会收取 shop.cpp/c/pas
,修改选手目录中的其他文件对评测无效。
题目首先会受到和非交互式程序题相同的限制。例如编译错误会导致整道题目得
在上述条件基础上,在一个测试点中,你得到满分,当且仅当每一次 find_price
的调用中:
- 你的每一个
query
的调用符合规则,且调用代价之和不超过 ; - 你的函数正确计算了
数组。
在一个测试点中,如果你没有获得满分,那么你获得
子任务
我们令代价之和的上界为
- 子任务 1:
; - 子任务 2:
; - 子任务 3:
,保证 ,若 则必有 。 - 子任务 4:
; - 子任务 5:
; - 子任务 6:
。
提示
I 君可能并不愿意让 V 君知道每件物品的价格,在物品价格相等时,他会按照他自己的某种方式来回答问题。
子任务分值
在本场比赛中,测试点(或子任务)的分值分布与你是否为集训队选手有关。本题的分值设置如下:
子任务编号 | ||||||
---|---|---|---|---|---|---|
集训队分值 | | | | | | |
非集训队分值 | | | | | | |
在 UOJ 上,将按照「集训队分值」一栏的分值进行评分。
时间限制: 2s
空间限制: 512MB