Codejam 2014, Round1C, Problem A

partelf.rb

# Problem description: https://code.google.com/codejam/contest/3004486/dashboard#s=p0

powers = [1]
nr = 1
41.times do
  nr = nr * 2
  powers << nr
end

T = gets.to_i
for t in 1..T
  p, q = gets.chomp.split('/').map { |n| n.to_i }
  g = p.gcd(q)
  p = p/g
  q = q/g

  x = 100
  for i in 0..41
    x = i if powers[i] == q
  end

  y = 0
  for i in 0..41
    break if powers[i] > p
    y = i
  end

  if x > 40 or y > 40
    ans = 'impossible'
  else
    ans = x - y
  end

  puts "Case ##{t}: #{ans}"
end