← 返回题目列表

AtCoder · arc220_e

E. 二进制位计数不少于K

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

给你正整数 N,C,K.

找到最小的正整数 X 满意 \displaystyle\min_{0\le i < N} \text{popcount}(X+Ci) \geq K.

可以证明这样一个正整数 X 始终存在。

你被给予 T 测试用例;解决它们中的每一个。

什么是popcount?

对于非负整数 x, \operatorname{popcount}(x) 是数量 1s 的二进制表示形式 x。更正式地说,对于非负整数 二进制的 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 是 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

考虑第一个测试用例。

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 满足条件,所以输出 13 在第一行。