【AtCoder Regular Contest 078 E】Awkward Response | Mrsrz's blog

交互题，二分。

题目大意：

你要猜一个数 $N$，你每次可以询问 $n$，然后交互库会在以下情况时返回 Y：

• $n\leq N$ 且 $n$ 的字典序小于等于 $N$ 的字典序。
• $n\gt N$ 且 $n$ 的字典序严格大于 $N$ 的字典序。

否则会返回 N。

你要在 $64$ 次询问中得到答案。

题解：

首先确定有多少位。可以从 $10^9$ 开始询问，每次减少一个 $0$。碰到 Y 说明这时位数刚好。有一个例外：$N$ 是 $10$ 的幂次，那么永远都是 Y，则还得对每个 $10^x$，判断一下 $10^x-1$。

确定最高位是多少，直接枚举每一位是什么即可。

确定之后的位是多少，只要二分这位是什么即可。

$64$ 次操作完全够用。

Code：

#include<cstdio>
int ans,w=1e9;
char o[5],lst;
int main(){
    while(w!=1){
        printf("? %d\n",w),fflush(stdout),scanf("%s",o);
        if(*o=='Y'){
            printf("? %d\n",w-1),fflush(stdout),scanf("%s",o);
            if(*o=='N'||lst=='N')break;
        }
        lst=*o;
        w/=10;
    }
    if(w==1e9){printf("! %d\n",w),fflush(stdout);return 0;}
    if(w==1){
        for(int i=1;i<10;++i){
            printf("? %d0\n",i),fflush(stdout),scanf("%s",o);
            if(*o=='Y'){printf("! %d\n",i),fflush(stdout);return 0;}
        }
    }else{
        for(int i=1;i<10;++i){
            printf("? %d\n",i),fflush(stdout),scanf("%s",o);
            if(*o=='N')break;
            ans=i*w;
        }
        for(w/=10;w;w/=10){
            int l=0,r=9,s=0;
            while(l<=r){
                const int mid=l+r>>1;
                printf("? %lld\n",(ans+mid*w+w)*10LL-1);
                fflush(stdout),scanf("%s",o);
                if(*o=='N')l=mid+1;else r=(s=mid)-1;
            }
            ans+=s*w;
        }
    }
    printf("! %d\n",ans),fflush(stdout);
    return 0;
}