这是一个交互问题。
您将获得 $$$n$$$ 个框,索引从 $$$1$$$ 到 $$$n$$$。这些盒子看起来相同,但每个盒子都有一个隐藏的功率值 $$$a_i$$$,即 $$$1$$$ 或 $$$2$$$。
您想要确定每个框的功率值。为此,您需要进行以下实验。最初,第 $$$i$$$ 个盒子放置在数轴上的坐标 $$$i$$$ 处 ($$$1 \le i \le n$$$)。
您可以执行以下两种类型的查询:
- "交换$$$x$$$" ($$$1 \le x \le n - 1$$$): 交换当前位于的框 坐标 $$$x$$$ 和 $$$x + 1$$$。请注意,此更改是永久性的,并且会影响所有后续查询。
- "扔$$$x$$$" ($$$1 \le x \le n$$$):向位于以下位置的盒子扔一个球 坐标 $$$x$$$。如果盒子的能量值为 $$$p$$$,则球向前移动 $$$p$$$ 单位以坐标 $$$x + p$$$。如果新坐标处有一个盒子,球会利用该盒子的力量再次跳跃。这一直持续到球落在没有盒子的坐标上。作为响应,您将获得球在停止之前跳跃的总次数。
您的任务是使用总共不超过 $$$\left\lceil \frac{3n}{2} \right\rceil$$$ 查询来确定每个框的功率值,同时计算两个 交换 和 扔 查询。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 盒子的数量。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
互动
每个测试用例的交互从读取整数 $$$n$$$ 开始。
要进行查询,请按以下格式之一输出一行:
- "交换$$$x$$$" (不带引号) ($$$1 \le x \le n - 1$$$): 交换当前位于的框 坐标 $$$x$$$ 和 $$$x + 1$$$。
- "扔$$$x$$$" (不带引号) ($$$1 \le x \le n$$$): 将球扔到位于 坐标 $$$x$$$。陪审团将用一个整数来响应,该整数表示球在停止之前跳跃的次数。
请注意,查询是 区分大小写.
确定每个框的功率值后,按以下格式输出一行:
- "! $$$a_1 \空间 a_2 \空间 \ldots \空间 a_n$$$"(不带引号):这里,$$$a_i$$$ 是盒子的功率值 最初位于 at 坐标 $$$i$$$ ($$$1 \le i \le n$$$)。提交最终答案后,继续下一个测试用例。
请注意,提交上一个查询的最终答案不会 不 计入 $$$\left\lceil \frac{3n}{2} \right\rceil$$$ 查询限制。
如果您的程序在一个测试用例中超过 $$$\left\lceil \frac{3n}{2} \right\rceil$$$ 查询,则您的程序必须立即终止才能接收判决 错误答案。否则,它可能会收到任何其他判决。
输出查询后,不要忘记输出行尾并刷新输出。否则,你会得到 超出空闲限制。为此,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
- System.out.flush() ;
- sys.stdout.flush() 在 Python 中;
- std::io::stdout().flush() 在 Rust 中;
- 请参阅其他语言的文档。
交互器是 非自适应;盒子的功率值在整个交互过程中保持恒定。
黑客
要破解,请使用以下格式。
第一行应包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$) — 盒子的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2$$$) — 每个框的功效值。
所有测试用例的 $$$n$$$ 总和不应超过 $$$1000$$$。
示例
输入复制
2 4 2 3 3 2 2 1
输出复制
throw 2 swap 3 throw 2 throw 1 ! 2 1 2 1 throw 1 swap 1 throw 1 ! 1 2
注意
示例中的交互过程如下:
| 解决方案 | 评审团 | 说明 |
| 2 | 有 $$$2$$$ 测试用例。 | |
| 4 | 第一个测试用例中有 $$$4$$$ 框。隐藏能力值为 $$$a = [2,1,2,1]$$$。 | |
| 扔 2 | 2 | 向坐标 $$$2$$$ 处的盒子扔一个球。球经过坐标 $$$2 \to 3 \to 5$$$ 并停在坐标 $$$5$$$ 处,因此响应为 $$$2$$$。 |
| 交换 3 | 交换位于坐标 $$$3$$$ 和 $$$4$$$ 处的框。现在框 $$$3$$$ 位于坐标 $$$4$$$ 处,框 $$$4$$$ 位于坐标 $$$3$$$ 处。 | |
| 扔 2 | 3 | 向坐标 $$$2$$$ 处的盒子扔一个球。球经过坐标 $$$2 \to 3 \to 4 \to 6$$$ 并停在坐标 $$$6$$$ 处,因此响应为 $$$3$$$。请注意,由于交换,响应有所不同。 |
| 扔 1 | 3 | 向坐标 $$$1$$$ 处的盒子扔一个球。球经过坐标 $$$1 \to 3 \to 4 \to 6$$$ 并停在坐标 $$$6$$$ 处,因此响应为 $$$3$$$。 |
| ! 2 1 2 1 | 该解决方案得出的结论是功率值为 $$$[2,1,2,1]$$$。 | |
| 2 | 第二个测试用例中有 $$$2$$$ 个框。隐藏能力值为 $$$a = [1, 2]$$$。 | |
| 扔 1 | 2 | 向坐标 $$$1$$$ 处的盒子扔一个球。球经过坐标 $$$1 \to 2 \to 4$$$ 并停在坐标 $$$4$$$ 处,因此响应为 $$$2$$$。 |
| 交换1 | 交换位于坐标 $$$1$$$ 和 $$$2$$$ 处的框。现在框 $$$1$$$ 位于坐标 $$$2$$$ 处,框 $$$2$$$ 位于坐标 $$$1$$$ 处。 | |
| 扔 1 | 1 | 向坐标 $$$1$$$ 处的盒子扔一个球。球穿过坐标 $$$1 \to 3$$$ 并停在坐标 $$$3$$$ 处,因此响应为 $$$1$$$。 |
| ! 1 2 | 该解决方案得出的结论是功率值为 $$$[1,2]$$$。 |
示例输入和输出中的空行只是为了更好的可读性;您不需要在解决方案中输出它们。
请注意,在第一个测试用例中,给定的查询实际上不足以唯一地确定功率值;它们仅用于说明输入/输出格式。