[HomeTrainingProblemsContestsC Language]  [LoginRegister] 
Problems Status Rank 
Problem 1336
New Lottery Game
Time Limit: 1000ms
Memory Limit: 65536kb Description
The Lottery is changing! The Lottery used to have a machine to generate a random winning number. But due to cheating problems, the Lottery has decided to add another machine. The new winning number will be the result of the bitwiseAND operation between the two random numbers generated by the two machines.To find the bitwiseAND of X and Y, write them both in binary; then a bit in the result in binary has a 1 if the corresponding bits of X and Y were both 1, and a 0 otherwise. In most programming languages, the bitwiseAND of X and Y is written X&Y. For example: The old machine generates the number 7 = 0111. The new machine generates the number 11 = 1011. The winning number will be (7 AND 11) = (0111 AND 1011) = 0011 = 3. With this measure, the Lottery expects to reduce the cases of fraudulent claims, but unfortunately an employee from the Lottery company has leaked the following information: the old machine will always generate a nonnegative integer less than A and the new one will always generate a nonnegative integer less than B. Catalina wants to win this lottery and to give it a try she decided to buy all nonnegative integers less than K. Given A, B and K, Catalina would like to know in how many different ways the machines can generate a pair of numbers that will make her a winner. Could you help her? Input
The first line of the input gives the number of test cases, T. T lines follow, each line with three numbers A B K.1 ≤ T ≤ 100. 1 ≤ A ≤ 109. 1 ≤ B ≤ 109. 1 ≤ K ≤ 109. Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of possible pairs that the machines can generate to make Catalina a winner.
Sample Input
5 3 4 2 4 5 2 7 8 5 45 56 35 103 143 88 Sample Output
Case #1: 10 Case #2: 16 Case #3: 52 Case #4: 2411 Case #5: 14377 Hint
In the first test case, these are the 10 possible pairs generated by the old and new machine respectively that will make her a winner: <0,0>, <0,1>, <0,2>, <0,3>, <1,0>, <1,1>, <1,2>, <1,3>, <2,0> and <2,1>. Notice that <0,1> is not the same as <1,0>. Also, although the pair <2, 2> could be generated by the machines it wouldn't make Catalina win since (2 AND 2) = 2 and she only bought the numbers 0 and 1.
Source
Google Code Jam Round 1B 2014
