同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22813_NotOneBitMore

2022-5-16 18:23| 发布者: Hocassian| 查看: 22| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-5-89506981487899-Problem List-采集的数据-后羿采集器.html

Pro.ID

22813

Title

Not One Bit More

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22813

AC

Submit

Ratio

11.11%

时间&空间限制

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Start with an integer, N₀, which is greater than 0. Let N₁ be the number of ones in the binary representation of N₀. So, if N₀ = 27, N₁ = 4.

Ingeneral, let N_i be the number of ones in the binary representation of N_i-1. This sequence will always converge to one.

Forany starting number, N₀ , let K( N₀ ) be the minimum i such that N_i is one. For example, if

N₀ = 31, then N₁ = 5, N₂ = 2, N₃ = 1, so K(31) = 3.

Givena range of consecutive numbers, and a value X, how many numbers in the range have a K(…) value equal to X?

输入

There will be several test cases in the data file. Each test case will consist of three integers on a single line:

LO HI X

where LO and HI ( 1 ≤ LO ≤ HI ≤ 10¹⁸ ) are the lower and upper limits of a range of integers, and X ( 0 ≤ X ≤ 10 ) is the target value for K( … ).

The data file will end with a line with three 0s.

输出

Description

Start with an integer, N₀, which is greater than 0. Let N₁ be the number of ones in the binary representation of N₀. So, if N₀ = 27, N₁ = 4.

Ingeneral, let N_i be the number of ones in the binary representation of N_i-1. This sequence will always converge to one.

Forany starting number, N₀ , let K( N₀ ) be the minimum i such that N_i is one. For example, if

N₀ = 31, then N₁ = 5, N₂ = 2, N₃ = 1, so K(31) = 3.

Givena range of consecutive numbers, and a value X, how many numbers in the range have a K(…) value equal to X?

Input

There will be several test cases in the data file. Each test case will consist of three integers on a single line:

LO HI X

where LO and HI ( 1 ≤ LO ≤ HI ≤ 10¹⁸ ) are the lower and upper limits of a range of integers, and X ( 0 ≤ X ≤ 10 ) is the target value for K( … ).

The data file will end with a line with three 0s.

Output

For each test case, output a line with a single integer, representing the number of integers in the range from LO to HI (inclusive) which have a K(…) value equal to X in the input.

Sample Input

31 31 3
31 31 1
27 31 1
27 31 2
1 4 1
1023 1025 1
1023 1025 2
0 0 0

Sample Output

1
0
0
3
2
1
1

Source

Mid Atlantic 2010

样例输入