AT_abc355_e [ABC355E] Guess the Sum

题目描述

本题是一个交互式问题（你的程序需要与评测系统通过输入输出进行交互）。

给定正整数 $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 翻译