CodeForces Ruler (1999G1&G2) 题解

wongdzoendzi / 2024-08-09 / 原文

CodeForces Ruler (1999G1&G2) 题解

题意

对每个例子 (case), 简单版本最多可询问 $10$ 次, 困难版本最多可询问 $7$ 次.

这是一道交互题. 有一把 "秘尺", 尺面丢失了一个数 $x(2\le x\le 999)$. 当你测一实际长度为 $y$ 的物体时: 若 $y<x$, 则测量结果是正确的, 为 $y$; 若 $y\ge x$, 则测量结果是错误的, 为 $y+1$. 你要找到 $x$ 的值. 为此, 你可以以如下格式的询问: ? a b, 我们会测量边长为 $a \times b$ 的矩形, 并给你返回它的面积.

询问次数限制见开头.

思路

发现

对于任取的两数 $a,b (a < b)$, 根据 $x$ 位置的不同, 我们会得到 $3$ 种不同的结果: 若$x \le a$, 得到 $(a+1)(b+1)$; 若 $a<x\le b$, 得到 $a(b+1)$; 若 $x > b$, 得到 $a\times b$.

结论

每两个值, 把区间分成三大块, 一次询问就能确定答案在哪一大块, 可以用三分来做. 每次把区间 $\left[l,r \right]$ 分成 $\left[ l,l+k\right],\left( l+k,r-k\right],\left( r-k,r\right]$ 其中 $k = \lfloor \frac{r-l}{3} \rfloor$ 这三大块, 再判断, 再缩小区间即可.

代码

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int l = 1, r = 1000;
    
    int ans = 0;
    while (l < r) {
        int k = (r - l) / 3;
        int mid1 = l + k, mid2 = r - k;  // 找出中间两个分界点，用于询问并判断x的位置  
        cout << "? " << mid1 << ' ' << mid2 << endl;
        cout.flush();
        int rsp;
        cin >> rsp;
        if (rsp == mid1 * mid2) {
            l = mid2 + 1;
        } else if (rsp == mid1 * (mid2 + 1)) {
            ans = mid2; // ans值要在中途确定，因为结束时mid1或mid2最终的位置不一定是答案
            l = mid1 + 1;
            r = mid2;
        } else if (rsp == (mid1 + 1) * (mid2 + 1)) {
            ans = mid1; // 同上 
            r = mid1;
        }
    }
    cout << "! " << ans << endl;
    cout.flush(); 
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}