← 返回题目列表

Codeforces · 2135/D1

D1. 来自未知(简单版)

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

这是问题的简单版本。版本之间的区别在于,在此版本中,对所有查询的文章长度总和没有限制。只有解决了该问题的所有版本,您才能破解。

这是一个交互问题。

RiOI 团队最近开发了一款名为 RiOI编辑器。编辑器仅使用一个整数参数 $$$W$$$ — 每行的宽度。已知 $$$1 \leq W \leq 10^5$$$。

由于您无法理解 RiOI 语言,因此从您的角度来看,单词之间的区别仅在于长度。因此,一个 文章 长度为$$$n$$$的 被定义为由$$$n$$$正整数组成的序列$$$a$$$,其中$$$a_i$$$是$$$i$$$中第$$$i$$$个单词的长度 文章 长度为$$$n$$$的。的 RiOI编辑器 显示 屏幕上的 文章 长度为$$$n$$$的 $$$[a_1, a_2,\ldots, a_n]$$$ 如下:

  • 如果 $$$\max(a_1, a_2, \ldots, a_n) \gt W$$$,则编辑器无法显示 文章 长度为$$$n$$$的;
  • 否则,编辑器能够显示 文章 长度为$$$n$$$的 通过以下过程:
    • 最初,$$$l = 1$$$,$$$s = 0$$$。整个过程中,$$$l$$$始终表示编辑器当前行数,$$$s$$$始终表示最后一行单词长度之和;
    • 然后,对于每个 $$$1\le i\le n$$$:
      • 如果$$$s + a_i \leq W$$$,则将该单词插入到当前行的末尾。因此,$$$l$$$ 保持不变,$$$s$$$ 增加$$$a_i$$$。
      • 否则,该单词将插入新行。因此,$$$l$$$ 变为 $$$l + 1$$$,$$$s$$$ 变为 $$$a_i$$$。
    • 显示文章所需的行数是$$$l$$$的最终值。

你对编辑器很感兴趣,所以你决定通过输入一些值来找出$$$W$$$的值 文章 进入编辑器并观察显示每个内容所需的行数 文章 长度为$$$n$$$的.

正式来说,你可以向陪审团询问 最多 $$$2$$$ 次。在每个查询中,您输入一个 文章 长度为$$$n$$$的 $$$[a_1, a_2, \ldots, a_n]$$$ ($$$1\leq n \leq 10^5$$$) 给编辑,评审团将回复您:

  • 显示所需的行数 文章 长度为$$$n$$$的,如果编辑器能够显示它;
  • $$$0$$$,如果编辑器无法显示 文章 长度为$$$n$$$的.

输入

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

互动

对于每个测试用例,您最多可以进行 $$$2$$$ 查询来找出 $$$W$$$ 的值。保证 $$$1\leq W\leq 10^5$$$。

要进行查询,您应该按以下格式打印新行:

  • $$$\texttt{? } n\texttt{ }a_1\texttt{ }a_2\texttt{ }\ldots\texttt{ }a_n$$$ ($$$1 \leq n, a_i \leq 10^5$$$) — 文章 长度为$$$n$$$的 您输入到编辑器。

在每个查询结束时,陪审团将打印一个整数,如陈述中所述。

要报告您已找到 $$$W$$$ 的值,请按以下格式打印新行:

  • $$$\texttt{! } W$$$ — 编辑器的参数。

打印答案不算作 $$$2$$$ 查询之一。

之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

这个问题中的交互者是 自适应。这意味着$$$W$$$的值在交互过程中可能会改变,但保证总有至少一个整数$$$W$$$满足所有查询。

黑客

要执行黑客攻击,只有以下格式可用:

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$) — 测试用例的数量。然后,输出一个字符串“手册”在同一行。

每个测试用例的唯一行包含一个整数 $$$W$$$ ($$$1\le W\le 10^5$$$) — 编辑器的参数。

该示例的黑客格式如下。

2 manual
20
1

$$$^{\text{*}}$$$要刷新,请使用:

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

示例

输入
复制

2

2

1


0

输出
复制

? 5 1 9 4 6 1

? 2 10 10

! 20
? 1 2

! 1

注意

在第一个测试用例中:

  • 对于第一个查询,单词总长度为$$$1+9+4+6+1=21$$$, 文章 长度为$$$n$$$的 分两行显示,因此 $$$W \lt 21$$$;
  • 对于第二个查询,单词的总长度为$$$10+10=20$$$,并且 文章 长度为$$$n$$$的 显示在一行中,因此 $$$W\ge 20$$$。

因此,我们确定$$$W = 20$$$。

在第二个测试用例中,编辑器无法显示 文章 长度为$$$n$$$的 中唯一的查询。因此,$$$W \lt 2$$$,所以它只能是$$$1$$$。