KUPCに多いリアクティブ問題。
http://kupc2014.contest.atcoder.jp/tasks/kupc2014_b
問題
1~1000のいずれかである整数Nを当てたい。
ヒントとして、数xを送るとNがxで割り切れるかどうかを教えてくれる。
ヒント200回以内にNを当てよ。
解法
Nが素数の場合は、ピンポイントでそれを問い合わせるしかない。
今回は以下の手法を取った。
Nが素数でなければ、√N以内に1個は約数があるはずである。
そこでまず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; } } }
まとめ
意外と多くの問い合わせが必要だった。