AtCoder Regular Contest 078 E Awkward Response

E - Awkward Response

Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 800 点

問題文

これはインタラクティブな問題です。

すぬけくんはお気に入りの正の整数 N を持っています。あなたは「n はお気に入りの正の整数か？」と最大 64 回すぬけくんに質問することができます。 N を特定してください。

すぬけくんはひねくれ者なので「n はお気に入りの正の整数か？」と質問されたとき、n が以下の 2 つの条件のどちらかを満たすとき Yes と、それ以外のとき No と答えます。

n≤N かつ str(n)≤str(N)を満たす
n>N かつ str(n)>str(N) を満たす

ここで、str(x) は正の整数 x を十進表記(先頭に 0 をつけない)の文字列として表したものです。例えば str(123)= 123，str(2000) = 2000 です。なお、この問題において文字列同士は辞書順で比較されます。例えば 11111 < 123，123456789 < 9 が成立します。

制約

1≤N≤10⁹

入出力

各質問は、標準出力に以下の形式で出力せよ：

? n

ここで n は 1 以上 10¹⁸ 以下の整数でなければならない。

次に、質問の答えが標準入力から以下の形式で与えられる：

ans

ここで ans は Y または N である．Y ならば、質問の答えが Yes であることを、N ならば No であることを示す。

最後に、答えを以下の形式で出力せよ：

! n

ここで n=N でなくてはならない。

ジャッジ

出力のあと、標準出力を flush せよ。従わない場合 TLE の可能性がある。
答えを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
出力の答えが間違っている場合の挙動は定義されていない(WA とは限らない)。

入出力例

これは N=123 のときの入出力例です。

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

1≤123 かつ str(1)≤str(123) なので答えは Yes です
32≤123 ですが、str(32)>str(123) なので答えは No です
1010>123 ですが、str(1010)≤str(123) なので答えは No です
999≥123 かつ str(999)>str(123) なので答えは Yes です
N は 123 であると 4 回の質問で回答できたため正解となります

Score : 800 points

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:

Input	Output
	`? 1`
`Y`
	`? 32`
`N`
	`? 1010`
`N`
	`? 999`
`Y`
	`! 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.

采用官方题解中的构造方法。先确定该数的位数，之后二分即可。

这里利用了从小到大排数，排在前面的字典序小于后面的字典序。这种构造的想法是由于返回Y、N的判定条件有2点，先固定其中一点的情况，这样返回的结果就只与另一个条件有关。显然确定位数更加容易，采用固定位数的大小关系进行数的字典序判定，依次二分。

 1 #include <bits/stdc++.h>
 2 typedef long long ll;
 3 using namespace std;
 4 const int MAX=1e5+5;
 5 const ll INF=1e9;
 6 char re[20];
 7 ll shi[11]={1},wei;
 8 ll get_wei()
 9 {
10     printf("? %lld
",INF);
11     fflush(stdout);
12     scanf("%s",re);
13     fflush(stdout);
14     if(re[0]=='Y')
15     {
16         for(ll i=1;i<=10;i++)
17         {
18             printf("? %lld
",2LL*shi[i-1]);
19             fflush(stdout);
20             scanf("%s",re);
21             if(re[0]=='Y')
22                 return i;
23             fflush(stdout);
24         }
25     }
26     else
27     {
28         for(ll i=1;i<=10;i++)
29         {
30             printf("? %lld
",shi[i-1]);
31             fflush(stdout);
32             scanf("%s",re);
33             if(re[0]=='N')
34                 return i-1;
35             fflush(stdout);
36         }
37     }
38 }
39 ll get_an(ll wei)
40 {
41     ll l=shi[wei-1],r=shi[wei]-1;
42     ll an=0;
43     while(l<=r)
44     {
45         ll mid=(l+r)/2;
46         printf("? %lld
",10LL*mid);
47         fflush(stdout);
48         scanf("%s",re);
49         if(re[0]=='Y')
50         {
51             an=mid;
52             r=mid-1;
53         }
54         else
55             l=mid+1;
56         fflush(stdout);
57     }
58     return an;
59 }
60 int main()
61 {
62     for(ll i=1;i<=10;i++)
63         shi[i]=10LL*shi[i-1];
64     wei=get_wei();
65     printf("! %lld
",get_an(wei));
66     fflush(stdout);
67     return 0;
68 }