CF1179E Alesya and Discrete Math

我们称一个函数是“好”的，如果它的定义域是某个整数集合，并且当它在 $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$，对所有 $1 \leq i \leq n$ 都成立。巧合的是，$n$ 是 $L$ 的约数。 她向 Alesya 提出了一个游戏。Alesya 每次可以询问 Tanya 某个函数在某个点的值。为了获胜，Alesya 需要为每个函数选择整数 $l_{i}$ 和 $r_{i}$（$0 \leq l_{i} \leq r_{i} \leq 10^{18}$），使得对于所有 $1 \leq i \leq n$，都有 $f_{i}(r_{i}) - f_{i}(l_{i}) \geq \frac{L}{n}$（这里 $f_i(x)$ 表示第 $i$ 个函数在点 $x$ 的值），并且任意两个函数的区间 $[l_i, r_i]$ 互不相交（但可以有一个公共点）。 不幸的是，Tanya 不允许询问次数超过 $2 \cdot 10^{5}$。请帮助 Alesya 获胜！ 可以证明，总是存在满足上述条件的 $[l_i, r_i]$ 的选择。 保证 Tanya 在游戏过程中不会更改函数，即交互器是非自适应的。

第一行包含两个整数 $n$ 和 $L$（$1 \leq n \leq 1000$，$1 \leq L \leq 10^{18}$，$n$ 是 $L$ 的约数），表示函数的数量以及它们在 $10^{18}$ 处的值。

当你找到所需的 $l_i, r_i$ 后，先在单独一行输出一个感叹号 "!"，然后输出 $n$ 行，第 $i$ 行包含两个用空格分隔的整数 $l_i$ 和 $r_i$。 # 交互说明 要询问 $f_i(x)$，请输出问号 "?"，然后输出两个整数 $i$ 和 $x$（$1 \leq i \leq n$，$0 \leq x \leq 10^{18}$）。注意，输出后必须刷新缓冲区以获得响应。 之后，你应读取一个整数，表示第 $i$ 个函数在点 $x$ 的值。 最多允许 $2 \cdot 10^5$ 次询问。 刷新缓冲区的方法（在输出整数和换行后立即执行）： - C++：fflush(stdout) - Java：System.out.flush() - Python：stdout.flush() - Pascal：flush(output) - 其它语言请参考相关文档。 # Hack 数据格式 仅允许 $1 \leq L \leq 2000$ 的测试数据。Hack 数据格式如下： 第一行包含两个整数 $n$ 和 $L$（$1 \leq n \leq 1000$，$1 \leq L \leq 2000$，$n$ 是 $L$ 的约数），表示函数数量和 $10^{18}$ 处的值。 接下来的 $n$ 行，每行包含 $L$ 个数 $l_1, l_2, \ldots, l_L$（$0 \leq l_j < 10^{18}$，$1 \leq j \leq L$，且 $l_j < l_{j+1}$），在第 $i$ 行中，$l_j$ 表示 $f_i(l_j) < f_i(l_j + 1)$。

在样例中，Tanya 有 $5$ 个相同的函数，$f(0) = 0$，$f(1) = 1$，$f(2) = 2$，$f(3) = 3$，$f(4) = 4$，其余所有点的值均为 $5$。 Alesya 需要为每个函数选择两个整数，使得函数在这两个点的值之差不少于 $\frac{L}{n}$（此处为 $1$），且各自的区间长度没有重叠。 一种可行的方式是为第 $1,2,3,4,5$ 个函数分别选择区间 $[0, 1]$、$[1, 2]$、$[2, 3]$、$[3, 4]$ 和 $[4, 5]$。 由 ChatGPT 4.1 翻译