分数: 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 黑板上 按此顺序。你的任务是让黑板上只包含一个值 \displaystyle\sum_{i=1}^{N}A_i.
您无法了解以下值 R 和 A_i 直接,但您最多可以与评委互动 25000 次。
对于正整数 i,让 X_i 是 分别是 i- 第一个整数写在黑板上。具体来说, X_i = A_i 为 i=1,2,\dots,N.
在一次交互中,您可以指定两个不同的正整数 i 和 j 并选择以下操作之一:
- 执行加法。法官将抹去 X_i 和 X_j 从黑板上写下 X_i + X_j 。
- |X_i + X_j| \leq R 必须持有。
- 执行比较。法官会告诉你是否 X_i < X_j 是真是假。
在这里,在每次交互开始时, i-th 和 j黑板上写的第一个整数一定不能被擦除。
适当地执行交互,以便在所有交互之后,黑板仅包含一个值 \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
接下来,重复交互,直到黑板上只包含一个值 \displaystyle\sum_{i=1}^{N}A_i.
执行加法时,按以下格式输出到标准输出。在末尾添加换行符。在这里, i 和 j 是不同的正整数。
+ i j
裁判的响应将从标准输入中按以下格式给出:
P
在这里, P 是一个整数:
- If P \geq N + 1,这意味着该值 黑板上写着 X_i + X_j ,就是 P已写入第一个整数。
- If P = -1,这意味着 i 和 j 不满足约束,或者交互次数已超出 25000.
执行比较时,按以下格式输出到标准输出。在末尾添加换行符。在这里, i 和 j 是不同的正整数。
? i j
裁判的响应将从标准输入中按以下格式给出:
Q
在这里, Q 是一个整数:
- If Q = 1,这意味着 X_i < X_j 是真的。
- If Q = 0,这意味着 X_i < X_j 是错误的。
- If Q = -1,这意味着 i 和 j 不满足约束,或者交互次数已超出 25000.
对于这两种类型的互动,如果法官的反应是 -1,您的程序已被认为不正确。在这种情况下,请立即终止您的程序。
当黑板上仅包含一个值时 \displaystyle\sum_{i=1}^{N}A_i,按以下格式向法官报告。这不计入互动次数。然后,立即终止您的程序。
!
如果您的输出格式与上述任何格式都不匹配, -1 将从标准输入给出。
-1
在这种情况下,您的程序已被视为不正确。立即终止您的程序。
注释
- 对于每个输出,在末尾附加换行符并刷新标准输出。否则,判决可能是 TLE.
- 输出结果(或接收到结果)后立即终止程序
-1)。否则,判决将是不确定的。 - 额外的换行符将被视为格式错误的输出。
示例输入和输出
这是一个可能的对话 N=3, R=10, A_1=-1, A_2=10, A_3=1.
| 输入 | 输出 | 说明 |
|---|---|---|
3 |
一、整数 给出了 N 。 | |
? 1 2 |
进行比较。 | |
1 |
法官返回 1 因为 X_1\lt X_2\ (-1\lt 10). | |
+ 1 3 |
执行加法。 | |
4 |
法官删除 X_1 = -1 和 X_3 = 1 从黑板上写下 X_1 + X_3 = 0。这是写入的第四个整数。 | |
+ 2 4 |
执行加法。 | |
5 |
法官删除 X_2 = 10 和 X_4 = 0 从黑板上写下 X_2 + X_4 = 10。这是写入的第五个整数。 | |
! |
黑板上仅包含一个值 \displaystyle\sum_{i=1}^{N}A_i,所以向法官报告此事。 |