PTA：猜数字-交互版

你需要编写一个“猜数字”的程序。跟你做过的大部分题目不一样，你需要通过不断地询问另外一个程序（以下称之为“交互程序”）来猜到最终的数字。

在你的程序刚运行时，交互程序会通过标准输入给你提供一个数字 N，表示你需要猜的数字在 1 到 N 范围里。

接下来你可以开始发起你的询问。你可以直接通过输出到标准输出来询问；每次询问为一个数字，表示你猜测的结果。每次询问后，你需要刷新输出流，否则可能会有输出内容停留在缓冲区不被输出。例如 C++ 你可以使用

fflush(stdout)

，Java 你可以使用

System.out.flush() 

，Pascal 你可以使用

flush(output)

，Python 则可以使用

stdout.flush()

。

交互程序会根据你的询问返回你的猜测与正确答案的比较情况。具体而言：

• 如果正确答案小于你的猜测，则会返回 <；
• 如果正确答案大于等于你的猜测，则会返回 >=

一旦你确定你找到了正确的答案，则输出

! x

（x 是你猜测的数字，注意与感叹号用空格隔开），并立刻结束你的程序（否则判题系统可能不能返回正确的判题结果）。

最后，总的询问次数不能大于等于 25 次。

请你尝试猜对正确的数字吧！

输入样例:

20
>=
<
>=
<
>=
<

输出样例:

5
18
10
13
12
11
! 12

样例程序

以下程序用于你理解如何与交互程序进行交互，并不是正确的程序。

#include <cstdio>

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", n / 2);
    fflush(stdout);
    char ans[10];
    scanf("%s", ans);
    if(ans[0] == '>') {
        printf("! %d\n", n / 2 + 1);
        fflush(stdout);
    } else {
        printf("! %d\n", n / 2 - 1);
        fflush(stdout);
    }
}

解题思路：

对面的程序首先确定了确定了一个值（程序心里想着。。。），然后告诉了我们一个最大数，确定值就在这之间，然后我们开始猜，对面程序会根据我们猜的数不断告诉我们是大于等于或者小了，最后我们能够确定就是这个数的时候，输出！+数。

但是这个过程，不管是对面的程序还是自己，都是我们自己写出来的。。。所以有点难以理解，不过慢慢想想就懂了。（假设自己分身？？？对面程序是分身，他心里想了一个数，本体来猜）

代码本身使用了类似于折半查找的思想，每次输入更新mid，min和max的值，不太难就没写注释，建议先跟着代码过程手写一波每一步的结果，一目了然。

AC代码如下：

#include <stdio.h>
int main()
{
    int mid,max,min=0;
    scanf("%d", &max);
    mid=(max+min)/2;
    printf("%d\n",mid);
    fflush(stdout);
    char ans[2];
    for(int i=0; i<25; i++)
    {
        scanf("%s", ans);
        if(ans[0] == '>'){
            min = mid;
            mid=(max+min)/2;
            if(mid == min){
                printf("! %d\n",mid);
                break;
            }
            else{
                printf("%d\n", mid);
            }

            fflush(stdout);
        }
        else{
            max = mid;
            mid=(max+min)/2;
            if(mid == max){
                printf("! %d\n",mid);
                break;
            }
            else{
                printf("%d\n", mid);
            }
            fflush(stdout);
        }
    }
    return 0;
}