Guess the Sum

题目描述

这是一个 交互式问题（你的程序通过标准输入输出与裁判交互）。 给定正整数 $N$ 和整数 $L$ 与 $R$ 满足 0 \leq L \leq R < 2^N。裁判有一个隐藏序列 $A = (A_0, A_1, \dots, A_{2^N-1})$，序列元素为 $0$ 到 $99$ 之间的整数（包含端点）。 你的目标是求出 $A_L + A_{L+1} + \dots + A_R$ 被 $100$ 除后的余数。但你不能直接知道序列 $A$ 中元素的值。相反，你可以向裁判询问如下问题：

选择非负整数 $i$ 和 $j$，满足 $2^i(j+1) \leq 2^N$。令 $l = 2^i j$ 且 $r = 2^i (j+1) - 1$。询问 $A_l + A_{l+1} + \dots + A_r$ 被 $100$ 除后的余数。

设 $m$ 为在任意序列 $A$ 情况下确定 $A_L + A_{L+1} + \dots + A_R$ 被 $100$ 除后的余数所需的最小问题次数。你需要在不超过 $m$ 个问题内找到该余数。

输入格式

输出格式

提示

$1 \leq N \leq 18$ $0 \leq L \leq R \leq 2^N - 1$ 所有输入值均为整数。这是一个交互式问题（你的程序通过标准输入输出与裁判交互）。 首先，从标准输入读取整数 $N$、$L$ 和 $R$： $N$ $L$ $R$

然后，重复提问直到你可以确定 $A_L + A_{L+1} + \dots + A_R$ 被 $100$ 除后的余数。每个询问应按以下格式输出： $?$ $i$ $j$

其中，$i$ 和 $j$ 必须满足以下约束：

$i$ 和 $j$ 为非负整数。 $2^i(j+1) \leq 2^N$

对于该询问，裁判会在标准输入中返回如下格式的回答： $T$

其中，$T$ 是问题的答案，即当 $l = 2^i j$ 且 $r = 2^i (j+1) - 1$ 时 $A_l + A_{l+1} + \dots + A_r$ 被 $100$ 除后的余数。 如果 $i$ 和 $j$ 不满足约束，或提问次数超过 $m$，则 $T$ 将为 $-1$。 如果裁判返回 $-1$，你的程序已被判为错误。在这种情况下，立即终止程序。 一旦你确定了 $A_L + A_{L+1} + \dots + A_R$ 被 $100$ 除后的余数，请按以下格式输出该余数并立即终止程序： $!$ $S$在每次输出的末尾打印换行并刷新标准输出。否则，判题可能会出现 TLE。 如果你的输出格式不正确或程序提前退出，判题结果将不确定。 输出答案后，立即终止程序。否则，判题结果将不确定。下面给出 $N=3$、$L=1$、$R=5$ 以及 $A=(31, 41, 59, 26, 53, 58, 97, 93)$ 的示例。在此例中，$m=3$，因此你最多可以询问三次。

标签: AtCoder|abc355E

来源

AtCoder|abc355E