Estaba buscando en la web y encontré este Google Code Jam Puzzle. Realmente me gustó, así que decidí publicarlo aquí.

Nuevo juego de lotería

¡La lotería está cambiando! La Lotería solía tener una máquina para generar un número ganador aleatorio. Pero debido a problemas de trampa, la Lotería ha decidido agregar otra máquina. El nuevo número ganador será el resultado de la operación bit-AND entre los dos números aleatorios generados por las dos máquinas.

Para encontrar el bit-AND de X e Y , escríbalos en binario; entonces un bit en el resultado en binario tiene un 1 si los bits correspondientes de X e Y eran ambos 1, y un 0 en caso contrario. En la mayoría de los lenguajes de programación, el AND bit a bit de X e Y se escribe X&Y .

Por ejemplo: la máquina anterior genera el número 7 = 0111 . La nueva máquina genera el número 11 = 1011 . El número ganador será (7 Y 11) = (0111 Y 1011) = 0011 = 3 .

Con esta medida, la Lotería espera reducir los casos de reclamos fraudulentos, pero desafortunadamente un empleado de la compañía de la Lotería ha filtrado la siguiente información: la máquina vieja siempre generará un número entero no negativo menor que A y la nueva siempre generará un entero no negativo menor que B .

Catalina quiere ganar esta lotería y para darle una oportunidad se decidió a comprar todos los enteros no negativos menor que K .

Dado A , B y K , a Catalina le gustaría saber de cuántas maneras diferentes las máquinas pueden generar un par de números que la convertirán en una ganadora.

¿Podrías ayudarla?

Entrada

La primera línea de la entrada da el número de casos de prueba, las líneas T. T siguen, cada línea con tres números AB K.

Salida

Para cada caso de prueba, envíe una línea que contenga "Caso #x: y", donde x es el número de caso de prueba (a partir de 1) e y es el número de pares posibles que las máquinas pueden generar para que Catalina sea una ganadora.

Límites

1 ≤ T ≤ 100. Conjunto de datos pequeño

1 ≤ A ≤ 1000. 1 ≤ B ≤ 1000. 1 ≤ K ≤ 1000. Gran conjunto de datos

1 ≤ A ≤ 109. 1 ≤ B ≤ 109. 1 ≤ K ≤ 109. Muestra

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

En el primer caso de prueba, estos son los 10 pares posibles generados por la máquina antigua y la nueva, respectivamente, que la convertirán en una ganadora: <0,0>, <0,1>, <0,2>, <0,3> , <1,0>, <1,1>, <1,2>, <1,3>, <2,0> y <2,1>. Observe que <0,1> no es lo mismo que <1,0>. Además, aunque el par <2, 2> podría ser generado por las máquinas, Catalina no ganaría ya que (2 Y 2) = 2 y ella solo compró los números 0 y 1.

Aquí está el enlace para el problema real: https://code.google.com/codejam/contest/2994486/dashboard#s=p1

Este es el código de golf, por lo que gana el código más corto. Buena suerte

Ruby, 107

Esperaba que este fuera un programa mucho más corto.

gets
loop{a,b,k=gets.split.map &:to_i
puts"Case ##{$.-1}: #{[*0...a].product([*0...b]).count{|x,y|x&y<k}}"}

Explicación

• La primera línea de entrada puede ignorarse.
• $. es el último número de línea leído.
• [*0...x]es una forma rápida de convertir el Rangeen un Array. Utiliza el operador splat ( *). Tenga en cuenta que Rangees exclusivo (en ...lugar de ..).
• Array#counttoma un bloque. Solo contará los elementos para los cuales el bloque devuelve un valor verdadero.

APL (63)

Es la E / S la que cuesta mucho.

↑{a b k←¯1+⍳¨⎕⋄'Case #',(⍕⍵),': ',⍕+/∊k∊⍨a∘.{2⊥∧/⍺⍵⊤⍨10/2}b}¨⍳⎕

Explicación:

• {... }¨⍳⎕: lea un número N desde el teclado y ejecute la siguiente función para cada número del 1 al N.
• a b k←¯1+⍳¨⎕: Leer tres números desde el teclado, generar una lista de 0..n-1 para cada uno, y almacenar estos en a, b, y k.
• a∘.{... }b: para cada combinación de valores de ay b:
  • ⍺⍵⊤⍨10/2: obtenga la representación binaria de 10 bits para ambos valores (esto es suficiente dados los límites)
  • ∧/: y juntos todos los pares de bits
  • 2⊤: convertirlo de nuevo en un número
• k∊⍨: para cada uno de estos valores, pruebe si está en k
• +/: suma el resultado
• 'Case #',(⍕⍵),': ',⍕: genera la cadena de salida para este caso
• ↑: convierte el resultado en una matriz, por lo que cada cadena termina en una línea separada.

Prueba:

      ↑{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

Aquí está mi solución Golfscript (probablemente podría mejorarse):

n/(;0:m;{[~0:w.{{.2$&3$<w+:w;)}4$*;)0}5$*];'Case #'m):m': 'w n}%

Aquí está el pseudocódigo que utilicé para esto:

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

Asume una entrada válida.

CJam - 62

Probablemente podría mejorarse; este es solo un puerto de mi respuesta Golfscript.

qN/(;{[~0_{{_2$&3$<V+:V;)}4$*;)0}5$*];"Case #"T):T": "V0:V;N}%

Rubí - 145

Todavía estoy aprendiendo Ruby, así que probablemente haya una forma más corta de hacerlo.

(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}"}

Sin golf :

( 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}"
}

J, 90 (70)

E / S a stdin / stdout, funciona como un script ( 90 ).

,&LF@('Test #'&,)"1@(":@#,{:)\@:}.@:(': '&,"1)@(+/@,@(>`(17 b./&i.)/@|.)&.".;._2)&.stdin''

Entrada en stdin, salida implícita en REPL (similar a APL, creo) ( 70 ).

'Test #',"1(":@#,{:)\}.': ',"1+/@,@(>`(17 b./&i.)/@|.)&.".;._2 stdin''

Ergh, J no es bueno en los requisitos de E / S como estos.

Para los curiosos, la parte que hace el trabajo pesado es +/@,@(>`(17 b./&i.)/@|.)&."., lo que resuelve una sola línea del problema (tomar y devolver una cadena).

CJAM - 57

0li{)"Case #"\':Sl~:K;L\{(2$,{1$&@+\}%~}h;\;{K<},,N4$}\*;

Creo que esto se puede jugar más golf.

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

Salida:

Case #1: 10
Case #2: 16
Case #3: 52
Case #4: 2411
Case #5: 14377