C - Beware of Overflow Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

この問題はインタラクティブな問題(あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題)です.

正整数 N が与えられます.

ジャッジシステムは正整数 R および N 個の整数 A_1,A_2,\dots ,A_N を隠し持っています. ここで |A_i|\le R,\ \left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R を満たすことが保証されます.

絶対値が R 以下の整数しか書き込むことができない黒板があり, はじめは何も書き込まれていません.

ジャッジシステムは, 黒板に A_1,A_2, \dots ,A_N の値を この順で 書き込みました. あなたは, 黒板にただ 1 つの値 \displaystyle\sum_{i=1}^{N}A_i が書き込まれている状態にする必要があります.

あなたは R および A_i の値を直接知ることはできませんが, その代わりにジャッジシステムに対して次のやり取りを 25000 回まで行うことができます.

正整数 i について, i 番目に黒板に書き込まれた整数を X_i とします. 特に, i=1,2,\dots ,N について X_i=A_i です.

1 回のやり取りでは, 相異なる正整数 i,j を指定し, 次のいずれかを選んで行います.

  • 足し算をしてもらう. ジャッジシステムは黒板から X_i,X_j を消し, 新たに X_i+X_j の値を黒板に書き込む.
    • |X_i+X_j|\le R を満たしていなくてはならない.
  • 大小比較をしてもらう. ジャッジシステムは X_i\lt X_j の真偽を答える.

ただし, 各やり取りを始める時点で i,j 番目に黒板に書き込まれた整数がすでに黒板から消されていてはなりません.

適切にやり取りを行って, 全てのやり取りを終えた後に黒板にただ 1 つの値 \displaystyle\sum_{i=1}^{N}A_i が書き込まれている状態にしてください.

R および A_i はプログラムとジャッジシステムの対話の開始前に決定されます.

制約

  • 2\leq N\leq 1000
  • 1\leq R\leq 10^9
  • |A_i|\leq R
  • \left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R
  • N,R,A_i は整数.

入出力

この問題はインタラクティブな問題(あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題)です.

最初に, N を標準入力から受け取ってください.

N

次に, 黒板にただ 1 つの値 \displaystyle\sum_{i=1}^{N}A_i が書かれている状態になるまで, やり取りを繰り返してください.

足し算をしてもらうときは, 以下の形式で標準出力に出力してください. 末尾に改行を入れてください. ここで i,j は相異なる正整数です.

+ i j

これに対するジャッジシステムの応答は, 次の形式で標準入力から与えられます.

P

ここで P は整数で,

  • P\geq N+1 の場合は, X_i+X_j の値が黒板に書き込まれ, それが P 番目に書き込まれたことを表します.
  • P=-1 の場合は, i,j が制約を満たしていないか, やり取りの回数が 25000 回を超えたことを表します.

大小比較をしてもらうときは, 以下の形式で標準出力に出力してください. 末尾に改行を入れてください. ここで i,j は相異なる正整数です.

? i j

これに対するジャッジシステムの応答は, 次の形式で標準入力から与えられます.

Q

ここで Q は整数で,

  • Q=1 の場合は, X_i<X_j が真であることを表します.
  • Q=0 の場合は, X_i<X_j が偽であることを表します.
  • Q=-1 の場合は, i,j が制約を満たしていないか, やり取りの回数が 25000 回を超えたことを表します.

足し算をしてもらうやり取りおよび大小比較をしてもらうやり取りのいずれについても, ジャッジシステムの応答が -1 であった場合は, プログラムはすでに不正解とみなされています. この場合, ただちにプログラムを終了してください.

黒板にただ 1 つの値 \displaystyle\sum_{i=1}^{N}A_i が書かれている状態になったら, 以下の形式でそのことをジャッジシステムに報告してください. ただし, これはジャッジシステムとのやり取りの回数に計上されません. その後, ただちにプログラムを終了してください.

!

上記のいずれの形式にも当てはまらない出力を行った場合は, -1 が標準入力から与えられます.

-1

このときも, プログラムはすでに不正解とみなされています. ただちにプログラムを終了してください.

注意点

  • 出力を行うたびに, 末尾に改行を入れて標準出力を flush してください. そうしなかった場合, ジャッジ結果が TLE となる可能性があります.
  • 解答を出力したら(または -1 を受け取ったら)ただちにプログラムを終了してください. そうしない場合, ジャッジ結果は不定です.
  • 余計な改行は不正なフォーマットの出力とみなされることに注意してください.

入出力例

N=3,R=10,A_1=-1,A_2=10,A_3=1 のときの対話の一例を示します.

