E: Awkward Response - AtCoder Regular Contest 078
公開されない整数Nが存在し、システムに整数nを入力とするクエリを出すと、下記の条件の時Yesが帰ってくる。
n≤N かつ str(n)≤str(N)を満たす
n>N かつ str(n)>str(N) を満たす
この時、最大64回の質問でNを特定せよ。
まず分かるのはnにSuffix 000000... をつけておくと n>=N は必ず満たされるので文字列比較のみになり2分探索でnのあるprefixとNが一致するように特定することができる。ここではN<=10^9がわかっているので、10Nから100Nの範囲で探す。
その後、prefixの桁数を特定すればそれが答えである。Nが10の累乗の場合でない場合は、10^10, 10^9,...などと比較していくと、一番目の条件が一致した段階でちょうど桁数になっている。Nが10の累乗でない、というおのは探索したnの最上位の桁が1より大きい時と見ればよい。
Nが10の累乗の可能性があるとき、こちらは逆に9999999... と言った数字と比較する。すると2番目の条件で判定できる。O(logN)。
