← 返回题目列表

Codeforces · 1498/E

E. 两栋房子

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

这是一个交互问题。请记住在与测试程序通信时刷新输出。您可以在 C++ 中使用 fflush(stdout)、Java 中的 system.out.flush()、Python 中的 stdout.flush() 或 Pascal 中的lush(output) 来刷新输出。如果您使用其他编程语言,请查阅其文档。您还可以参考交互问题指南:https://codeforces.com/blog/entry/45307。

迪克西特居住在一座城市。在城市里,有$$$n$$$ 的房子。每对房屋之间都有一条有向的道路。例如,考虑两栋房屋 A 和 B,则存在一条从 A 到 B 或从 B 到 A 的有向道路,但不能同时存在。通往第 $$$i$$$ 号房屋的道路数量为 $$$k_i$$$。

如果 A 从 B 可达并且 B 从 A 可达,则两栋房屋 A 和 B 是双向可达的。当存在从房屋 A 到房屋 B 的路径时,我们说房屋 B 从房屋 A 可达。

迪克西特想在城里买两套房子,一套住,一套学习。当然,他想从一所房子到另一所房子旅行。因此,他想找到一对双向可达的房屋 A 和 B。在所有这些房屋对中,他想选择价值 $$$|k_A - k_B|$$$ 最大值的房屋,其中 $$$k_i$$$ 是通往房屋 $$$i$$$ 的道路数量。如果存在多个最佳对,则其中任何一个都是合适的。

由于 Dixit 正忙着准备 CodeCraft,你能帮他找到想要的一对房子,或者告诉他不存在这样的房子吗?

在问题输入中,没有给出每条路的方向。对于每个房屋,您仅获得通往该房屋的传入道路数量 ($$$k_i$$$)。

你只能向法官提出一种类型的查询:给出两栋房屋A和B,法官回答从A是否可以到达B。查询数量没有上限。但是,在法官对您的任何疑问回答“是”后,您不能再提出更多疑问。此外,您不能两次询问同一查询。

一旦您用尽所有查询(或者法官对您的任何查询回答“是”),您的程序必须输出对两座房子的猜测并退出。

有关更多详细信息,请参阅下面的交互部分。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 500$$$) 表示城市中的房屋数量。下一行包含 $$$n$$$ 空格分隔的整数 $$$k_1, k_2, \dots, k_n$$$ ($$$0 \le k_i \le n - 1$$$),其中第 $$$i$$$ 表示通往第 $$$i$$$ 号房屋的传入道路数量。

互动

要提出查询,请打印“? A B”$$$(1 \leq A,B \leq N, A\neq B)$$$。如果从 A 屋可以到达 B 屋,法官将回答“是”,否则回答“否”。

要输出最终答案,请打印“! A B”,其中 A 和 B 是双向可达的,最大可能值为 $$$|k_A - k_B|$$$。如果不存在这样的一对房屋A和B,则输出“!0 0”。

输出最终答案后,你的程序必须立即终止,否则你将收到错误答案的判决。

您不能两次询问同一查询。您提出的问题数量没有上限,但是,在法官对您的任何问题回答“是”后,您不能再提出更多问题。您的程序现在必须输出最终答案(“!A B”或“!0 0”)并终止。

如果您以不正确的格式提出查询或重复之前的查询,您将得到错误答案判决。

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

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

示例

输入 #1

3
1 1 1
Yes

输出 #1

? 1 2
! 1 2

输入 #2

4
1 2 0 3
No
No
No
No
No
No

输出 #2

? 2 1
? 1 3
? 4 1
? 2 3
? 4 2
? 4 3
! 0 0

注意

在第一个示例输入中,我们得到一个由三栋房屋组成的城市,每栋房屋都有一条传入道路。用户程序提出一个查询:“? 1 2”:询问我们是否可以从房子$$$1$$$到达房子$$$2$$$。法官回答“是”。用户程序现在得出结论,这些信息足以确定正确答案。因此,它输出“!1 2”并退出。

在第二个示例输入中,用户程序查询六对不同的房屋,最后回答“!0 0”,因为确信该城市不存在问题中所需的两栋房屋。