Guess The Numbe (交互题)

左手的ㄟ右手 2021-07-16 20:23 278阅读 0赞

D. Guess The Number  
Time limit 2 seconds  
Memory limit 512Mb  
Input standard input  
Output standard output

This is an interactive problem.

Somebody has secretly set the number x (1 ≤ x ≤ n). Your program has to guess this number interacting with the testing system. There are two kinds of queries:

? y (1 ≤ y ≤ n) — the result is either string “>=” which means that x ≥ y, or string “<” which means that x < y (without quotes)
    ! y (1 ≤ y ≤ n) — should be called once when your program is about to terminate. All output after it is ignored. You must make this call to tell the system the number you discovered (i. e., x = y).

Interaction Protocol

Input starts with a line with single integer 1 ≤ n ≤ 109. After it there will follow separate lines with answers to your queries in form .

Output queries one per line, as specified in the statement.

After each query read the separate line with answer to your query in form ”? y”.

The total number of queries of the first type must not be greater than binary logarithm of n rounded up, otherwise you will get “Wrong answer”. Do not forget to do two things after each query: 1) to print the newline; 2) to flush the output. It is possible to do using fflush(stdout) or cout.flush() in C/C++ and flush(output) in Pascal.

Interaction Example

16  
? 9  
<  
? 5

> # =  
 ? 7  
 <  
 ? 6 #

! 6

第一次做交互题，根据你的输入会不断反馈给你输出帮助你找到答案。这题很明显就是一个二分查找，注意一下二分过程 当<时 r=mid-1（答案必然小于mid） >=时 l=mid(答案可能等于mid) 然后当范围缩小到l==r时，l即为答案。且mid=(1+l+r)/2要不然会无限循环 L 3 R 4 mid=(3+4+1)/2=4就可以顺势让r-1=3，得出答案3。

啊对，一般交互题要注意每次输出后加个cout.flush() 来清空缓冲区，下面代码中cout<<endl也会清空所以就不加了。

Code

#include<iostream>
    #include<string>
    using namespace std;
    
    int main()
    { 
    	int n;cin >> n;
    	int l = 1, r = n;
    	while (l != r)
    	{ 
    		int mid = (l + r+1) / 2;
    		cout << "?" << mid << endl;
    		string str;cin >> str;
    		if (str == "<")r = mid - 1;
    		else l = mid;
    	}
    	cout << "?" << l << endl;
    }