一、题目

点此看题

题目描述

猜一个数$a$a，每次可以提一个问题$(x,y)$(x,y)，如果$x\geq y\mod a$x≥ymoda 返回x，否则返回y，你最多询问$60$60次，然后必须回答出$a$a是多少。

二、解法

一道神奇的交互题$qwq$qwq

首先必须明确一个结论：若$x\geq a$x≥a，则 $x\mod a\leq x/2$xmoda≤x/2（证明就不给了，很好意会的）

考虑倍增，$l,r$l,r都是$2$2的幂次，找到最小的$l,r$l,r使得 $l\mod a\geq r\mod a$lmoda≥rmoda，这时候一定是返回x的，结合上面的结论，就会发现这时候$l< a\leq r$l<a≤r

得到这个区间之后，我们可以二分，判断$(mid,l)$(mid,l)会返回什么，由于一直有$l<a\leq r$l<a≤r，所以如果返回x，那么就说明$mid$mid没被取模，所以$a$a一定大于$mid$mid，否则$mid$mid一定取过模，$a$a一定小于等于$mid$mid。由于$l$l是开区间（即$a$a不会取到$l$l），分到$l+1=r$l+1=r是停止，$l+1$l+1就是最终的答案。

#include <cstdio>
#include <iostream>
using namespace std;
int read()
{
 int x=0,flag=1;char c;
 while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
 while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
 return x*flag;
}
string s;
void work(int &l,int &r)
{
    do
    {
        printf("? %d %d\n",l,r);
        cin>>s;
        if(s[0]=='y') l=r,r<<=1;
    }while(s[0]=='y');
}
int main()
{
    cin>>s;
    while(s.size()!=3)
    {
        int l=0,r=1;
        work(l,r);
        while(l+1<r)
        {
            int mid=(l+r)>>1;
            printf("? %d %d\n",mid,l);
            cin>>s;
            if(s[0]=='x') l=mid;
            else r=mid;
        }
        printf("! %d\n",l+1);
        cin>>s;
    }
}

• 点赞
• 收藏
• 分享
• • 文章举报

C202044zxy 发布了236 篇原创文章 · 获赞 12 · 访问量 5812 私信 关注