gistfile1.rb

# 1B problem B 2013 Google Code Jam
# adapted answer from 'dolphinigle'

gets.to_i.times do |ca|
  my, n = gets.split(" ").map(&:to_i)
  motes = gets.split(" ").map(&:to_i).sort

  best = motes.length # all delete
  if my == 1
    puts "Case ##{ca+1}: #{best}" 
  else
    add = 0
    motes.each_with_index do |o, i|
      # just eat and go next
      my += o and next if my > o 

      # stop here, update the best before add
      # important step! as it will catch the case where add and delete are mixed together
      best = [best, add + n - i].min 

      # add
      my += my - 1 and add += 1  while o >= my

      my += o
    end
    best = [best, add].min
    puts "Case ##{ca+1}: #{best}"
  end
end