/ 
Time Limit: 6 sec / Memory Limit: 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 is1101, 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.