good_luck.rb

# A solution for:
# https://code.google.com/codejam/contest/2418487/dashboard#s=p2
# Brute force, generating and checking all the cases.
# Works for the small input, does not work for the large one.

def get_all_n_numbers(n, m)
  if n == 1
    numbers = []
    for i in 2..m
      numbers << i.to_s
    end
    return numbers
  end

  numbers_1 = get_all_n_numbers(n-1, m)
  numbers = []
  for num in numbers_1
    for i in 2..m
      numbers << "#{num}#{i}"
    end
  end
  return numbers
end

def get_all_random_products(numbers, n)
  return [1, numbers[0].to_i ] if n == 1
  products_1 = get_all_random_products(numbers, n-1)
  products = []
  for p in products_1
    products << p
    products << p * numbers[n-1].to_i
  end
  return products
end

gets
puts "Case #1:"

r, n, m, k = gets.chomp.split.map { |x| x.to_i }
products_list = []
r.times do
  products_list << gets.chomp.split.map { |x| x.to_i }
end

all_n_numbers = get_all_n_numbers(n, m)
product_hash = {}
for numbers in all_n_numbers
  for product in get_all_random_products(numbers, n)
    product_hash[product] = [] if product_hash[product].nil?
    product_hash[product] << numbers
  end
end

for products in products_list
  possible_numbers = all_n_numbers
  for product in products
    possible_numbers = possible_numbers & product_hash[product]
  end
  puts possible_numbers.sample
end