L - (Binary Search)^{-1}

2 secs 1024 MB
uni_kakurenbo's icon uni_kakurenbo

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


配点:400400

問題文

Judge 君と Contestant 君は数字当てゲーム「n-n\text{-}guesser」で遊びます.(nn は正の整数)

n-n\text{-}guesser は次のようなゲームです:

  • Judge 君が 00 以上 nn 以下の整数 xx (と呼ぶことにする) を自由に決め,Contestant 君がその数字を当てる.
  • Contestant 君と Judge 君とは次のような対話を何度でも行える:
    • Contestant 君が Judge 君に,実数 qq を自由に選び「qq?」と質問する.
    • qq?」と質問された Judge 君は, Contestant 君に 22 命題「qx<12|q - x | < \frac{1}{2} である」および「qxq \leq x である」の真偽をそれぞれ教える.

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

  • 22 実数 l,rl, r を用意し,はじめ (l,r)=(0,n)(l, r) = (0, n) とする.
  • 対話が終了されるまで以下を繰り返す:
    • q=12(l+r)q = \frac{1}{2}(l + r) として,Judge 君に「qq?」と質問をする.
    • qx<12|q - x| < \frac{1}{2} であるならばである整数の値が確定するため,対話を終了する.
    • qx<12| q - x | < \frac{1}{2} でなく,かつ qxq \leq x ならば llqq で置換し,繰り返しの先頭に戻る.
    • qx<12| q - x | < \frac{1}{2} でなく,かつ qxq \leq x でないならば rrqq で置換し,繰り返しの先頭に戻る.

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

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

X-X\text{-}guesser,(X+1)-, (X+1)\text{-}guesser,,n-, \ldots, n\text{-}guesser (nX),\scriptsize (n \geq X) \normalsize, \ldots のうち,Contestant 君の質問回数がちょうど KK 回になるようなものはいくつありますか?
求めてください.

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

制約

  • 1Φ1031 \leq \Phi \leq 10^3
  • 1X<2401 \leq X < 2^{40}
  • 1K121 \leq K \leq 12
  • X,KX, K は整数

入力

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

XKX \enspace K

出力

答えを出力せよ.

サンプル

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

{7,9,10,15,16,17,45,46,47,48,49,50,51}-\{\, 7, 9, 10, 15, 16, 17, 45, 46, 47, 48, 49, 50, 51 \,\}\text{-}guesser が満たします.

たとえば 7-7\text{-}guesser は次のように進行し,質問は 33 回行われます:

  • Judge 君が鍵として 00 以上 77 以下の整数 x=6(=X)x = 6 \,(= X) を決める.
  • Contestant 君は (l,r)=(0,7)(l, r) = (0, 7) と初期化する.
  • Contestant 君が「72(=12(l+r))\frac{7}{2} \, (= \frac{1}{2}(l + r))?」と質問する.
    • Judge 君によって「72x<12|\frac{7}{2} - x| < \frac{1}{2} ではない」かつ「72x\frac{7}{2} \leq x である」ことが伝えられる.
    • Contestant 君は (l,r)=(72,7)(l, r) = (\frac{7}{2}, 7) と更新する.
  • Contestant 君が「214(=12(l+r))\frac{21}{4} \, (= \frac{1}{2}(l + r))?」と質問する.
    • Judge 君によって「214x<12|\frac{21}{4} - x| < \frac{1}{2} ではない」かつ「214x\frac{21}{4} \leq x である」ことが伝えられる.
    • Contestant 君は (l,r)=(214,7)(l, r) = (\frac{21}{4}, 7) と更新する.
  • Contestant 君が「498(=12(l+r))\frac{49}{8} \, (= \frac{1}{2}(l + r))?」と質問する.
    • Judge 君によって「498x<12|\frac{49}{8} - x| < \frac{1}{2} である」かつ「498x\frac{49}{8} \leq x ではない」ことが伝えられる.
    • Contestant 君は x=498=6x = \left\lfloor \frac{49}{8} \right\rfloor = 6 であることを理解する.

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

提出


Go (1.21)