#P18956. [Mladen Manev 2022 AT6] treasury / 最少称量找假币堆
[Mladen Manev 2022 AT6] treasury / 最少称量找假币堆
最少称量找假币堆
这是交互题。有 堆物品,第 堆有 件。恰有一堆是假的,其中每件重 101 克;其余每件重 100 克。假堆编号由交互器固定,选手不知道。
每次称量选择整数 ,满足 ,称出所取物品的总重量。称量后物品仍然可以在后续称量中使用。
需要识别假堆,并使最坏情况下的称量次数最少。
交互协议
先读入 ,再读入 个整数 ,这是公开信息。满足 、。
称量时输出 ? p1 p2 ... pN,刷新输出,随后读入一个 64 位整数总重量。
也支持等价的紧凑格式 @ d S:,字符串 恰好有 个十进制数字;将其从左到右每 位分成一组,分别表示 ,不足 位的数前补零。例如 @ 2 000102 表示 。每组数仍须满足容量限制;计为一次称量,返回值不变。大规模数据请使用紧凑格式,避免分隔符导致过大的累计通信量。
确定假堆后输出 ! k,其中 为从 开始的堆编号,刷新输出并退出。最终回答不算称量。
计分
设 为根据公开数组 ,在所有可能假堆中取最坏情况时,理论上所需的最少称量次数。答案正确且称量不超过 次获得该测试的满分,使用 次得一半, 次得四分之一,更多则不得分。
本题包总分为 100,测试捆绑计分,满分要求所有测试都在最优次数内完成。 时 ,应直接回答。
交互示意
公开信息为 。称量 ? 0 1 2,若返回 302,正常基准重量为 ,多出的 克说明第三堆是假堆,可以输出 ! 3。
题包说明
原题使用 inicjuj/waz/odpowiedz 库接口,本题包改为等价的标准流协议。隐藏数据文件格式为 及数组 ;交互器只把 发送给选手。允许某个 ,与官方勘误一致。
本题原为波兰 IOI 2020 选拔赛第二天 Skarbiec,由本网站 2022 年训练赛选用。官方分析。
来源与数据说明
2022 年 Dr. Mladen Manev,AT6,原题名 treasury。赛事资料,原文题面见附件 statement.pdf。
原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。