这是一个交互问题。请记住在与测试程序通信时刷新输出。您可以在 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”,因为确信该城市不存在问题中所需的两栋房屋。