欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces1103B 二分交互题

程序员文章站 2022-05-22 10:46:27
...

手速场,半小时做完就开始挂机了。

群里有人提出了用v和2v去比较

然后我想起了曾经一道交互题是拿二进制去试探,先加大的,再加小的,看行不行。

这样如果如果v%a<2v%a,那么a>2v,如果输出x,那么v<a<2v

就可以确定a的上下区间,分别是v和2v。

然后再去二分mid,每次输出v和mid,找到v%a<mid%a的mid的最大值。那么mid+1就是a

当时寝室4个人中,我先说二进制试探,然后lts已经差不多完全想出来了,然而wa on test 3.确实确定上下区间后没考虑清楚接下来怎么办。。。感觉再冷静下来想一想就差不多了。还是菜。。。

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	cin>>s;
	while(s!="end")
	{
		int l=0,r=1;
		printf("? %d %d\n",l,r);
		cin>>s;	
		while(s=="y")
		{
			l=r,r<<=1;
			printf("? %d %d\n",l,r);
			fflush(stdout);
			cin>>s;
		}
		int mid;
		while(l+1<r)
		{
			mid=(l+r)>>1;
			printf("? %d %d\n",l,mid);
			fflush(stdout);
			cin>>s;
			if(s=="y")
				l=mid;
			else
				r=mid;
		}
		printf("! %d\n",l+1);
		fflush(stdout);
		cin>>s;
	}
}