← 返回题目列表

AtCoder · xmascon16_a

A. 数组和

中文机器翻译题面 查看原题

配点 : 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 点。

入出力

  1. 首先,会给出表示数列长度的整数 N 在标准输入中。
  2. 接着,只要不超过程序的执行时间限制,你的程序可以进行任意次数的提问。
    1. 每次提问时,要将字符 ? 和 按字典顺序比较 2 整数 l,r 用空格分隔输出到标准输出。
      • l,r 必须满足题目中的条件。
    2. 然后,会在标准输入中给出数列 a 间隔 [l,r) 的和。
  3. 最后,字符 ! 并将包含在数列 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 正在输出答案。