F. 猜数字游戏

内存限制:256 MiB 时间限制:2000 ms 题目类型:交互

题目描述

本题为交互题,请确保你已经完成了交互题测试或了解交互题怎么做,监考人员不会回答任何关于如何做交互题的问题。

​你准备玩一个猜数字游戏,给定一个 长的正整数数组,数组的元素对用户隐藏,你需要猜出的最大值,猜测规则如下:

​在游戏开始前,你拥有 个硬币;

​在开始猜测前,你需要支付 块的硬币以购买一个具有 面的骰子, 要求 。每次投掷该骰子,您将获得一个范围在的随机数,确保随机数服从均匀分布;

​每次猜测时,你需要指定一个正整数 )。程序将帮助你投掷骰子,倘若你获得随机数 ,那么程序将会返回子数组 的最大值。每次猜测都会消耗个硬币。每次猜测过后,程序将随机调整数组的元素位置

​当你的硬币数量小于 时,你不允许再次猜测,并输出你猜测到的数组的最大值。此外,你允许随时输出猜测到的最大值!当你猜测到的最大值与 的最大值相同时,你将获得游戏的胜利!

输入格式

第一行输入一个正整数 , 表示隐藏数组 的长度.

交互

要购买购买一个具有 面的骰子,按照如下格式输出一行(不包含引号)

"! m"

要进行猜测,请按照如下格式输出一行(不包含引号)

"? index"

表示你指定的下标索引, 注意要求 . 此时会输入一个正整数 , 表示子数组 的最大值, 表示程序生成的随机数.

要输出答案,请按照如下格式输出一行(不包括引号)

"! ans"

表示你猜到的数组的元素最大值.

若在任何时候输入的数为-1,说明你的询问超出次数/询问不合法/回答不合法/答案错误/其他输入错误,此时,你需要直接退出程序,接收到Wrong Answer。否则,你可能会得到任意一种错误类型作为回应

输出询问或回答后,不要忘记输出换行并刷新缓存区。否则,您可能会收到 Time limit exceeded 判定。为此,请使用:

在 C++ 中 fflush(stdout)或 cout.flush()

在 Java 中 System.out.flush()

在 Pascal 中 flush(output)

在 Python 中 stdout.flush()

对于其他语言,请参阅其他语言的文档。

交互器是自适应的,在每一次猜测操作后,交互器都会重新调整隐藏数组 的元素位置。

样例

// 后面的内容仅代表解释

输入 #1

4	//	隐藏数组的长度
5	//	第一次回答

输出 #1

! 4		//	购买一个具有 4 面的骰子
? 1		//	第一次操作,指定索引为1.
! 5		//	答案正确

​ 隐藏的数组, 第一次操作程序生成的随机数 , 返回子数组 的最大值.

输入 #2

5 	//	隐藏数组的长度
2	//	第一次回答
6	//	第二次回答

输出 #2

! 2		//	购买一个具有 2 面的骰子
? 1		//	第一次操作,指定索引为1
? 2		//	第二次操作,指定索引为2
! 6		//	答案正确

​ 隐藏的数组 ,第一次操作程序生成的随机数 ,返回子数组 的最大值 ;在第一次操作后,隐藏数组调整元素的位置,新的隐藏数组 。第二次操作程序生成的随机数 ,返回子数组 的最大值

注意,上述操作并非代表最优操作,仅仅作为操作的演示。

数据范围与提示

​ 确保 , 允许 数组元素出现重复.