← 返回题目列表

Codeforces · 1847/E

E. 三角白金?

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

这是一个交互问题。

Made in Heaven 是一个相当奇怪的展位。当然,它(可以说)是现存最强大的替身,但它也是一个热心的解谜爱好者。比如最近给Qtaro带来了如下问题:

Made in Heaven 有 $$$n$$$ 隐藏整数 $$$a_1, a_2, \dots, a_n$$$ ($$$3 \le n \le 5000$$$, $$$1 \le a_i \le 4$$$)。 Qtaro 必须通过向 Made in Heaven 询问以下形式的一些查询来确定所有 $$$a_i$$$:

- 在一个查询中,Qtaro 可以为 Made in Heaven 提供三个不同的索引 $$$i$$$、$$$j$$$ 和 $$$k$$$ ($$$1 \leq i, j, k \leq n$$$)。
- 如果 $$$a_i, a_j, a_k$$$ 形成非退化三角形 $$$^\dagger$$$ 的边,Made in Heaven 将用该三角形的面积进行响应。
- 否则,Made in Heaven 将响应 $$$0$$$。

通过询问最多 $$$5500$$$ 这样的问题,Qtaro 必须要么告诉 Made in Heaven $$$a_i$$$ 的所有值,要么报告不可能唯一地确定它们。

不幸的是,由于宇宙重启,Qtaro 不如承太郎聪明。请帮助 Qtaro 解决 Made In Heaven 的问题。

——————————————————————

$$$^\dagger$$$ 当且仅当以下三个不等式全部成立时,三个正整数 $$$a, b, c$$$ 被认为形成非退化三角形的边:

- $$$a+b > c$$$,
- $$$b+c > a$$$,
- $$$c+a > b$$$。

互动

交互从读取 $$$n$$$ ($$$3 \le n \le 5000$$$) 开始,即隐藏整数的数量。

要提出与三元组$$$(i, j, k)$$$ ($$$1 \leq i < j < k \leq n$$$)相对应的问题,请输出“? $$$i$$$ $$$j$$$ $$$k$$$”,不带引号。之后,您应该读取单个整数 $$$s$$$。

- 如果 $$$s = 0$$$,则 $$$a_i$$$、$$$a_j$$$ 和 $$$a_k$$$ 不是非退化三角形的边。
- 否则,$$$s = 16 \Delta^2$$$,其中 $$$\Delta$$$ 是三角形的面积。为了方便起见,以这种格式提供区域,因此您只需输入整数即可。

如果数字 $$$a_i$$$ 无法唯一确定,则打印“! $$$-1$$$”(不带引号)。另一方面,如果您已经确定了 $$$a_i$$$ 的所有值,则在一行上打印“! $$$a_1$$$ $$$a_2$$$ $$$\dots$$$ $$$a_n$$$”。

交互器是非自适应的。隐藏数组$$$a_1,a_2,\dots,a_n$$$是预先固定的,在交互过程中不会改变。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

您可以使用以下输入格式破解解决方案。

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5000$$$) — 隐藏整数的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 4$$$) — 隐藏数组。

示例

输入 #1

3

63

输出 #1

? 1 2 3

! -1

输入 #2

6

0

0

0

63

15

135

输出 #2

? 1 2 3

? 2 3 4

? 4 5 6

? 1 5 6

? 3 5 6

? 1 2 4

! 3 2 1 4 2 2

输入 #3

15

3

3

3

3

3

0

输出 #3

? 1 2 3

? 4 6 7

? 8 9 10

? 11 12 13

? 13 14 15

? 4 5 6

! -1

输入#4

15

3

15

0

3

3

3

输出#4

? 1 2 3

? 3 4 5

? 4 5 6

? 7 8 9

? 10 11 12

? 13 14 15

! 1 1 1 2 2 4 1 1 1 1 1 1 1 1 1 1

输入 #5

10

3

48

3

48

63

0

输出 #5

? 1 3 5

? 4 6 8

? 1 5 9

? 6 8 10

? 4 2 6

? 7 10 8

! 1 3 1 2 1 2 4 2 1 2

注意

在第一个示例中,交互过程如下:

StdinStdoutExplanation3Read $$$n = 3$$$。有 $$$3$$$ 隐藏整数? 1 2 3求 $$$a_1$$$、$$$a_2$$$ 和 $$$a_3$$$63 所形成的面积 $$$16\Delta^2 = 63$$$。所以面积 $$$\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$$$! -1回答没有唯一的数组满足查询。

从收到的面积,我们可以推断出形成三角形的数字是($$$4$$$,$$$4$$$,$$$1$$$)或($$$3$$$,$$$2$$$,$$$2$$$)(按某种顺序)。由于存在多个满足查询的数字数组,因此无法找到唯一的答案。

在第二个示例中,交互过程如下:

StepStdinStdoutExplanation16读取$$$n = 6$$$。有 $$$6$$$ 隐藏整数2? 1 2 3求$$$a_1$$$、$$$a_2$$$和$$$a_3$$$构成的面积30不构成非退化三角形4? 2 3 4求$$$a_2$$$、$$$a_3$$$和$$$a_4$$$50形成的面积不构成非退化三角形6吗? 4 5 6求$$$a_4$$$、$$$a_5$$$和$$$a_6$$$70构成的面积不构成非退化三角形8吗? 1 5 6求 $$$a_1$$$、$$$a_5$$$ 和 $$$a_6$$$963 形成的面积 $$$16\Delta^2 = 63$$$。那么面积 $$$\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$$$10 ? 3 5 6求$$$a_3$$$、$$$a_5$$$和$$$a_6$$$形成的面积1115收到$$$16\Delta^2 = 15$$$。那么面积 $$$\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$$$12 ? 1 2 4求$$$a_3$$$、$$$a_5$$$和$$$a_6$$$形成的面积13135收到$$$16\Delta^2 = 135$$$。所以面积 $$$\Delta = \sqrt{\frac{135}{16}} \approx 2.904738$$$14! 3 2 1 4 2 2找到一个唯一答案,即$$$a = [3, 2, 1, 4, 2, 2]$$$。

从步骤$$$10$$$和$$$11$$$,我们可以推断多重集$$$\left\{a_3, a_5, a_6\right\}$$$一定是$$$\left\{2, 2, 1\right\}$$$。

从步骤 $$$8$$$ 和 $$$9$$$ 开始,多重集 $$$\left\{a_1, a_5, a_6\right\}$$$ 必须是 $$$\left\{4, 4, 1\right\}$$$ 或 $$$\left\{3, 2, 2\right\}$$$。

由于 $$$\left\{a_3, a_5, a_6\right\}$$$ 和 $$$\left\{a_1, a_5, a_6\right\}$$$ 共享 $$$a_5$$$ 和 $$$a_6$$$,我们得出结论 $$$a_5 = a_6 = 2$$$,以及 $$$a_1 = 3$$$,$$$a_3 = 1$$$。

从步骤$$$6$$$和$$$7$$$,我们知道$$$a_5 = a_6 = 2$$$,并且$$$a_4$$$、$$$a_5$$$和$$$a_6$$$不能形成非退化三角形,因此$$$a_4 = 4$$$。

在所有已知信息下,只有 $$$a_2 = 2$$$ 满足步骤 $$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$12$$$ 和 $$$13$$$ 中进行的查询。

在第三个示例中,满足查询的一个数组是$$$[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$$$。