<span>Awkward Response AtCoder - 2656 ( 二分+交互题)</span>

Problem Statement

This is an interactive task.

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

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

Both <var>n≤N</var> and <var>str(n)≤str(N)</var> hold.
Both <var>n>N</var> and <var>str(n)>str(N)</var> hold.

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

Constraints

<var>1≤N≤10⁹</var>

Input and Output

Write your question to Standard Output in the following format:

? <var>n</var>

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

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

<var>ans</var>

Here, <var>ans</var> is either Y&nbs***bsp;N. Y represents "Yes"; N represents "No".

Finally, write your answer in the following format:

! <var>n</var>

Here, <var>n=N</var> 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 <var>N=123</var>:

Input	Output
	`? 1`
`Y`
	`? 32`
`N`
	`? 1010`
`N`
	`? 999`
`Y`
	`! 123`

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

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

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

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

Both <var>n≤N</var> and <var>str(n)≤str(N)</var> hold.
Both <var>n>N</var> and <var>str(n)>str(N)</var> 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=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int query(string ans)
{
    char x;
    cout<<"? "<<ans<<endl;
    cin>>x;
    if(x=='Y')
    {
        return 1;
    }else
    {
        return 0;
    }
}
void solve()
{
    string temp="9";
    string ans="1";
    while(!query(temp))
    {
        temp+="9";
        ans+="0";
    }
    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="1";
    string res;
    while(1)
    {
        cout<<"? "<<ans<<endl;
         cin>>res;
        if(res[0]=='Y')
        {
            ans+="0";
        }else
        {
            break;
        }
        if(ans.length()>11)
        {
            solve();
            return 0;
        }
    }
    int len=ans.length();
    string temp;
    rep(i,0,len-1)
    {
        int mid;
        int l=0;
        int r=9;
        while(l<=r)
        {
            mid=(l+r)>>1;
            ans[i]='0'+mid;
            if(query(ans))
            {
                r=mid-1;
            }else
            {
                l=mid+1;
                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 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}