← 返回题目列表

AtCoder · abc321_e

H. 完全二叉树

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

分数: 450 点

问题陈述

有一棵树 N 顶点编号 1 to N。 对于每个 i\ (2 \leq i \leq N),有一条边连接顶点 i 和顶点 \lfloor \frac{i}{2} \rfloor。 没有其他边缘。

在这棵树中,找到与顶点距离 X is K。 这里,两个顶点之间的距离 u 和 v 定义为连接顶点的简单路径中的边数 u 和 v.

你有 T 测试用例解决。 单个文件中的

约束

  • 1\leq T \leq 10^5
  • 1\leq N \leq 10^{18}
  • 1\leq X \leq N
  • 0\leq K \leq N-1
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出,其中 \mathrm{test}_i 代表 i-第一个测试用例:

T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T

每个测试用例均按以下格式给出:

N X K 

输出

打印 T 行。

的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例作为整数。


示例输入 1

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

示例输出 1

1
3
4
2
0

树 N=10 如下图所示。

在这里,

  • 有 1 顶点, 2,距顶点的距离 2 is 0.
  • 有 3 顶点, 1,4,5,距顶点的距离 2 is 1.
  • 有 4 顶点, 3,8,9,10,距顶点的距离 2 is 2.
  • 有 2 顶点, 6,7,距顶点的距离 2 is 3.
  • 没有与顶点距离的顶点 2 is 4.

示例输入 2

10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

示例输出 2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976