HAP01 - Play with Binary Numbers
Let S be the binary representation of an integer. We define two functions a(i) and b(i) such that:
- a(i) = Number of occurrences of '1' at odd positions of S,
- b(i) = Number of occurrences of '1' at even positions of S.
For example: for integer 19, S = 10011, so a(19) = 2 and b(19) = 1.
Input
First line contains an integer T, the number of test cases. Then T lines follow. On each line, you will be given three integers M, N, K.
Output
For each test case output a single integer R, where R is the number of integers 'i' between M and N (both inclusive) such that absolute difference of a(i) and b(i) is equal to K. The answer to each each test case should be on a separate line.
Constraints
T <= 50
1 <= M < N <= 10^19
1 <= N - M <= 10^6
0 <= K <= 50
Example
Input: 1 1 10 2 Output: 2
hide comments
RuPp$:
2013-04-18 16:06:45
getting WA, Can you suggest why?
|
Added by: | :-) |
Date: | 2013-04-16 |
Time limit: | 1.201s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | own |