昨日の続き

Make　Purse Light

　多分動くと思う。めちゃくちゃ遅い。

#
# Make Purse Light

def get_hanging(price, base_coins, payment)
  sum = 500 * payment[3] + 100 * payment[2] + 50 * payment[1] + 10 * payment[0]
  hanging = sum - price
  return false if hanging < 0

  hanging_coins = [0,0,0,0]
  hanging_coins[3], hanging = hanging.divmod(500)
  hanging_coins[2], hanging = hanging.divmod(100)
  hanging_coins[1], hanging = hanging.divmod(50)
  hanging_coins[0], hanging = hanging.divmod(10)
  return false if payment[0] != 0 and hanging_coins[0] != 0
  return false if payment[1] != 0 and hanging_coins[1] != 0
  return false if payment[2] != 0 and hanging_coins[2] != 0
  return false if payment[3] != 0 and hanging_coins[3] != 0

  return hanging_coins
end

def search_purse_light(price, base_coins, current)
  sum = 500 * current[3] + 100 * current[2] + 50 * current[1] + 10 * current[0]
  hanging = sum - price
  return [nil, nil] if hanging < 0

  least_coin_num = nil
  hanging_coins = get_hanging(price, base_coins, current)
  if hanging_coins
    least_coin_num = base_coins.inject(0) {|sum, n| sum + n } -
      current.inject(0) {|sum, n| sum + n } +
      hanging_coins.inject(0) {|sum, n| sum + n }
    best_payment = current
  end
  3.downto(0) do |index|
    (1..current[index]).to_a.each do |t|
      next_coins = current.dup
      next_coins[index] = (current[index] - t)
      payment, coin_num = search_purse_light(price, base_coins, next_coins)
      if payment and (least_coin_num.nil? or coin_num < least_coin_num)
        best_payment , least_coin_num = payment, coin_num
      end
    end
  end
  [best_payment, least_coin_num]
end

def main
  results = []
  loop do
    price = readline.to_i
    break if price == 0
    coins = readline.split(/\s/).map{|n| n.to_i }
    results << search_purse_light(price, coins, coins)
  end
  results.each do |result|
    coins = result[0]
    puts "10 #{coins[0]}" if coins[0] != 0
    puts "50 #{coins[1]}" if coins[1] != 0
    puts "100 #{coins[2]}" if coins[2] != 0
    puts "500 #{coins[3]}" if coins[3] != 0
  end
end

main