D. Game with modulo
题目链接: https://codeforces.com/contest/1104/problem/D
题意:
这题是一个交互题, 首先一开始会有一个数 a, 你最终的目的是要将它猜出来.
每次询问会输出 "? x y", 然后有:
- "x" (without quotes), if
- (
- x
- %
- a
- )
≥
- (y % a)
- .
- "y" (without quotes), if
- (
- x
- %
- a
- )
- <(y % a)
- .
最多给你 60 次询问的机会, 问最后这个 a 是多少.
题解:
这里会用到取余的性质, 假设现在有一个数 b, 现在有 b%a=c. 假设 a>b 那么我们什么都不用管; 假设 a<=b, 我们可以推出 c 是满足 c<a/2 的.
也就是说, 当 x,y 都小于 a 时, 必定会输出 "y"; 否则, 至少有 y<a/2.
那么我们想到一开始令 x=1,y=2 进行倍增, 因为当 y=2*x 时, 若 y>a, 则有 y%a<x%a 恒成立, 此时也 x 也是必定小于 a 的.
那么我们可以通过这个确立一个区间, 然后在区间里面进行二分来询问 a 的值就好了.
注意一下 a=1 以及 a=2 时的特殊情况.
代码如下:
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll mx = 1000000000;
- string s;
- int query(ll x,ll y){
- printf("? %I64d %I64d\n",x,y);
- fflush(stdout);
- char c;
- getchar();
- scanf("%c",&c);
- if(c=='x'){
- return 0;
- }else return 1;
- }
- int main(){
- while(cin>>s){
- if(s=="end") break ;
- ll a=1,b=2;
- if(query(a,b)==0){
- if(query(2,1)==0) printf("! 1\n");
- else printf("! 2\n");
- continue ;
- }
- while(query(a,b)){
- a*=2;
- b*=2;
- if(b>=mx){
- b=mx;
- break ;
- }
- }
- ll l=a+1,r=b+1,mid;
- while(l<r){
- mid=l+r>>1;
- if(query(a,mid)) l=mid+1;
- else r=mid;
- }
- printf("! %I64d\n",r);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2945181.html