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
prakash:
2016-12-27 19:28:38
very easy
|
|
madhavgaba:
2016-07-05 19:22:13
didn't understand.....same code AC in C but TLE in C++ |
|
pulkitgulati:
2016-07-03 21:20:43
such a beautiful implementation of bitwise operator...worth solving |
|
mcjoshi:
2016-02-27 04:27:15
Wooo.....
|
|
shantanu tripathi:
2015-08-29 18:55:33
@ admin 15011977 plzz check this id why its giving TLE....and when i changed variable from int to long long it got AC.. |
|
chin:
2015-06-18 15:57:03
Brute force works!!!..:D |
|
vank:
2014-09-14 13:07:19
So here comes the Century :) |
|
Barack Obama:
2014-08-21 21:49:36
submission id 12204868, it shows wrong answer.....but test cases running well....what are the possible problems...?? |
|
vb30:
2014-06-18 10:40:57
AC...
|
|
Bhavik:
2014-02-13 09:30:09
brute force works....AC in first attempt |
Added by: | :-) |
Date: | 2013-04-16 |
Time limit: | 1.201s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | own |