Awkward Response AtCoder - 2656 ( 二分+交互题)

Problem Statement

This is an interactive task.

Snuke has a favorite positive integer, N . You can ask him the following type of question at most 64 times: "Is n your favorite integer?" Identify N .

Snuke is twisted, and when asked "Is n your favorite integer?", he answers "Yes" if one of the two conditions below is satisfied, and answers "No" otherwise:

• Both n ≤ N and str ( n )≤ str ( N ) hold.
• Both n > N and str ( n )> str ( N ) hold.

Here, str ( x ) is the decimal representation of x (without leading zeros) as a string. For example, str (123)= 123 and str (2000) = 2000 . Strings are compared lexicographically. For example, 11111 < 123 and 123456789 < 9 .

Constraints

• 1≤ N ≤10 ⁹

Input and Output

Write your question to Standard Output in the following format:

? n

Here, n must be an integer between 1 and 10 ¹⁸ (inclusive).

Then, the response to the question shall be given from Standard Input in the following format:

ans

Here, ans is either Y or N . Y represents "Yes"; N represents "No".

Finally, write your answer in the following format:

! n

Here, n = N must hold.

Judging

• After each output, you must flush Standard Output. Otherwise you may get TLE .
• After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
• When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA ).

Sample

Below is a sample communication for the case N =123 :

• Since 1≤123 and str (1)≤ str (123) , the first response is "Yes".
• Since 32≤123 but str (32)> str (123) , the second response is "No".
• Since 1010>123 but str (1010)≤ str (123) , the third response is "No".
• Since 999≥123 and str (999)> str (123) , the fourth response is "Yes".
• The program successfully identifies N =123 in four questions, and thus passes the case.

题意：有一个1~1e9的数字，让你去猜。

你可以做最多64个询问，每一个询问评测机会根据这个规定来返回信息。

Snuke is twisted, and when asked "Is n your favorite integer?", he answers "Yes" if one of the two conditions below is satisfied, and answers "No" otherwise:

• Both n ≤ N and str ( n )≤ str ( N ) hold.
• Both n > N and str ( n )> str ( N ) hold.

思路：

先确定这个数多少位，然后每一位用二分去得到具体这一位的数字。

我们从1到10，再100 ，1000， 每一次*10的去询问，就可以得到这个数字的位数。

如果我们问10，返回Y，问100，返回N，那么这一位是2位数，可以对照规定自己琢磨为什么。

知道多少位只有，我们每一个位置

int mid;
int l=0;
int r=9;

这样二分。

这里我利用了多一位的数一定n>N来一直进入第二个条件来询问的，

比如 是二位数，我问的时候问三位数，已知位放再数字中，未知位放0，询问位通过二分进行变化，

那么一定进入第二个条件，根据字典序的关系，来确定这一位的数字是几。

对于1和100这种1和1后面只有0的数，我们通过询问全是9的数来特判。

细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <strstream>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#define ALL(x) (x).begin(), (x).end()

#define rt return

#define dll(x) scanf("%I64d",&x)

#define xll(x) printf("%I64d\n",x)

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll powmod(ll a,ll b,ll MOD){ll ans=;while(b){if(b%)ans=ans*a%MOD;a=a*a%MOD;b/=;}return ans;}

inline void getInt(int* p);

const int maxn=;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

int query(string ans)

{

    char x;

    cout<<"? "<<ans<<endl;

    cin>>x;

    if(x=='Y')

    {

        return ;

    }else

    {

        return ;

    }

}

void solve()

{

    string temp="";

    string ans="";

    while(!query(temp))

    {

        temp+="";

        ans+="";

    }

    cout<<"! "<<ans<<endl;

}

int main()

{

    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);

    //freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);

    string ans="";

    string res;

    while()

    {

        cout<<"? "<<ans<<endl;

         cin>>res;

        if(res[]=='Y')

        {

            ans+="";

        }else

        {

            break;

        }

        if(ans.length()>)

        {

            solve();

            return ;

        }

    }

    int len=ans.length();

    string temp;

    rep(i,,len-)

    {

        int mid;

        int l=;

        int r=;

        while(l<=r)

        {

            mid=(l+r)>>;

            ans[i]=''+mid;

            if(query(ans))

            {

                r=mid-;

            }else

            {

                l=mid+;

                temp=ans;

            }

        }

        ans=temp;

    }

    temp.pop_back();

    int num=temp.length();

    stringstream ss;

    ss.clear();

    ss<<temp;

    ll fans;

    ss>>fans;

    fans++;

    cout<<"! "<<fans<<endl;

    return ;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '');

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  - ch + '';

        }

    }

    else {

        *p = ch - '';

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  + ch - '';

        }

    }

}