这是一个交互问题。
为了防止顽皮的兔子在动物园里随意闲逛,动物园管理员为兔子围栏设置了一把特殊的锁。这种锁称为旋转激光锁。
该锁由 $$$n$$$ 同心环组成,编号从 $$$0$$$ 到 $$$n-1$$$。最内环是环$$$0$$$,最外环是环$$$n-1$$$。所有环均等分为 $$$nm$$$ 部分。每个环都包含一个金属弧,恰好覆盖 $$$m$$$ 连续部分。环的中心是一个核心,整个锁周围是与 $$$nm$$$ 部分对齐的 $$$nm$$$ 接收器。
核心有 $$$nm$$$ 激光,从中心向外照射,每个部分一个。激光可以被任何电弧阻挡。锁外部的显示屏显示有多少激光击中外部接收器。
在上面的示例中,有 $$$n=3$$$ 个环,每个环覆盖 $$$m=4$$$ 部分。电弧颜色为绿色(环 $$$0$$$)、紫色(环 $$$1$$$)和蓝色(环 $$$2$$$),而激光束显示为红色。有 $$$nm=12$$$ 部分,$$$3$$$ 激光没有被任何电弧阻挡,因此在这种情况下显示屏将显示 $$$3$$$。
兔兔试图打开锁来释放兔子,但锁完全不透明,他看不到任何弧线在哪里。考虑到弧线的相对位置,瓦比特可以自己打开锁。
准确地说,Wabbit 需要 $$$n-1$$$ 整数 $$$p_1,p_2,\ldots,p_{n-1}$$$ 满足 $$$0 \leq p_i < nm$$$,这样对于每个 $$$i$$$ $$$(1 \leq i < n)$$$,Wabbit 可以精确地顺时针旋转圆环 $$$0$$$ $$$p_i$$$ 次,使得 $$$0$$$ 覆盖的部分与 $$$i$$$ 覆盖的部分完全对齐。在上面的示例中,相对位置为 $$$p_1 = 1$$$ 和 $$$p_2 = 7$$$。
要操作锁,他可以拾取任何 $$$n$$$ 环并将其顺时针或逆时针旋转 $$$1$$$ 部分。每次旋转后您都会在显示屏上看到数字。
因为他的爪子很小,所以在完成所有旋转后,Wabbit 要求你帮助他找到弧线的相对位置。在 Wabbit 不耐烦之前,您最多可以执行 $$$15000$$$ 轮换。
输入
第一行由 2 个整数 $$$n$$$ 和 $$$m$$$ $$$(2 \leq n \leq 100, 2 \leq m \leq 20)$$$ 组成,表示环的数量以及每个环覆盖的节数。
互动
要执行旋转,请在单行上打印“? x d”,其中 $$$x$$$ $$$(0 \leq x < n)$$$ 是您要旋转的环,$$$d$$$ $$$(d \in \{-1,1\})$$$ 是您要旋转的方向。$$$d=1$$$ 表示顺时针旋转$$$1$$$ 部分而$$$d=-1$$$ 表示按$$$1$$$ 部分逆时针旋转。
对于每个查询,您将收到一个整数 $$$a$$$:执行旋转后未被任何弧阻挡的激光数量。
找出弧的相对位置后,打印!后面跟着 $$$n-1$$$ 整数 $$$p_1, p_2, \ldots, p_{n-1}$$$。
请注意,环的位置是为每个测试用例预先确定的,并且在交互过程中不会改变。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将得到超出空闲限制的判决。
为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客:
要破解,请使用以下测试格式:
第一行应包含两个整数 $$$n$$$ 和 $$$m$$$。
的下一行应包含 $$$n-1$$$ 整数 $$$p_1,p_2,\ldots,p_{n-1}$$$:环 $$$1,2,\ldots,n-1$$$ 的相对位置。
示例
输入 #1
3 4 4 4 3
输出 #1
? 0 1 ? 2 -1 ? 1 1 ! 1 5
注意
对于第一次测试,配置与声明中的图片所示相同。
第一次旋转后(即顺时针旋转环 $$$0$$$ $$$1$$$ 部分),我们获得以下配置:
第二次旋转后(即逆时针旋转$$$2$$$环$$$1$$$部分),我们获得以下配置:
第三次旋转后(即顺时针旋转$$$1$$$环$$$1$$$部分),我们获得以下配置:
如果我们顺时针旋转环$$$0$$$一次,我们可以看到环$$$0$$$覆盖的部分将与环$$$1$$$覆盖的部分相同,因此$$$p_1=1$$$。
如果我们顺时针旋转环$$$0$$$五次,环$$$0$$$覆盖的部分将与环$$$2$$$覆盖的部分相同,因此$$$p_2=5$$$。
请注意,如果我们进行一组不同的旋转,则最终可能会得到不同的 $$$p_1$$$ 和 $$$p_2$$$ 值。