M_sea

CF1103B Game with modulo
CodeForcesLuogu翻译分析想法很神仙的一道交互题。我竟然没想出来qwq首先,$y=x\mod a$的函...
扫描右侧二维码阅读全文
31
2019/01

CF1103B Game with modulo

CodeForces

Luogu翻译

分析

想法很神仙的一道交互题。我竟然没想出来qwq

首先,$y=x\mod a$的函数图像大概是这个样子(忽略$y$轴左边的部分):

可以发现是周期为$a$的函数。

于是,对于$i$和$i\times 2$的一组询问,当返回x也就是$i\times 2\mod a<i\mod a$的时候,这时一定有$i<a\leq i\times 2$。

当然有特殊情况,下面再考虑。

找到$a$的范围之后,就可以二分了。当然还是询问$mid$和$mid\times 2$。

最后注意判一下答案为$1$或$2$的情况。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

string s,res;

int main() {
    while (233) {
        cin>>s; if (s=="end") break;
        int L,R;
        for (re ll i=1;;i<<=1) {
            cout<<"? "<<i<<' '<<min(i<<1ll,(ll)2e9)<<'\n';
            fflush(stdout); cin>>res;
            if (res=="x") { L=i,R=(int)min((ll)1e9,i<<1ll); break; }
        }
        while (L<R) {
            int mid=(L+R)>>1;
            cout<<"? "<<(mid<<1)<<' '<<mid<<'\n';
            fflush(stdout); cin>>res;
            if (res=="x") R=mid;
            else L=mid+1;
        }
        if (L==2) {
            cout<<"? 2 1\n"; fflush(stdout);
            cin>>res;
            if (res=="x") cout<<"! 1\n";
            else cout<<"! 2\n";
        }
        else cout<<"! "<<L<<'\n';
        fflush(stdout);
    }
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 13 PM

2 条评论

  1. xgzc

    文章目录打错了啊2333
    怎么两个都是代码啊QwQ

    1. M_sea
      @xgzc

      已修改,感谢qwq

发表评论