KUPC2014 : B - 数当てゲーム

KUPCに多いリアクティブ問題。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_b

問題

1～1000のいずれかである整数Nを当てたい。
ヒントとして、数xを送るとNがxで割り切れるかどうかを教えてくれる。
ヒント200回以内にNを当てよ。

解法

Nが素数の場合は、ピンポイントでそれを問い合わせるしかない。

今回は以下の手法を取った。
Nが素数でなければ、√N以内に１個は約数があるはずである。

そこでまず2～40で割れるか問い合わせる。
あとはNを1000からデクリメントしながら試していく。
2～40で割れるかどうかは判定済みなので、大半はこの時点で解の候補かどうかわかる。

41～1000の間に154個素数があるので、Nが素数でも最大39+154=192回以内の問い合わせで間に合う。

void solve() {
	int f,i,j,k,l,x,y;
	int div[101];
	char judge[2];
	
	FOR(i,40) {
		_P("? %d\n",i+1);
		fflush(stdout);
		scanf("%s", judge);
		div[i+1]=judge[0]=='Y';
	}
	for(j=1000;j>=1;j--) {
		int ok=1;
		FOR(i,40) if((j%(i+1)==0)!=div[i+1]) ok=0;
		if(ok==0) continue;
		_P("? %d\n",j);
		fflush(stdout);
		scanf("%s", judge);
		if(judge[0]=='Y') {
			_P("! %d\n",j);
			return;
		}
	}
	
}

まとめ

意外と多くの問い合わせが必要だった。