L - (Binary Search)^{-1}

2 secs 1024 MB
uni_kakurenbo

マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)


配点:

問題文


Judge 君と Contestant 君は数字当てゲーム「guesser」で遊びます.( は正の整数)

guesser は次のようなゲームです:

  • Judge 君が 以上 以下の整数 (と呼ぶことにする) を自由に決め,Contestant 君がその数字を当てる.
  • Contestant 君と Judge 君とは次のような対話を何度でも行える:
    • Contestant 君が Judge 君に,実数 を自由に選び「?」と質問する.
    • ?」と質問された Judge 君は, Contestant 君に 命題「 である」および「 である」の真偽をそれぞれ教える.

Contestant 君は以下の戦略を立てました:

  • 実数 を用意し,はじめ とする.
  • 対話が終了されるまで以下を繰り返す:
    • として,Judge 君に「?」と質問をする.
    • であるならばである整数の値が確定するため,対話を終了する.
    • でなく,かつ ならば で置換し,繰り返しの先頭に戻る.
    • でなく,かつ でないならば で置換し,繰り返しの先頭に戻る.

Contestant 君は戦略通りにゲームをします.

また,Judge 君は整数 が好きなので,Judge 君が guesser () を行うとき,必ずとして整数 を選ぶことが分かっています.
なおこの情報はあなただけが知っています.(Contestant 君は知りません.)

guesserguesserguesser のうち,Contestant 君の質問回数がちょうど 回になるようなものはいくつありますか?
求めてください.

なお,この問題の制約下で答えは有限個であることが示せます.

制約


  • は整数

入力


各テストケースの入力は,それぞれ以下の形式で与えられる:

出力


答えを出力せよ.

サンプル


入力例1
1
6 3
出力例1
13

guesser が満たします.

たとえば guesser は次のように進行し,質問は 回行われます:

  • Judge 君が鍵として 以上 以下の整数 を決める.
  • Contestant 君は と初期化する.
  • Contestant 君が「?」と質問する.
    • Judge 君によって「 ではない」かつ「 である」ことが伝えられる.
    • Contestant 君は と更新する.
  • Contestant 君が「?」と質問する.
    • Judge 君によって「 ではない」かつ「 である」ことが伝えられる.
    • Contestant 君は と更新する.
  • Contestant 君が「?」と質問する.
    • Judge 君によって「 である」かつ「 ではない」ことが伝えられる.
    • Contestant 君は であることを理解する.

入力例2
3
141 1
1000 5
99824435 3
出力例2
1
73
11

提出


Go (1.14)