这是一个交互问题。
给你一个按升序排序的单链表。您应该找到列表中大于或等于 x 的最小整数。
更正式地说,有一个基于 n 个元素的数组构建的单一喜欢列表。索引为 i 的元素包含两个整数:valuei 是该元素中的整数值,nexti 是单向链表的下一个元素的索引(如果当前元素是最后一个元素,则为 -1)。该列表已排序,即如果 nexti ≠ - 1,则 valuenexti > valuei。
给定列表中的元素数量 n、第一个元素开始的索引以及整数 x。
您最多可以进行 2000 个以下两种类型的查询:
- ? i (1 ≤ i ≤ n) - 询问 valuei 和 nexti 的值,
- ! ans — 给出问题的答案:大于或等于 x 的最小整数,或者! -1,如果没有这样的整数。您的程序应该在该查询之后终止。
编写一个程序来解决这个问题。
输入
第一行包含三个整数 n、start、x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 109) - 列表中元素的数量、第一个元素的索引和整数 x。
互动
要进行第一种类型的查询,请打印 ? i (1 ≤ i ≤ n),其中 i 是您想要了解其信息的元素的索引。
在每次查询类型 ?读取两个整数 valuei 和 nexti (0 ≤ valuei ≤ 109, - 1 ≤ nexti ≤ n, nexti ≠ 0)。
保证如果 nexti ≠ - 1,则 valuenexti > valuei,并且数组值给出一个有效的单链表,其中 start 是第一个元素。
请注意,您不能询问超过 1999 个 ? 类型的查询。
如果 nexti = - 1 且 valuei = - 1,则意味着您提出的查询数量超出了允许的数量,或者提出了无效查询。您的程序应立即终止(例如,通过调用 exit(0))。您将收到“错误答案”,这意味着您提出的查询超出了允许的范围,或者提出了无效的查询。如果您忽略这一点,您可以获得其他结论,因为您的程序将继续从关闭的流中读取。
如果您不打印任何内容或忘记刷新输出(包括最终答案),您的解决方案将得到“超出空闲限制”。
要刷新,您可以使用(在打印查询和行结束后):
- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 对于其他语言,请参阅文档。
黑客格式
对于 hack,请使用以下格式:
在第一行打印三个整数 n, start, x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 109)。
在接下来的 n 行中打印列表元素的描述:在第 i 行中打印两个整数 valuei 和 nexti (0 ≤ valuei ≤ 109, - 1 ≤ nexti ≤ n, nexti ≠ 0)。
打印的结构应该是有效的单链表。特别是,应该可以通过链接 nexti 从 start 到达所有元素,并且最后一个元素 end 的 nextend 中应该有 -1。
输出
要打印问题的答案,请打印! ans,其中 ans 是列表中大于或等于 x 的最小整数,如果没有这样的整数,则为 -1。
示例
输入 #1
5 3 80 97 -1 58 5 16 2 81 1 79 4
输出 #1
? 1 ? 2 ? 3 ? 4 ? 5 ! 81
注意
您可以通过以下链接阅读有关单链表的更多信息:https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list
第一个示例案例的插图。开始和结束元素标记为黑色。