E - popcount ≥ K 解説 /

実行時間制限: 6 sec / メモリ制限: 1024 MiB

配点 : 1000 点

問題文

正整数 N,C,K が与えられます。

\displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K を満たす最小の正整数 X を求めてください。

ただし、そのような正整数 X は必ず存在することが証明できます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

popcount とは？

非負整数 x について \operatorname{popcount}(x) とは、x を 2 進法で表記したときの 1 の個数です。 より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。

例えば、13 を 2 進法で表記すると 1101 なので、 \operatorname{popcount}(13)=3 となります。

制約

  • 1\le T \le 10^5
  • 1\le N\le 10^8
  • 1\le C\le 30
  • 1\le K\le 30
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N C K

出力

各テストケースに対する答えを順に改行区切りで出力せよ。

入力例 1

3
3 1 3
6 7 12
100000000 30 30

出力例 1

13
32711
144115183780888607

1 番目のテストケースについて考えます。

X=13 は

  • i=0 のとき：\text{popcount}(X+Ci)=\text{popcount}(13)=3
  • i=1 のとき：\text{popcount}(X+Ci)=\text{popcount}(14)=3
  • i=2 のとき：\text{popcount}(X+Ci)=\text{popcount}(15)=4

より条件を満たしていることが確認できます。

13 より小さい条件を満たす正整数は存在しないので、1 行目には 13 を出力してください。

Score : 1000 points

Problem Statement

You are given positive integers N,C,K.

Find the smallest positive integer X satisfying \displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K.

It can be proved that such a positive integer X always exists.

You are given T test cases; solve each of them.

What is popcount?

For a non-negative integer x, \operatorname{popcount}(x) is the number of 1s in the binary representation of x. More formally, for a non-negative integer x satisfying \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace), we have \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.

For example, 13 in binary is 1101, so we have \operatorname{popcount}(13)=3.

Constraints

  • 1\le T \le 10^5
  • 1\le N\le 10^8
  • 1\le C\le 30
  • 1\le K\le 30
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N C K

Output

Output the answers for the test cases in order, separated by newlines.

Sample Input 1

3
3 1 3
6 7 12
100000000 30 30

Sample Output 1

13
32711
144115183780888607

Consider the first test case.

X=13 satisfies the condition, as confirmed below:

  • When i=0: \text{popcount}(X+Ci)=\text{popcount}(13)=3
  • When i=1: \text{popcount}(X+Ci)=\text{popcount}(14)=3
  • When i=2: \text{popcount}(X+Ci)=\text{popcount}(15)=4

There is no positive integer smaller than 13 satisfying the condition, so output 13 on the first line.