← 返回题目列表

AtCoder · arc179_c

C. 小心溢出

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

分数: 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,所以向法官报告此事。