1665D - GCD Guess - CodeForces Solution


bitmasks chinese remainder theorem constructive algorithms interactive math number theory

Please click on ads to support us..

Python Code:

import sys
import random
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda: sys.stdin.readline().strip("\r\n")
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab,bc,cd : ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x : print(x)
prinT = lambda x : print(x)
f = lambda : sys.stdout.flush()
inv =lambda x:pow(x,mod-2,mod)
dx = [0,0,1,-1]
dy = [1,-1,0,0]
mod = 10**9 + 7
mod1 = 998244353

for _ in range (ii()) :
    x = 0

    for i in range (30) :
        print('?',(1<<i) - x,(3<<i) - x)
        f()
        t = ii()

        if ((t>>i)&1 == 0) :
            x += (1<<i)
        
    print('!',x)
    f()

C++ Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll M = 1e9 + 7;

/*
        ***        **************
        ***        **************
        ***        ***
        ***        ***
        ***        ***
        *************************
        *************************
                   ***        ***
                   ***        ***
                   ***        ***
        **************        ***
        **************        ***

*/

#define v(li) vector<ll>
#define vp(li) vector<pair<ll, ll>>
#define m(li) map<ll, ll>
#define s(li) set<ll>

#define f(i, n) for (ll i = 0; i < n; i++)
#define f1(i, n) for (ll i = 1; i < n+1; i++)
#define test(t) while (t--)
#define w(i, n) while (i < n)
#define prs(n) cout << n << " "
#define prn(n) cout << n << " "
#define newl cout << "\n"
#define pb(a) push_back(a);
#define pop pop_back()
#define in(x) insert(x)
#define fsort(v) sort(v.begin(), v.end())
#define rsort(v) sort(v.begin(), v.end(), greater<ll>())
#define rev(v) reverse(v.begin(), v.end())
#define max_ele(v) *max_element(v.begin(), v.end())
#define min_ele(v) *min_element(v.begin(), v.end())

ll binexp(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = binexp(a, b / 2);
    if (b % 2 == 0)
        return res * res;
    else
        return a * res * res;
}

ll biexm(ll a, ll b)
{
    if (b == 0)
        return 1;
    ll res = biexm(a, b / 2);
    if (b % 2 == 0)
        return ((res % M) * (res % M)) % M;
    else
        return ((((res % M) * (res % M)) % M) * (a % M)) % M;
}

ll hcf(ll a, ll b)
{
    if (a % b == 0)
        return b;
    return hcf(b, a % b);
}
ll lcm(ll a,ll b){
    return (a*b)/(hcf(a,b));
}

int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    /* Sieve */
    // ll N=1e6;
    // ll spf[N+1];
    // f(i,N+1) spf[i]=i;
    // for(ll i=2;i<N+1;i++){
    //     if(spf[i]==i){
    //         for(ll j=i*i;j<N+1;j+=i){
    //            spf[j]=i;
    //         }
    //     }
    // }


    // ll N=1e6;
    // bool isprime[N+1];
    // f1(i,N) isprime[i]=true;
    // isprime[1]=false;
    // for(ll i=2;i<N+1;i++){
    //     if(isprime[i]){
    //         for(ll j=i*i;j<N+1;j+=i) isprime[j]=false;
    //     }
    // }


    // vector<ll> primes;
    // for(ll i=2;i<N+1;i++) if(isprime[i]) primes.push_back(i);


            /* Code Starts here */
    
    ll t;
    cin >> t;
    test(t)
    {   
       ll b=(1LL<<30);
       ll num=0;
       for(ll i=0;i<30;i++){
            ll r=(1LL<<i)-num;
            cout<<"? "<<r<<" "<<b+r<<"\n";
            ll q=(1LL<<i);
            cout.flush();
            ll x;
            cin>>x;
            if(x>q) num+=q;
       }

       cout<<"! "<<num<<"\n";
       cout.flush();
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1735B - Tea with Tangerines
1735C - Phase Shift
1321C - Remove Adjacent
281B - Nearest Fraction
1043A - Elections
1598C - Delete Two Elements
1400C - Binary String Reconstruction
1734D - Slime Escape
1499A - Domino on Windowsill
991A - If at first you don't succeed
1196C - Robot Breakout
373A - Collecting Beats is Fun
965A - Paper Airplanes
863E - Turn Off The TV
630E - A rectangle
1104A - Splitting into digits
19C - Deletion of Repeats
1550B - Maximum Cost Deletion
1693A - Directional Increase
735D - Taxes
989A - A Blend of Springtime
339C - Xenia and Weights
608A - Saitama Destroys Hotel
1342C - Yet Another Counting Problem
548A - Mike and Fax
109A - Lucky Sum of Digits
864C - Bus
626B - Cards
1221A - 2048 Game
1374D - Zero Remainder Array