← 返回题目列表

Codeforces · 1973/D

D. 猫、狐狸和最大数组分割

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

这是一个交互问题。

Fox 给了 Cat 两个正整数 $$$n$$$ 和 $$$k$$$。她有一个隐藏数组 $$$a_1, \ldots , a_n$$$ ,长度为 $$$n$$$,使得每个 $$$i$$$ 都有 $$$1 \leq a_i \leq n$$$ 。现在他们要玩以下游戏:

对于任何两个整数 $$$l, r$$$ 使得 $$$1 \leq l \leq r \leq n$$$,定义 $$$f(l, r) = (r - l + 1) \cdot \max\limits_{x=l}^r a_x$$$。换句话说,$$$f(l, r)$$$ 等于子数组 $$$a_l, \ldots, a_r$$$ 的最大值乘以其大小。

Cat 最多可以向 Fox 询问 $$$2 n$$$ 有关数组的问题。他会告诉她两个整数 $$$l$$$ 和 $$$x$$$ ($$$1 \leq l \leq n, 1 \leq x \leq 10^9$$$),她会告诉他一个整数 $$$p$$$ 作为答案 — 最小的正整数 $$$r$$$ 使得 $$$f(l, r) = x$$$,或者 $$$n+1$$$ 如果没有这样的整数$$$r$$$ 存在。

现在,Cat 需要找到最大值 $$$m$$$,使得存在序列 $$$c_1, \ldots, c_{k-1}$$$,使得 $$$1 \leq c_1 < \ldots < c_{k-1} < n$$$ 且 $$$f(1, c_1) = f(c_1 + 1, c_2) = \ldots = f(c_{k-1}+1, n) = m$$$。如果不存在这样的$$$m$$$,他应该指出这一点并以$$$-1$$$作为答案。请注意,对于 $$$k = 1$$$,$$$m$$$ 始终等于 $$$f(1, n)$$$。

换句话说,目标是找到最大的 $$$m$$$,以便您可以将数组精确地拆分为 $$$k$$$ 子数组($$$k$$$ 是在交互开始时给定的常量),以便所有子数组的长度与其最大值的乘积等于 $$$m$$$,或者确定不存在这样的 $$$m$$$。每个元素都应该恰好属于一个子数组。

猫不知道他应该做什么,所以他让你帮他玩这个游戏。

互动

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

每个测试用例的第一行包含两个正整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 10^4$$$) — 隐藏数组的长度和所需分割中的子数组数量。

现在您可以通过以下方式进行查询 - 打印一行“$$$\mathtt{?} \ l \ x$$$”(它必须包含 $$$1 \leq l \leq n$$$, $$$1 \leq x \leq 10^9$$$),并且您将收到最小整数 $$$r$$$ 使得 $$$l \leq r \leq n$$$ 和 $$$f(l, r) = x$$$,或 $$$n + 1$$$(如果不存在这样的 $$$r$$$)。

如果你想打印答案,请输出“$$$\mathtt{!} \ m$$$”,如果你的答案正确,你将收到 $$$1$$$,否则将收到 $$$-1$$$。在第一种情况下,交互会继续下一个测试用例。请注意,打印答案不计入查询次数。请注意,您不会立即收到下一个测试用例的值,您首先必须阅读对上一个测试用例的答案是否正确。

如果您在任何时候收到整数$$$-1$$$,则意味着您的程序进行了无效查询、超出查询限制或给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

保证测试用例的$$$n$$$总和不会超过$$$10^4$$$。

黑客

黑客的格式应如下:第一行应包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。应遵循测试用例的描述。

每个测试用例的第一行应包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 10^4$$$) — 数组 $$$a$$$ 的长度以及要将其拆分为的子数组的数量。

第二行应包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n $$$ ($$$1 \leq a_i \leq n $$$)。

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

示例

输入 #1

3
1 1

1
2 2

1

3

1
6 3

7

2

3

6

1

输出 #1

! 1


? 1 1

? 2 1

! -1


? 1 9

? 1 6

? 3 6

? 4 6

! 6

注意

三个测试用例中的隐藏数组是 $$$[1]$$$、$$$[1, 2]$$$ 和 $$$[1, 3, 6, 1, 2, 1]$$$。在第二个测试用例中,没有任何分割满足约束,因此答案是 $$$-1$$$。

第三个测试用例的第一个查询的答案是 $$$7$$$,因为不存在有效的 $$$r$$$。对于第三个测试用例的第二个查询,由于 $$$2 \cdot \max(1, 3) = 6$$$,我们将得到 $$$2$$$ 作为答案,因为 $$$r = 1$$$ 不满足约束。

示例交互正确猜测了所有三个答案($$$1、-1$$$ 和 $$$6$$$),因此在每个答案后收到 $$$1$$$。