← 返回题目列表

Codeforces · 2159/F

F. 大结局:蛇

中文机器翻译题面 查看原题

这是一个交互问题。

给你一个整数 $$$n$$$ 和一个 $$$n\times n$$$ 数字 $$$G$$$ 网格。数字网格包含从 $$$1$$$ 到 $$$n^2$$$ 的每个数字恰好一次。

让我们定义一个 蛇 长度为 $$$l$$$ 作为双端队列 $$$[(x_1,y_1), (x_2,y_2), \ldots, (x_l,y_l)]$$$,其中 $$$(x_1,y_1)$$$ 是蛇的头,$$$(x_l,y_l)$$$ 是蛇尾。在第二个 $$$1$$$ 处,$$$x_1=x_2=\ldots = x_l=1$$$ 和 $$$y_i=i$$$ 对于所有 $$$1 \leq i \leq l$$$。换句话说,蛇完全位于第一行,头部位于$$$(1,1)$$$,而蛇的其余部分位于头部的右侧。

随后的每一秒,蛇都会在网格中向下或向右移动。形式上,尾部 $$$(x_l,y_l)$$$ 被删除,并且 $$$(x_1+1,y_1)$$$ 或 $$$(x_1,y_1+1)$$$ 添加为新头。 蛇的第一步总是向下。 可以证明,在这些限制下,蛇永远不会与自身相交。蛇将精确移动 $$$2n-2$$$ 次,并且永远不会移出网格。在第 $$$2n-1$$$ 处,头部到达 $$$(n,n)$$$,并且运动停止。可以证明,蛇向右移动了 $$$n-1$$$ 次,向下移动了 $$$n-1$$$ 次。

有 $$$n$$$ 条隐藏的蛇,第 $$$i$$$ 条蛇的长度为 $$$i$$$ 为 $$$1 \leq i \leq n$$$,每条蛇根据上述规则独立移动。你不知道蛇是如何移动的。定义 $$$f(l,T)$$$ 为长度为 $$$l$$$ 的蛇在第二个 $$$T$$$ 所覆盖的最大数量。

长度为 $$$l=3$$$ 的蛇的示例。

现在,您还获得了一个整数 $$$m$$$。您的任务是找到 $$$f(l,T)$$$ 的 $$$m$$$ 最小值,最多使用 $$$120n+m$$$ 查询来询问 $$$f(l,T)$$$ 的值,对于 $$$1 \leq l \leq n$$$ 和 $$$1 \leq T \leq 2n-1$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 500, 1 \leq m \leq n(2n-1)$$$)。

以下 $$$n$$$ 行包含网格 $$$G$$$。这些行的第 $$$i$$$ 包含 $$$n$$$ 整数 $$$G_{i,1}, G_{i,2}, \ldots, G_{i,n}$$$ ($$$1 \leq G_{i,j} \leq n^2$$$)。

保证 $$$G$$$ 包含从 $$$1$$$ 到 $$$n^2$$$ 的每个数字恰好一次。

保证所有测试用例的$$$n$$$总和不超过$$$500$$$,所有测试用例的$$$m$$$总和不超过$$$5\cdot 10^4$$$。

阅读 $$$n+1$$$ 行输入后,交互将从您的第一个查询开始。

互动

要进行查询,请按以下格式输出一行(不带引号):

  • "? $$$l\;T$$$" ($$$1 \leq l \leq n$$$, $$$1 \leq T \leq 2n-1$$$)。

每次查询后,读入一个整数 – $$$f(l,T)$$$ 的值。您最多可以提出 $$$120n+m$$$ 此类查询。

当您准备好输出答案时,请按以下格式打印一行:

  • "! $$$S_1\;S_2\;S_3\;\ldots\;S_m$$$" ($$$1 \leq S_1 \leq S_2 \leq \ldots \leq S_m$$$)。

这应该包含按非降序排列的 $$$f(l,T)$$$ 的 $$$m$$$ 最小值。请注意,这不计入查询限制。

此后,继续进行下一个测试用例,如果这是最后一个测试用例,则退出。

如果您在交互过程中进行超过 $$$120n+m$$$ 查询,您的程序必须立即终止,并且您将收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印每一行后,不要忘记输出行尾并刷新输出缓冲区。否则,您将收到 超出空闲限制 判决。要冲洗,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • System.out.flush() ;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

黑客

要进行破解,请使用以下格式:

第一行应包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 100$$$)。

每个测试用例的第一行应包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 500, 1 \leq m \leq n(2n-1)$$$)。

以下 $$$n$$$ 行每行应包含 $$$n$$$ 整数,提供有关网格 $$$G$$$ 的信息。这些行的第 $$$i$$$ 包含 $$$n$$$ 整数 $$$G_{i,1}, G_{i,2}, \ldots, G_{i,n}$$$ ($$$1 \leq G_{i,j} \leq n^2$$$)。

然后,对于每条长度递增的$$$n$$$蛇,输出长度为$$$2n-2$$$的字符串$$$s_l$$$。 $$$s_l$$$ 的第 $$$i$$$ 个字母必须表示长度为 $$$l$$$ 的蛇的第 $$$i$$$ 步,其中 'R' 表示右且 'D' 表示向下。对于所有 $$$1 \le l \le n$$$,$$$s_l$$$ 的第一个字母必须是 'D'.

对于每个 $$$l$$$,字符串 $$$s_l$$$ 必须恰好包含 $$$n-1$$$ 'R's 并且恰好 $$$n-1$$$ 'D的。

所有测试用例的 $$$n$$$ 总和不应超过 $$$500$$$。

所有测试用例的 $$$m$$$ 总和不应超过 $$$5 \cdot 10^4$$$。

例如,示例交互对应的hack格式如下。

1
3 15
4 2 5
1 9 3
7 6 8
DRDR
DDRR
DRRD

示例

输入
复制

1
3 15
4 2 5
1 9 3
7 6 8

4

1

9

6

8

4

4

7

7

8

5

4

9

9

9

输出
复制





? 1 1

? 1 2

? 1 3

? 1 4

? 1 5

? 2 1

? 2 2

? 2 3

? 2 4

? 2 5

? 3 1

? 3 2

? 3 3

? 3 4

? 3 5

! 1 4 4 4 4 5 6 7 7 8 8 9 9 9 9

注意

下面显示了三条蛇穿过网格时所覆盖的图块。

第一条蛇覆盖的瓷砖。
第二条蛇覆盖的瓷砖。

第三条蛇覆盖的瓷砖如上面的语句所示。