配点 : 100 点
問題文
兔子很长 N 整数序列 给出 a = \{a_0,a_1,...,a_{N-1}\} 已经准备好了。
你可以问兔子以下问题。
- r-l 是 在 2 冪数 (1,2,4,8,...) 差不多是这样 l,r (0 \leq l \lt r \leq N) 组 1 序列选择 a 间隔 [l,r) 的和,即, 请咨询 (a_l+a_{l+1}+...+a_{r-1}) 。
尽可能以最少的提问次数,猜出数列 a 中包含的数字总和。
制約
- 1 \leq N \leq 10^5.
- 0 \leq a_i \leq 10^4.
採点
- 在所有测试用例中,提问次数最多的那个用例的次数 x 时, 我想知道,“有多少种方法可以选择一个整数使得900/max(x,9) 的小数点以下去掉后的值即为得分。
- 但如果有任何不正确的情况, 1 即使只有一个也算不正确。 0 点。
入出力
- 首先,会给出表示数列长度的整数 N 在标准输入中。
- 接着,只要不超过程序的执行时间限制,你的程序可以进行任意次数的提问。
- 每次提问时,要将字符
?和 按字典顺序比较 2 整数 l,r 用空格分隔输出到标准输出。- l,r 必须满足题目中的条件。
- 然后,会在标准输入中给出数列 a 间隔 [l,r) 的和。
- 每次提问时,要将字符
- 最后,字符
!并将包含在数列 a 中的数字的总和以空格分隔输出。
参考输入输出示例。
注意点
输出答案后,你的程序必须立即结束。 如果未结束,评测结果不确定。同样,如果输出不正确,结果也不确定(不一定 WA 。
如果你的程序输出了正确答案并结束,则视为正确答案。
注意,在输出之后必须刷新输出。如果不刷新输出,可能会导致超时(TLE)。
每种语言的输入/输出方法都是过去 AtCoder 问题中提出的问题(链接: ABC 019 D:高桥君和树的直径会更好。 给出
入出力例
N=7,\ a = \{1,2,3,4,5,6,7\} 时的输入输出示例。 已给出
| 入力 | 出力 | 説明 |
|---|---|---|
| 7 | 序列长度 N 。 询问 | |
| ? 0 1 | 区間 [0,1) 的和。 | |
| 1 | 已给出问题的回答。 | |
| ? 0 4 | 区間 [0,4) 的和。 | |
| 10 | 已给出问题的回答。 | |
| ? 1 3 | 区間 [1,3) 的和。 | |
| 5 | 已给出问题的回答。 | |
| ? 3 7 | 区間 [3,7) 的和。 | |
| 22 | 已给出问题的回答。 | |
| ! 28 | 正在输出答案。 |