CF1999G2 Ruler (hard version)

Easy version

区别就在于 \(Easy\) 可以询问 \(10\) 次 ，因为 \(log_2(1000)\) 略大于 \(10\)，而且这个标尺很明显具有单调性，所以可以二分，每次询问可以直接询问 \(1\) 和 \(mid\) 即可

Hard version

因为只有 \(7\) 次,所以采用三分，分类讨论

1. \(mid1 \times mid2 = cnt\) 则 \(x\) 大于 \(mid2\) 将 \(l:=mid2+1\)
2. \(mid1 \times (mid2 + 1) = cnt\) 则 \(x\) 处于 \(mid1, mid2\) 之间，将 \(l:=mid1+1,r:=mid2\)
3. 否则 \(x\) 比 \(mid1\) 还要小，\(r:=mid1\) 即可

代码

#include<bits/stdc++.h>
using namespace std;
int check(int sum,int x,int y)
{
    if(x*y==sum) return 1;
    if(x*(y+1)==sum) return 2;
    if((x+1)*(y+1)==sum) return 3;
    return 0;
}
void solve()
{
    int l=2,r=1000;
    while(l<r)
    {
        int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
        cout<<"? "<<mid1<<" "<<mid2<<endl;
        int x;
        cin>>x;
        int k=check(x,mid1,mid2);
        if(k==1) l=mid2+1;
        else if(k==3) r=mid1;
        else if(k==2) l=mid1+1,r=mid2;
        
    }
    cout<<"! "<<l<<endl;
    return;
}
int main()
{
    int _;
    cin>>_;
    while(_--)
    {
        solve();
    }
}