AT_abc355_e [ABC355E] Guess the Sum

[problemUrl]: https://atcoder.jp/contests/abc355/tasks/abc355_e 本题是一个**交互式问题**（你的程序需要与评测系统通过输入输出进行交互）。 给定正整数 $N$，以及两个整数 $L,R$，满足 $0 \leq L \leq R < 2^N$。评测系统持有一个长度为 $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$ 的余数。 对于任意的 $A$，能够确定 $A_L + A_{L+1} + \dots + A_R$ 除以 $100$ 的余数所需的最小询问次数为 $m$。请你在不超过 $m$ 次的询问内，求出 $A_L + A_{L+1} + \dots + A_R$ 除以 $100$ 的余数。

本题为交互式问题（你的程序需要与评测系统通过输入输出进行交互）。 首先，你需要从标准输入读取整数 $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$ 时，请按如下格式输出答案，并立即终止程序： > ! $S$

见上文输入格式说明。

## 约束条件 - $1 \leq N \leq 18$ - $0 \leq L \leq R \leq 2^N - 1$ - 输入均为整数 ## 注意事项 - **每次输出后请在末尾加上换行并刷新标准输出，否则可能会导致评测结果为 TLE。** - **如果在交互过程中输出格式错误或程序中途退出，评测结果不确定。** - 输出答案后请立即终止程序，否则评测结果不确定。 ## 输入输出样例 以下是 $N=3, L=1, R=5, A=(31,41,59,26,53,58,97,93)$ 时的输入输出示例。在此情况下 $m=3$，因此最多可进行 $3$ 次询问。 输入 输出 说明 3 1 5 首先给出整数 $N, L, R$。 ? 0 1 询问 $(i, j) = (0, 1)$。 41 $l=1, r=1$，因此答案为 $A_1=41$ 除以 $100$ 的余数 $41$。 ? 1 1 询问 $(i, j) = (1, 1)$。 85 $l=2, r=3$，因此答案为 $A_2+A_3=85$ 除以 $100$ 的余数 $85$。 ? 1 2 询问 $(i, j) = (1, 2)$。 11 $l=4, r=5$，因此答案为 $A_4+A_5=111$ 除以 $100$ 的余数 $11$。 ! 37 得到答案 $37$ 后输出。 由 ChatGPT 4.1 翻译