3953: 走为上(挖土机 CSP-J 模拟赛 ~ 第十五场)

《三十六计》终于结束了，33DAI 可以逃离这三十六道题目的世界了。

他面前一共有 $�$ 扇门，从左往右排成了一排，每扇门背后都有一个编号。$�$ 扇门背后的编号是 $1\sim �$ 的一个排列（每扇门的编号都是 $1\sim �$ 中的一个且互不相等）。33DAI 不知道每扇门背后的编号是多少。

只有编号为 $�$ 的门是出口，33DAI 可以向 Kitten 发起最多 $20$ 次询问，每次询问格式为 ? l r（$1\le �<�\le �$），Kitten 会告诉他从左往右数的第 $�$ 扇门到第 $�$ 扇门中，编号第二大的门是从左往右的第几扇。

如果你已经确定了编号为 $�$ 的门的位置，输出 ! pos（表示你认为编号为 $�$ 的门是从左往右的第 $���$ 扇门），然后结束程序即可。

交互格式

你的程序会和交互器程序进行标准输入输出的交互。你的可以通过输入得到交互器程序的输出，交互器程序会通过输入得到你的程序的输出。

初始你可以通过输入一个整数，得到 $�$。

紧接着每轮交互你可以输出 ? l r 或者 ! x，然后你需要输出一个换行并刷新缓冲区。

• 如果你输出了 ? l r，你将可以通过输入得到一个 $�$，表示从左往右数的第 $�$ 扇门到第 $�$ 扇门中，编号第二大的门是从左往右的第 $�$ 扇。
• 如果你输出了 ! x，交互器会检查编号为 $�$ 的门是否是从左往右数的第 $�$ 扇，并判断你是否通过了这个测试点。输出这行后，你应该结束程序。

如果你的 ? l r 超过了 $20$ 次，或者 ! x 中的 x 不正确，将无法通过对应的测试点。否则你将通过对应的测试点。

Q：什么是刷新缓冲区？
A：cout<<endl; 可以输出一个换行并刷新缓冲区。你也可以通过执行语句 fflush(stdout); 或者 cout.flush(); 来刷新缓冲区。

样例代码

为了避免你不知道你的程序应该长什么样子，下面给一个能拿到本题 $10$ 分的代码，这个代码中我展示了三种不同的刷新缓冲区的方式，代码思路是先确定编号为 $2$ 的门位置，然后根据前两个数中较小的在哪以及后两个数中较小的在哪儿来找到编号为 $3$ 的门的位置。

你的代码不必像我一样问出所有问题的答案之后再来计算，你可以根据每个问题的答案来决定下一个问题问什么。

#include <iostream>
using namespace std;

int main() {
    int n = 5;

    int ans15, ans14, ans25, ans45;

    cout << "? 1 5" << endl;
    cin >> ans15;

    cout << "? 1 4" << endl;
    cin >> ans14;

    cout << "? 2 5" << endl;
    cin >> ans25;

    cout << "? 4 5" << endl;
    cin >> ans45;

    if (ans15 == 1) {
        if (ans14 == 1)
            cout << "! 5" << endl;
        else
            cout << "! 4" << endl;
    } else {
        if (ans25 == 2)
            cout << "! 5" << endl;
        else
            cout << "! 2" << endl;
    }

    return 0;
}


5
5
1
5
5

? 1 5
? 1 4
? 2 5
? 4 5
! 4