Codeforces #499 Div1 B. Rocket

750ptの問題を入れる必要あったのかな…。
http://codeforces.com/contest/1010/problem/B

問題

1～Mの間の整数xを当てるインタラクティブ問題である。
整数yを送ると、xがそれより小さい・大きい・一致を返す。
ただし、時々大小逆の値を返すことがあり、その周期nは明らかになっている。

解法

最初n回y=1を送れば、n回中どの回次で大小逆の値を返すかわかる。
あとはその情報を元に二分探索するだけ。

int M,N;

int ret[31];

int ask(int v) {
	printf("%d\n",v);
	fflush(stdout);
	int a;
	scanf("%d",&a);
	assert(a!=-2);
	
	if(a==0) exit(0);
	return a;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>N;
	FOR(i,N) ret[i]=ask(1);
	
	int L=1,R=M+1;
	int cnt=0;
	while(R>L+1) {
		x=(L+R)/2;
		
		y=ask(x)*ret[cnt];
		if(y==-1) R=x;
		else L=x+1;
		cnt=(cnt+1)%N;
	}
	
	ask(L);
	
	
}

まとめ

周期性を忘れてる人が結構いてHackを稼げた。