入力 出力 説明
3 まず整数 N が与えられます。
? 1 2 大小比較をしてもらいます.
1 X_1\lt X_2\ (-1\lt 10) なのでジャッジシステムは 1 を返します.
+ 1 3 足し算をしてもらいます.
4 ジャッジシステムは X_1=-1,X_3=1 を黒板から消し, X_1+X_3=0 の値を黒板に書き込みました. 4 番目の書き込みでした.
+ 2 4 足し算をしてもらいます.
5 ジャッジシステムは X_2=10,X_4=0 を黒板から消し, X_2+X_4=10 の値を黒板に書き込みました. 5 番目の書き込みでした.
! 黒板にはただ 1 つの値 \displaystyle\sum_{i=1}^{N}A_i が書き込まれている状態になったので, そのことをジャッジシステムに報告します.

Score : 500 points

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer N.

The judge has a hidden positive integer R and N integers A_1, A_2, \dots, A_N. It is guaranteed that |A_i|\le R and \left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R.

There is a blackboard on which you can write integers with absolute values not exceeding R. Initially, the blackboard is empty.

The judge has written the values A_1, A_2, \dots, A_N on the blackboard in this order. Your task is to make the blackboard contain only one value \displaystyle\sum_{i=1}^{N}A_i.

You cannot learn the values of R and A_i directly, but you can interact with the judge up to 25000 times.

For a positive integer i, let X_i be the i-th integer written on the blackboard. Specifically, X_i = A_i for i=1,2,\dots,N.

In one interaction, you can specify two distinct positive integers i and j and choose one of the following actions:

  • Perform addition. The judge will erase X_i and X_j from the blackboard and write X_i + X_j on the blackboard.
    • |X_i + X_j| \leq R must hold.
  • Perform comparison. The judge will tell you whether X_i < X_j is true or false.

Here, at the beginning of each interaction, the i-th and j-th integers written on the blackboard must not have been erased.

Perform the interactions appropriately so that after all interactions, the blackboard contains only one value \displaystyle\sum_{i=1}^{N}A_i.

The values of R and A_i are determined before the start of the conversation between your program and the judge.

Constraints

  • 2 \leq N \leq 1000
  • 1 \leq R \leq 10^9
  • |A_i| \leq R
  • \left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R
  • N, R, and A_i are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read N from Standard Input.

N

Next, repeat the interactions until the blackboard contains only one value \displaystyle\sum_{i=1}^{N}A_i.

When performing addition, make an output in the following format to Standard Output. Append a newline at the end. Here, i and j are distinct positive integers.

+ i j

The response from the judge will be given from Standard Input in the following format:

P

Here, P is an integer:

  • If P \geq N + 1, it means that the value X_i + X_j has been written on the blackboard, and it is the P-th integer written.
  • If P = -1, it means that i and j do not satisfy the constraints, or the number of interactions has exceeded 25000.

When performing comparison, make an output in the following format to Standard Output. Append a newline at the end. Here, i and j are distinct positive integers.

? i j

The response from the judge will be given from Standard Input in the following format:

Q

Here, Q is an integer:

  • If Q = 1, it means that X_i < X_j is true.
  • If Q = 0, it means that X_i < X_j is false.
  • If Q = -1, it means that i and j do not satisfy the constraints, or the number of interactions has exceeded 25000.

For both types of interactions, if the judge's response is -1, your program is already considered incorrect. In this case, terminate your program immediately.

When the blackboard contains only one value \displaystyle\sum_{i=1}^{N}A_i, report this to the judge in the following format. This does not count towards the number of interactions. Then, terminate your program immediately.

!

If you make an output in a format that does not match any of the above, -1 will be given from Standard Input.

-1

In this case, your program is already considered incorrect. Terminate your program immediately.

Notes

  • For each output, append a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
  • Terminate your program immediately after outputting the result (or receiving -1). Otherwise, the verdict will be indeterminate.
  • Extra newlines will be considered as malformed output.

Sample Input and Output

Here is a possible conversation with N=3, R=10, A_1=-1, A_2=10, A_3=1.

Input Output Explanation
3 First, the integer N is given.
? 1 2 Perform a comparison.
1 The judge returns 1 because X_1\lt X_2\ (-1\lt 10).
+ 1 3 Perform an addition.
4 The judge erases X_1 = -1 and X_3 = 1 from the blackboard and writes X_1 + X_3 = 0. This is the fourth integer written.
+ 2 4 Perform an addition.
5 The judge erases X_2 = 10 and X_4 = 0 from the blackboard and writes X_2 + X_4 = 10. This is the fifth integer written.
! The blackboard contains only one value \displaystyle\sum_{i=1}^{N}A_i, so report this to the judge.