昨日の続き
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