問題はこちら
No.253 ロウソクの長さ - yukicoder
yukicoder No.246 質問と回答 - メモとほとんど同じ
ただし単純な2分探索では、例えばXが10の時、特定する前にロウソクが燃え尽きてしまい、11と区別ができず困る
ということで小さい値は最初に分けておく
最初に聞く値をdとすると、d以下は10回以内に特定しなければならず、d以上はd回以内に特定しなければならない。ということでdとして32を選んだ
int ask(int m){ int n; printf("? %d\n",m); fflush(0); scanf("%d",&n); return n; } int main(){ int i,n,u=1e9+1,l=10,m=32; n=ask(32); while(n){ if(n==1)l=m; else u=m; i++; m=(u+l)/2; n=ask(m-i); } printf("! %d\n",m); return 0; }
参考までに、以前の問題のコードはこうだった
d=1<<30,s; main(i){for(;fflush(!printf("%c %d\n",d?63:33,s+(d/=2))),d;s+=i*d)scanf("%d",&i);}
新たに質問回数を保存する変数jを作るとして、出力部分は
printf("%c %d\n",d?63:33,s+(d/=2)-!!d*j)
とすれば良さそう。sの値の更新もs+=!!~i*dで大丈夫。
問題はdの扱いだが、最初の1回だけ違う処理をすればいいのでjで分岐できる
iが-1だった場合は通常通り対応し、そうでなければ、通常の2分探索を最初からすると考えれば、i!=-1の時だけdに1<<30を加えればよいので、まとめると以下のようになる
d=64,s,j; main(i){for(;fflush(!printf("%c %d\n",d?63:33,s+(d/=2)-!!d*j)),d;j++?s+=!!~i*d:(d+=!!~i<<30))scanf("%d",&i);}
118B
