这是一个交互问题。
约翰和他想象中的朋友玩游戏。有 $$$n$$$ 灯排列成一圈。灯按顺时针顺序从 $$$1$$$ 到 $$$n$$$ 编号,也就是说,对于任何 $$$i = 1、\ldots、n - 1$$$,灯 $$$i$$$ 和 $$$i + 1$$$ 是相邻的,并且灯 $$$n$$$ 和 $$$1$$$ 也是相邻的。最初所有灯都关闭。
约翰和他的朋友轮流行动,约翰先行动。轮到约翰时,他可以选择终止游戏或采取行动。要采取行动,约翰可以选择任何正数 $$$k$$$ 并打开他选择的任何 $$$k$$$ 灯。为了响应这一移动,约翰的朋友将选择 $$$k$$$ 个连续的灯并将它们全部关闭(在该移动之前关闭的范围内的灯将保持关闭状态)。请注意,$$$k$$$ 的值与约翰最后一步的数字相同。例如,如果 $$$n = 5$$$ 并且 John 刚刚打开了三盏灯,John 的朋友可以选择关闭灯 $$$1, 2, 3$$$,或 $$$2, 3, 4$$$,或 $$$3, 4, 5$$$,或 $$$4, 5, 1$$$,或 $$$5, 1, 2$$$。
此后,John 可以选择终止或再次移动,依此类推。然而,约翰的移动次数不能超过 $$$10^4$$$。
约翰想要最大化游戏结束时打开的灯的数量,而他的朋友想要最小化这个数量。您的任务是为约翰提供实现最佳结果的策略。您的程序将为约翰交互播放,而陪审团的交互程序将为约翰的朋友播放。
假设游戏中有 $$$n$$$ 盏灯。令 $$$R(n)$$$ 为游戏结束时如果双方都采取最佳行动时打开的灯的数量。您的程序必须在 $$$10^4$$$ 步内至少打开 $$$R(n)$$$ 灯来终止游戏。有关交互详细信息,请参阅下面的交互部分。
由于技术原因,针对此问题的黑客攻击已被禁用。
互动
最初,您的程序将被输入一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$)——游戏中灯的数量。然后交互器将等待您的操作。
要进行移动,请打印一行,以整数 $$$k$$$ ($$$1 \leq k \leq n$$$) 开头,后跟 $$$k$$$ 不同的整数 $$$l_1, \ldots, l_k$$$ ($$$1 \leq l_i \leq n$$$) — 您要打开的灯的索引。索引可以按任何顺序打印。允许尝试打开已经打开的灯(尽管这不会产生任何效果)。
如果您的移动因任何原因无效,或者您的移动次数超过 $$$10^4$$$,则交互器将回复包含单个整数 $$$-1$$$ 的行。否则,回复将是包含单个整数 $$$x$$$ ($$$1 \leq x \leq n)$$$ 的行,这意味着响应是按顺时针顺序关闭从 $$$x$$$ 开始的 $$$k$$$ 连续灯。
要终止游戏而不是进行移动,请打印包含单个整数 $$$0$$$ 的行。如果此时至少有 $$$R(n)$$$ 灯打开,则测试将通过(请注意,$$$R(n)$$$ 和收到的判决都不会以任何方式传达给您的程序)。此操作不计入移动次数(也就是说,在 $$$10^4$$$ 移动之后终止游戏是合法的)。
要收到正确的判决,您的程序应在打印 $$$0$$$ 后或收到 $$$-1$$$ 作为响应后立即终止。
不要忘记在每次操作后刷新你的输出。
示例
输入 #1
3
输出 #1
0
输入 #2
4 1
输出 #2
2 1 3 0
注意
当$$$n = 3$$$时,约翰的任何一步都可以逆转,因此$$$R(3) = 0$$$,立即终止游戏是正确的。
$$$R(4) = 1$$$,第二个示例案例中显示了实现此结果的一种策略。
示例交互中的空行是为了清晰起见,不应打印。