A - Array Sum 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

配点 : 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 になるとは限らない）．

あなたのプログラムが正しい答えを出力して終了した場合，正答とみなされる．

出力した後に，出力をflushしなければならないことに注意せよ．flushしなかった場合，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 答えを出力している．