4718번 - Not One Bit More
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1 | 1 | 1 | 100.000% |
문제
Start with an integer, N0, which is greater than 0. Let N1 be the number of ones in the binary representation of N0. So, if N0 = 27, N1 = 4.
In general, let Ni be the number of ones in the binary representation of Ni−1. This sequence will always converge to one.
For any starting number, N0, let K(N0) be the minimum i such that Ni is one. For example, if N0 =31, then N1 =5, N2 =2, N3 =1, so K(31)=3.
Given a 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 ≤ 1018) 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.
출력
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.
예제 입력 1
31 31 3 31 31 1 27 31 1 27 31 2 1 4 1 1023 1025 1 1023 1025 2 0 0 0
예제 출력 1
1 0 0 3 2 1 1