原题链接：
https://codeforces.com/contest/1999/problem/G1 (Easy Ver， 可查询 10 次)

https://codeforces.com/contest/1999/problem/G2 (Hard Ver)

题目大意

我们有一把尺子，但是中间缺少了一个数字 $x (2\leq x\leq 999)$ 。如果使用这把尺子测量长度大于等于 $x$ 的物体时，得到的长度会比正常情况多 $1$ 。

每次可以进行以下查询：

? a b

每次查询会使用这把尺子对长为 $a$ ，宽为 $b$ 的矩形进行测量，并根据其测量结果算出面积，求问是否能在 7 次查询内找到缺失的 $x$ ，并以! x的形式输出。

思路

由于 $3^{7}=2187>1000$，即 $\log_3{1000}<7$ ，因此考虑三分求解。

将 $x$ 的上下界作为初始的 $l$ 和 $r$ 值。令左三等分点 $midl=l+(r-l)/3$ ，右三等分点 $midr=r-(r-l)/3-1$，

每次询问都对 $midl$ 和 $midr$ 进行，根据询问所得的面积 $S$ 进行区间的选择：

1. 当 $S=midl\cdot midr$ 时，说明询问的两个数都在 $x$ 左侧，取区间 $\lbrack midr+1,r\rbrack$；
2. 当 $S=midl\cdot (midr+1)$ 时，说明 $midl$ 在 $x$ 左侧，$midr$ 在 $x$ 右侧（或就在 $x$ 处），取区间 $\lbrack midl+1,midr\rbrack$；
3. 当 $S=midl\cdot midr$ 时，说明询问的两个数都在 $x$ 右侧（$midl$ 可能在 $x$ 处），取区间 $\lbrack l,midl\rbrack$。

经过至多 $7$ 次询问之后即可将区间范围缩小至 $1$，此时输出答案即可。

如果每次只能询问一个数 $a$，因为 $\log_2{1000}<10$ ，可知询问次数的上界为 $10$ 次，对应该题简单版本的上界，可以使用更简单的二分法求解。

可以进一步推广得到：若 $x$ 的值域极差为 $d$，每次可以询问 $n$ 个数，那么询问次数的上界为 $\lceil \log_{n+1}{(d+1)} \rceil$。

实现

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  while (T--) {
    int l = 2, r = 999;
    while (l < r) {
      int midl = l + (r - l) / 3, midr = r - (r - l) / 3 - 1;
      int num;
      cout << "? " << midl << ' ' << midr << endl;
      cin >> num;
      if (num == midl * midr) {
        l = midr + 1;
      } else if (num == midl * (midr + 1)) {
        l = midl + 1, r = midr;
      } else {
        r = midl;
      }
    }
    cout << "! " << r << endl;
  }
  return 0;
}