本题与困难版的唯一区别是最大题数。
这是一个交互问题。
有一个隐藏的整数 $$$1 \le x \le n$$$ 你必须找到它。为了找到它,您最多可以提出 $$$\mathbf{53}$$$ 问题。
在每个问题中,您可以选择一个非空整数集合$$$S$$$,并询问$$$x$$$是否属于$$$S$$$,在每个问题之后,如果$$$x$$$属于$$$S$$$,您将收到“YES”,否则“NO”。
但问题是,并不是所有的答案都一定是真的(有些是开玩笑的),只是保证每两个连续的问题,至少有一个回答正确。
除了问题之外,您最多可以对答案 $$$x$$$ 进行 $$$2$$$ 猜测。每次你进行猜测时,如果你猜对了 $$$x$$$,你会收到“:)”并且你的程序应该终止,否则你会收到“:(”。
作为开玩笑的一部分,我们不会一开始就固定 $$$x$$$ 的值。相反,只要之前的所有响应都有效,如上所述,它就可以在整个交互过程中发生变化。
请注意,您的答案猜测总是正确的。如果您在猜测之前和之后提出问题,那么按照正常情况,这两个问题中至少有一个会被正确回答。
输入
输入的唯一行包含单个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即 $$$x$$$ 的最大可能值。
互动
对于每一个问题,如果你想询问一个集合$$$S$$$,首先打印字符'?',然后打印$$$S$$$的大小,然后逐个打印$$$S$$$的元素。每个元素应该是 $$$1$$$ 和 $$$n$$$ 之间的整数,元素必须不同。在每个问题之后,阅读字符串“是”或“否”,如声明中所述。您最多可以提出 $$$53$$$ 这样的问题。
如果你想猜测 $$$x$$$,首先打印字符 '!'然后打印你的猜测。每次猜测后,读“:)”或“:(”。如果你猜对$$$x$$$,答案是“:)”,你的程序应该立即终止,否则你会收到“:(”。你最多可以做出$$$2$$$这样的猜测。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
此问题不允许进行黑客攻击。
示例
输入 #1
6 NO :( NO :)
输出 #1
? 5 1 2 5 4 3 ! 6 ? 4 1 2 3 4 ! 5
注意
如果第一个问题的答案是正确的,那么 $$$x$$$ 将等于 $$$6$$$,但正如我们在第一个猜测中看到的,$$$6$$$ 不是答案。
所以第一个问题的答案就是开玩笑。众所周知,我们两个问题中至少有一个的答案是正确的,既然第一个问题的答案是开玩笑,那么第二个问题的答案应该是正确的。
所以我们会明白 $$$x$$$ 不等于 $$$1, 2, 3$$$ 或 $$$4$$$,并且我们也知道 $$$x$$$ 也不等于 $$$6$$$。因此$$$x$$$应该等于$$$5$$$。