← 返回题目列表

Codeforces · 727/C

C. 猜数组

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

这是一个交互问题。您应该在每打印一行之后使用刷新操作。例如,在 C++ 中,您应该使用 fflush(stdout),在 Java 中,您应该使用 System.out.flush(),而在 Pascal 中,您应该使用lush(output)。

在这个问题中,你应该猜测一个你未知的数组 a 。您最初拥有的唯一信息是数组 a 的长度 n。

唯一允许的操作是通过索引求两个元素的总和。正式地,您可以打印两个索引 i 和 j(索引应该不同)。然后你的程序应该读取响应:单个整数等于 ai + aj。

很容易证明,使用最多 n 个请求总是可以猜测数组。

编写一个程序,通过最多发出 n 个请求来猜测数组 a。

互动

在每个测试中,您的程序应该猜测一个数组。

输入以包含整数 n (3 ≤ n ≤ 5000) 的行开始——数组的长度。你的程序应该首先读取它。

之后,您的程序应将有关两个元素之和的请求打印到标准输出,或通知数组已被猜测。

- 如果您的程序请求两个元素的总和,它应该以“? i j”格式打印行(i 和 j 是 1 到 n 之间的不同整数),其中 i 和 j 是数组 a 中的索引。
- 如果你的程序通知数组被猜出,它应该以“! a1 a2 ... an”格式打印行(保证所有ai都是不超过105的正整数),其中ai是数组a的第i个元素。

请求的响应是一个等于 ai + aj 的整数,打印在单独的行上。

你的程序最多可以执行 n 个请求。请注意最后一行 «! a1 a2 ... an» 不计为请求。

不要忘记在每打印一行后进行刷新操作。

程序打印猜测的数组后,它应该正常终止。

示例

输入 #1

5
9
7
9
11
6

输出 #1

? 1 5
? 2 3
? 4 1
? 5 2
? 3 4
! 4 6 1 5 5

注意

进行黑客攻击的测试格式为:

- 第一行包含一个整数 n (3 ≤ n ≤ 5000) - 数组的长度。
- 第二行包含 n 个数字 a1, a2, ..., an (1 ≤ ai ≤ 105) - 要猜测的数组元素。