#P18956. [Mladen Manev 2022 AT6] treasury / 最少称量找假币堆

[Mladen Manev 2022 AT6] treasury / 最少称量找假币堆

最少称量找假币堆

这是交互题。有 NN 堆物品,第 ii 堆有 AiA_i 件。恰有一堆是假的,其中每件重 101 克;其余每件重 100 克。假堆编号由交互器固定,选手不知道。

每次称量选择整数 p1,…,pNp_1,\ldots,p_N,满足 0≤pi≤Ai0\le p_i\le A_i,称出所取物品的总重量。称量后物品仍然可以在后续称量中使用。

需要识别假堆,并使最坏情况下的称量次数最少。

交互协议

先读入 NN,再读入 NN 个整数 AiA_i,这是公开信息。满足 1≤N≤1061\le N\le10^6、1≤Ai≤1091\le A_i\le10^9。

称量时输出 ? p1 p2 ... pN,刷新输出,随后读入一个 64 位整数总重量。

也支持等价的紧凑格式 @ d S:1≤d≤101\le d\le10,字符串 SS 恰好有 NdNd 个十进制数字;将其从左到右每 dd 位分成一组,分别表示 p1,…,pNp_1,\ldots,p_N,不足 dd 位的数前补零。例如 @ 2 000102 表示 (0,1,2)(0,1,2)。每组数仍须满足容量限制;计为一次称量,返回值不变。大规模数据请使用紧凑格式,避免分隔符导致过大的累计通信量。

确定假堆后输出 ! k,其中 kk 为从 11 开始的堆编号,刷新输出并退出。最终回答不算称量。

计分

设 WW 为根据公开数组 AA,在所有可能假堆中取最坏情况时,理论上所需的最少称量次数。答案正确且称量不超过 WW 次获得该测试的满分,使用 W+1W+1 次得一半,W+2W+2 次得四分之一,更多则不得分。

本题包总分为 100,测试捆绑计分,满分要求所有测试都在最优次数内完成。N=1N=1 时 W=0W=0,应直接回答。

交互示意

公开信息为 A=(1,2,3)A=(1,2,3)。称量 ? 0 1 2,若返回 302,正常基准重量为 300300,多出的 22 克说明第三堆是假堆,可以输出 ! 3。

题包说明

原题使用 inicjuj/waz/odpowiedz 库接口,本题包改为等价的标准流协议。隐藏数据文件格式为 N,kN,k 及数组 AA;交互器只把 N,AN,A 发送给选手。允许某个 pi=0p_i=0,与官方勘误一致。

本题原为波兰 IOI 2020 选拔赛第二天 Skarbiec,由本网站 2022 年训练赛选用。官方分析。

来源与数据说明

2022 年 Dr. Mladen Manev,AT6,原题名 treasury。赛事资料,原文题面见附件 statement.pdf。

原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。