CF 1999 G2. Ruler (hard version) (*1900) 交互+三分

showball / 2024-09-02 / 原文

CF 1999 G2. Ruler (hard version) (*1900) 交互+三分

题目链接

题意：

现在给你一把暗尺，它缺少了一个数字 $x$ ，那么当你测量的物品长度小于 $x$ 时，测量值就是准确的。

否则，测量值就会大 $1$ 。

现在，你可以进行查询，每次查询可以给出 $a$ 和 $b$ 。系统会返回 $a\times b$ 的值。

现在要求你进行最多 $7$ 次查询，求出 $x$ 的值。

思路：

很显然，我们选择了一组 $a$, $b$ 后，区间就会被分成三段。$3^7=2187 > 1000$ 。所以直接三分即可。

交互题记得把 #define endl '\n' 注释掉。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
//#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   auto query=[&](int l,int r){
     cout<<"? "<<l<<" "<<r<<endl;
     int ret;
     cin>>ret;
     return ret;
   };

   int l=2,r=999;
   while(l<r){
    int m1=l+(r-l)/3,m2=r-(r-l)/3;
    int res=query(m1,m2);
    if(res==(m1+1)*(m2+1)) r=m1;
    else if(res==m1*(m2+1)) l=m1+1,r=m2;
    else l=m2+1; 
   }
   cout<<"! "<<l<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}