200782: [AtCoder]ARC078 E - Awkward Response

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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 \leq N$ and $str(n) \leq 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 \leq N \leq 10^{9}$

Input and Output

Write your question to Standard Output in the following format:

? $n$

Here, $n$ must be an integer between $1$ and $10^{18}$ (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 \leq 123$ and $str(1) \leq str(123)$, the first response is "Yes".
  • Since $32 \leq 123$ but $str(32) > str(123)$, the second response is "No".
  • Since $1010 > 123$ but $str(1010) \leq str(123)$, the third response is "No".
  • Since $999 \geq 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.

Input

题意翻译

交互题。 给定一个数字$N$，要你通过若干次询问得到$N$。 一次交互格式类似于$?~x$，其中$x$是你询问的数字，交互库会返回答案$Y$或者$N$，分别表示$Yes$和$No$。 返回$Y$当且仅当满足下述条件中的一个： - $x \leqslant N$并且$str(x) \leqslant str(N)$ - $x > N$并且$str(x) > str(N)$ 其中$str(x)$的含义是将十进制整数$x$转成字符串，字符串比较按字典序比较。下面这行代码则是一个交互的示例，其中$s$是字符串变量，用来读取交互库返回的答案。 ```cpp void query(int x){printf("? %d\n",x);fflush(stdout);scanf("%s",s);} ``` 若找到答案，请按$!~x$的格式输出，其中$x$为你找到的数字$N$。 你最多询问 $64$ 次。

Source/Category

加入题单

算法标签：