← 返回题目列表

Codeforces · 1179/E

E. Alesya 和离散数学

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

如果一个函数的定义域是一组整数,并且它是在 $$$x$$$ 和 $$$x-1$$$、$$$f(x) = f(x-1) + 1$$$ 或 $$$f(x) = f(x-1)$$$ 中定义的,我们称该函数为好函数。

Tanya 发现了 $$$n$$$ 好的函数 $$$f_{1}、\ldots、f_{n}$$$,它们定义在从 $$$0$$$ 到 $$$10^{18}$$$ 的所有整数上,并且 $$$f_i(0) = 0$$$ 和 $$$f_i(10^{18}) = L$$$ 对于所有$$$i$$$ 从 $$$1$$$ 到 $$$n$$$。 $$$n$$$ 是 $$$L$$$ 的除数,这是一个臭名昭著的巧合。

她建议阿莱西亚玩游戏。使用一个问题 Alesya 可以向 Tanya 询问任意单个点上任意单个函数的值。要获胜,Alesya 必须选择整数 $$$l_{i}$$$ 和 $$$r_{i}$$$ ($$$0 \leq l_{i} \leq r_{i} \leq 10^{18}$$$),使得 $$$f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n}$$$ (此处$$$f_i(x)$$$ 表示对于所有 $$$i$$$,第 $$$i$$$ 个函数在点 $$$x$$$ 处的值,使得 $$$1 \leq i \leq n$$$ 使得对于任何一对两个函数,它们的线段 $$$[l_i, r_i]$$$ 不相交(但可能有一个公共点)。

不幸的是,Tanya 不允许提出超过 $$$2 \cdot 10^{5}$$$ 的问题。帮助阿莱西亚取得胜利!

可以证明,满足上述条件的$$$[l_i, r_i]$$$总是可以选择的。

可以保证的是,Tanya 在游戏过程中不会改变功能,即交互器不具有自适应性

输入

第一行包含两个整数 $$$n$$$ 和 $$$L$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq L \leq 10^{18}$$$, $$$n$$$ 是 $$$L$$$ 的除数) — 函数的数量及其值$$$10^{18}$$$。

互动

要询问 $$$f_i(x)$$$,请打印符号“?”不带引号,然后是两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \leq i \leq n$$$, $$$0 \leq x \leq 10^{18}$$$)。请注意,您必须刷新输出才能获得响应。

之后,您应该读取一个整数,它是点 $$$x$$$ 中第 $$$i$$$ 个函数的值。

您最多可以提出 $$$2 \cdot 10^5$$$ 问题。

要刷新,您可以使用(在打印整数和行尾之后):

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

黑客:

只有 $$$1 \leq L \leq 2000$$$ 的测试才允许进行黑客攻击,对于黑客攻击,请使用以下格式设置测试:

第一行应包含两个整数 $$$n$$$ 和 $$$L$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq L \leq 2000$$$, $$$n$$$ 是 $$$L$$$ 的除数) — 函数数量及其值$$$10^{18}$$$。

$$$n$$$ 以下各行应包含 $$$L$$$ 数字 $$$l_1$$$, $$$l_2$$$, ... , $$$l_L$$$ ($$$0 \leq l_j < 10^{18}$$$ 对于所有 $$$1 \leq j \leq L$$$ 和 $$$l_j < l_{j+1}$$$ 对于所有 $$$1 < j \leq L$$$),在 $$$i$$$ 中的第 $$$l_j$$$ 意味着 $$$f_i(l_j) < f_i(l_j + 1)$$$。

输出

当您找到需要的 $$$l_i, r_i$$$ 时,打印 $$$"!"$$$(不带引号),然后在 $$$n$$$ 行中,其中的 $$$i$$$ 应包含两个整数 $$$l_i$$$、$$$r_i$$$ 除以空格。

示例

输入 #1

5 5
? 1 0
? 1 1
? 2 1
? 2 2
? 3 2
? 3 3
? 4 3
? 4 4
? 5 4
? 5 5
!
0 1
1 2
2 3
3 4
4 5

输出 #1

0
1
1
2
2
3
3
4
4
4
5

注意

在示例中,Tanya 具有 $$$5$$$ 相同的函数,其中 $$$f(0) = 0$$$、$$$f(1) = 1$$$、$$$f(2) = 2$$$、$$$f(3) = 3$$$、$$$f(4) = 4$$$ 且所有剩余点的值为 $$$5$$$。

Alesya 必须为所有函数选择两个整数,以便函数在其点上的值差不小于 $$$\frac{L}{n}$$$ (这里是 $$$1$$$)并且线段交集的长度为零。

一种可能的方法是为函数 $$$1$$$ 选择对 $$$[0$$$, $$$1]$$$, $$$[1$$$, $$$2]$$$, $$$[2$$$, $$$3]$$$, $$$[3$$$, $$$4]$$$ 和 $$$[4$$$, $$$5]$$$,分别为$$$2$$$、$$$3$$$、$$$4$$$ 和$$$5$$$。