题解 CF1999G2 Ruler (hard version)

cjh20090318 · 2024-08-08 11:13:29 · 题解

很简单的交互题，不怎么需要动脑子。

题意

这是一道交互题。

和简单版本不同的是，你最多可以进行 7 次查询。

有一个秘密的尺子，上面缺少一个数字 x。当你测量一个长度为 y 的物体时，尺子会报告以下值：

• 如果 y < x，尺子（正确地）测量物体长度为 y。
• 如果 y \ge x，尺子错误地测量物体长度为 y+1。

你需要找出 x 的值。为此，你可以进行以下形式的查询：

找出 x 的值，回答格式为 \texttt{! x}。

分析

每次可以询问两个值，如果二分同一个值的话未免显得有点浪费。

答案具有单调性，且 \log_3 999 略小于 7，考虑三分。

初始时 l = 2, r = 999，设 m_1 = l + \left\lfloor \dfrac{r-l} 3 \right\rfloor, m_2 = r - \left\lfloor \dfrac{r-l} 3 \right\rfloor。

查询 m_1 \times m_2 组成矩形测出来的面积 S，有如下三种情况：

最后得到的 l 即为缺失的数字 x，每次询问区间长度会缩小到原来的 \dfrac 1 3 倍，询问次数可以保证。

代码

//the code is from chenjh
#include<cstdio>
#define FLUSH fflush(stdout)
using namespace std;
int check(const int x,const int y){
    printf("? %d %d\n",x,y),FLUSH;
    int ret;scanf("%d",&ret);
    return ret;
}
void solve(){
    int l=2,r=999;
    for(int m1,m2,ret;l<r;){
        m1=l+(r-l)/3,m2=r-(r-l)/3;
        ret=check(m1,m2);
        if(ret==(m1+1)*(m2+1)) r=m1;
        else if(ret==m1*(m2+1)) l=m1+1,r=m2;
        else l=m2+1;
    }
    printf("! %d\n",l),FLUSH;
}
int main(){
    int T;scanf("%d",&T);
    while(T--) solve();
    return 0;
}