You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道交互题。

交互库在 $1$ 到 $n$ 之间选定了一个整数。你需要通过不断猜测，根据交互库返回的大小关系找出这个整数。

你最多可以猜测 $30$ 次。

交互协议

程序开始时，你应当从标准输入读取一个整数 $n$（$1\le n\le 10^9$）。

此后重复以下过程：

1. 向标准输出打印一个整数，表示你的猜测；
2. 从标准输入读取交互库的回答。

交互库的回答只可能是：

• 1：所选整数大于你上一次的猜测；
• -1：所选整数小于你上一次的猜测；
• 0：猜测正确。读到 0 后，你的程序必须立即结束。

每次输出猜测后必须换行并刷新输出缓冲区，否则可能得到超时结果。

交互示例

5
-1
1
0

3
1
2

示例中，答案是 $2$。交互输入与输出按发生顺序交错，实际程序不应额外输出空行。

参考实现

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define sc second
#define ll long long
using namespace std;
int n, res; 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int l = 1, r = n, mid, x;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		cout << mid << endl;
		cin >> x;
		if (x == 0) return 0;
		if (x == 1) l = mid + 1;
		else r = mid - 1; 
	}
	return 0;
}