# Google Code Jam - New Lottery Game

I was looking around on the web and I found this Google Code Jam Puzzle. I really liked it so I decided to post it here.

### New Lottery Game

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 bitwise-AND operation between the two random numbers generated by the two machines.

To find the bitwise-AND 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 bitwise-AND 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 non-negative integer less than A and the new one will always generate a non-negative integer less than B.

Catalina wants to win this lottery and to give it a try she decided to buy all non-negative 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.

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.

Limits

1 ≤ T ≤ 100. Small dataset

1 ≤ A ≤ 1000. 1 ≤ B ≤ 1000. 1 ≤ K ≤ 1000. Large dataset

1 ≤ A ≤ 109. 1 ≤ B ≤ 109. 1 ≤ K ≤ 109. Sample

Input                 Output
5                     Case #1: 10
3 4 2                 Case #2: 16
4 5 2                 Case #3: 52
7 8 5                 Case #4: 2411
45 56 35              Case #5: 14377
103 143 88


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.

This is code-golf, so shortest code wins. Good Luck

• Is a trailing newline optional and a leading newline allowed? – John Dvorak Nov 1 '14 at 7:14

# Ruby, 107

I expected this would be a much shorter program.

gets
loop{a,b,k=gets.split.map &:to_i
puts"Case ##{$.-1}: #{[*0...a].product([*0...b]).count{|x,y|x&y<k}}"}  ## Explanation • The first line of input can be ignored. • $. is the last read line number.
• [*0...x] is a quick way to turn the Range into an Array. It uses the splat operator (*). Note that the Range is an exclusive one (... instead of ..).
• Array#count takes a block. It will only count the elements for which the block returns a truthy value.
• Any chance you can do $<.map{...}? – John Dvorak Nov 1 '14 at 6:42 • It's actually two characters longer, because it has to take an argument. – britishtea Nov 1 '14 at 14:59 ## APL (63) It's the I/O that costs a lot. ↑{a b k←¯1+⍳¨⎕⋄'Case #',(⍕⍵),': ',⍕+/∊k∊⍨a∘.{2⊥∧/⍺⍵⊤⍨10/2}b}¨⍳⎕  Explanation: • {...}¨⍳⎕: read a number N from the keyboard, and run the following function for each number from 1 to N. • a b k←¯1+⍳¨⎕: read three numbers from the keyboard, generate a list from 0..n-1 for each, and store these in a, b, and k. • a∘.{...}b: for each combination of values from a and b: • ⍺⍵⊤⍨10/2: get the 10-bit binary representation for both values (this is enough given the limits) • ∧/: and together all pairs of bits • 2⊤: turn it back into a number • k∊⍨: for each of these values, test if it is in k • +/: sum the result • 'Case #',(⍕⍵),': ',⍕: generate the output string for this case • ↑: turn the result into a matrix, so each string ends up on a separate line. Test:  ↑{a b k←¯1+⍳¨⎕⋄'Case #',(⍕⍵),': ',⍕+/∊k∊⍨a∘.{2⊥∧/⍺⍵⊤⍨10/2}b}¨⍳⎕ ⎕: 5 ⎕: 3 4 2 ⎕: 4 5 2 ⎕: 7 8 5 ⎕: 45 56 35 ⎕: 103 143 88 Case #1: 10 Case #2: 16 Case #3: 52 Case #4: 2411 Case #5: 14377  ## Golfscript - 74 64 Here is my Golfscript solution (could probably be improved): n/(;0:m;{[~0:w.{{.2$&3$<w+:w;)}4$*;)0}5$*];'Case #'m):m': 'w n}%  Here is the pseudocode I used for this: Split string at newlines Get rid of first element (this is not needed, as I am looping through each element anyway) Let m=0 (case #) For each group of 3 numbers A, B, and K: Let w=0 (number of winning combinations) For(C,0,A-1) For(D,0,B-1) If (A&B)<K Let w=w+1 (one more winning combination) End End End Let m=m+1 (case # incremented) Output("Case #",m,": ",w,"/n") End  Assumes valid input. ## CJam - 62 Could probably be improved; this is just a port of my Golfscript answer. qN/(;{[~0_{{_2$&3$<V+:V;)}4$*;)0}5$*];"Case #"T):T": "V0:V;N}%  # Ruby - 145 I'm still learning Ruby, so there's probably a shorter way to do this. (1..gets.to_i).each{|_|a,b,k=gets.split.map{|x|x.to_i};x=0;(0...k).each{|i|(0...a).each{|j|(0...b).each{|k|x+=1 if j&k==i}}};p"Case ##{_}: #{x}"}  Ungolfed: ( 1 .. gets.to_i ).each{ | _ | a, b, k = gets.split.map{ | x | x.to_i } x = 0 ( 0 ... k ).each{ | i | ( 0 ... a ).each{ | j | ( 0 ... b ).each{ | k | x += 1 if j & k == i } } } p "Case ##{_}: #{x}" }  • Looping with #map is one character shorter than with #each. You don't need to loop trough 0...k, you can simply check if the binary and is lower than k. When you're only calling a method without arguments in a block you can use Symbol#to_proc (x.map &:to_i). – britishtea Nov 1 '14 at 4:59 ## J, 90 (70) I/O to stdin/stdout, works as a script (90). ,&LF@('Test #'&,)"1@(":@#,{:)\@:}.@:(': '&,"1)@(+/@,@(>(17 b./&i.)/@|.)&.".;._2)&.stdin''  Input on stdin, output implicit in REPL (akin to APL, I believe) (70). 'Test #',"1(":@#,{:)\}.': ',"1+/@,@(>(17 b./&i.)/@|.)&.".;._2 stdin''  Ergh, J isn't good at I/O requirements like these. For the curious, the part doing the heavy work is +/@,@(>(17 b./&i.)/@|.)&."., which solves a single line of the problem (taking and returning a string). ## CJAM - 57 0li{)"Case #"\':Sl~:K;L\{(2$,{1$&@+\}%~}h;\;{K<},,N4$}\*;


I think this can be golfed further.

0                                  acts as a counter for the case #
li{                              accepts the first line of input as integer/opens block
)                             iterates counter
"Case #"\':S                 adds "Case #X: " to stack (though in 4 parts)
l~:K;L\                     takes next line of input, assign K, add null array
{
(2$, decrease B and generate list of number <A { 1$&                    Copy the current value of B, do & with current n<A
@+\                   Add the new possible lottery number to array
}%~                     loop for each element if the list of numbers <A
}h                        loop which repeats for all numbers less than B
;/;{K<},,                   trim and count the possible numbers less than K
N4$add new line and copy the counter back in place }\* runs the block T times ; removes the counter so it doesn't print  Output: Case #1: 10 Case #2: 16 Case #3: 52 Case #4: 2411 Case #5: 14377 ` • li{"Case #"]_,6/)+~':Sl~:K;L\{(2$,{1\$&@+\}%~}h;\;{K<},,N}* for fun, this does the same thing but instead of having a counter for case#, it counts the number of elements in the stack. – kaine Nov 1 '14 at 23:32