原题链接：
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;
}