読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.253 ロウソクの長さ

問題はこちら
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