Problem:


		
Problem B: Make Purse Light

		

			Mr. Bill は店で買い物をしている。 彼の財布にはいくらかの硬貨（10 円玉、50 円玉、100 円玉、500 円玉）が入っているが、彼は今この小銭をできるだけ消費しようとしている。 つまり、適切な枚数の硬貨によって品物の代金を払うことで、釣り銭を受け取った後における硬貨の合計枚数を最小にしようとしている。
		

		

			幸いなことに、この店の店員はとても律儀かつ親切であるため、釣り銭は常に最適な方法で渡される。 したがって、例えば 1 枚の 500 円玉の代わりに 5 枚の 100 円玉が渡されるようなことはない。 また、例えば 10 円玉を 5 枚出して、50 円玉を釣り銭として受け取ることもできる。 ただし、出した硬貨と同じ種類の硬貨が釣り銭として戻ってくるような払いかたをしてはいけない。 例えば、10 円玉を支払いの際に出したにも関わらず、別の 10 円玉が釣り銭として戻されるようでは、完全に意味のないやりとりが発生してしまうからである。
		

		

			ところが Mr. Bill は計算が苦手なため、実際に何枚の硬貨を使用すればよいかを彼自身で求めることができなかった。 そこで、彼はあなたに助けを求めてきた。 あなたの仕事は、彼の財布の中にある硬貨の枚数と支払い代金をもとに、使用すべき硬貨の種類と枚数を求めるプログラムを書くことである。なお、店員はお釣りに紙幣を使用することはない。
		
Input

		

			入力にはいくつかのテストケースが含まれる。
		

		

			それぞれのテストケースは 2 行から構成される。 1 行目には Mr. Bill の支払い金額を円単位で表した 1 つの整数が含まれている。 2 行目には 4 つの整数が含まれており、それらは順に財布の中にある 10 円玉、50 円玉、100 円玉、500 円玉の枚数をそれぞれ表す。
		

		

			支払い金額は常に 10 円単位である。 すなわち、支払い金額の一円の位は常に 0 である。 また財布の中に、同じ種類の硬貨は最大で 20 枚までしかないと仮定してよい。 支払いが不可能なケースが入力中に与えられることはない。
		

		

			入力の終了は単一の 0 を含む行によって表される。
		

		
Output

		

			それぞれのテストケースについて、Mr. Bill が使用すべき硬貨の種類と枚数を出力せよ。
		

		

			出力の各行には 2 つの整数 ci 、ki が含まれる。これは支払いの際に ci 円玉を ki 枚使用することを意味している。
			複数種類の硬貨を使用する場合は、ci の小さいほうから順に、必要な行数だけ出力を行うこと。 下記の出力例を参考にせよ。
		

		

			なお、出力には余計なスペースを含めてはならない。 連続するテストケースの間は空行で区切ること。
		

		
Sample Input

		

160
1 1 2 0
160
1 0 2 10
0

		
Output for the Sample Input

		

10 1
50 1
100 1

10 1
100 2

1番目のデータ がある。
		

-->
		


Sample input:
160
1 1 2 0
160
1 0 2 10
0


Sample output:
10 1
50 1
100 1

10 1
100 2

Submission status: Runtime Error

Solution code:
def coin(n):
    return [(n % 500) / 100, (n % 100) / 50, (n % 50) / 10, n / 500]

ret = ''

while True:
    n = int(raw_input())
    if n == 0:
        break
    c10, c50, c100, c500 = map(int, raw_input().split())
    m = 20000
    result = []
    money = 500 * l + 100 * k + 50 * j + 10 * i
    result = coin(money - n)
    if result[0] - c10 != 0:
        ret += '10 ' + str(result[0] - c10)
        ret += '\n'
    if result[1] - c50 != 0:
        ret += '50 ' + str(result[1] - c50)
        ret += '\n'
    if result[2] - c100 != 0:
        ret += '100 ' + str(result[2] - c100)
        ret += '\n'
    if result[3] - c500 != 0:
        ret += '500 ' + str(result[3] - c500)
        ret += '\n'
    ret += '\n'

print ret[:-1]

Submission status: Runtime Error

Solution code:
def coin(n):
    return [(n % 500) / 100, (n % 100) / 50, (n % 50) / 10, n / 500]

ret = ''

while True:
    n = int(raw_input())
    if n == 0:
        break
    c10, c50, c100, c500 = map(int, raw_input().split())
    m = 20000
    result = []
    money = 500 * l + 100 * k + 50 * j + 10 * i

Submission status: Runtime Error

Solution code:
from itertools import product
L = [10, 50, 100, 500]

def solve():
    #print N
    ans = [[20] * 4, [20] * 4]
    for c in product(*[range(N[i] + 1) for i in xrange(4)]):
        #print "out", c
        r = calc(c)
        #print "in", r
        if check(c, r):
            ans = min([r, c], ans, key = lambda x: sum(x[0]))
            #print "check", ans
        #print
    return ans[1]

def calc(N):    
    r = sum(L[i] * N[i] for i in xrange(4)) - M
    #print r
    if r < 0:
        return [-1] * 4
    ret = [0] * 4
    for i in xrange(3, -1, -1):
        ret[i] += r / L[i]
        r -= ret[i] * L[i]
    return ret

def check(N1, N2):
    if N2[0] == -1:
        return False
    for c1, c2 in zip(N1, N2):
        if c1 > 0 and c2 > 0:
            return False
    return True

M = int(raw_input())
while True:
    N = map(int, raw_input().split())
    for i, n in zip(L, solve()):
        if n == 0:
            continue
        print i, n
    M = int(raw_input())
    if M == 0:
        break
    print

Submission status: WA: Presentation Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from itertools import product
coins = [10,50,100,500]

def coin_count(num):
    count = 0
    for coin in sorted(coins,reverse = True):
        count += num // coin
        num -= (num // coin)*coin
    return count

while True:
    price = int(input())
    if price == 0:
        break
    has = list(map(int,input().split()))
    sum_coins = list(map(lambda x: x[0]*x[1], zip(has,coins)))


    change = (sum(sum_coins) - price)
    surplus = [change % 50 // 10, change % 100 // 50, change % 500 // 100, change // 500]

    for i in range(4):
        if has[i] > surplus[i]:
            print(coins[i],has[i] - surplus[i])
    print()

Submission status: WA: Presentation Error

Solution code:
def opt_change(n):
	change = [0,0,0,0]
	purse = (10,50,100,500)
	for i in range(4):
		change[3-i] = n / purse[3-i]
		n = n % purse[3-i]
	return change

while 1:
	price = int(raw_input())
	if price == 0:
		break
	purse_num = map(int,raw_input().split())
	purse = [10,50,100,500]
	own = sum([purse[i] * purse_num[i] for i in range(4)])
	result = opt_change(own-price)
	for i in range(4):
		num = 0 if purse_num[i] <= result[i] else (purse_num[i] - result[i])
		if num != 0:
			print purse[i], num
	print ""

Submission status: WA: Presentation Error

Solution code:
c = [10, 50, 100, 500]

while True:
	n = int(input())
	if n == 0:
		break
	m = list(map(int, input().split()))
	r = [0]*4
	n = sum(x[0]*x[1] for x in zip(m, c)) - n
	for i in range(4)[::-1]:
		r[i] = n // c[i]
		n -= r[i] * c[i]

	for i in range(4):
		if m[i] > r[i]:
			print('{} {}'.format(c[i], m[i]-r[i]))
	print()

Submission status: WA: Presentation Error

Solution code:
while True:
    n = input()

    if n == 0:
        break

    y10, y50, y100, y500 = map(int, raw_input().split())
    Sum = 10 * y10 + 50 * y50 + y100 * 100 + y500 * 500

    while Sum - 500 >= n:
        Sum -= 500
        y500 -= 1
    while Sum - 100 >= n:
        Sum -= 100
        y100 -= 1
    while Sum - 50 >= n:
        Sum -= 50
        y50 -= 1
    while Sum - 10 >= n:
        Sum -= 10
        y10 -= 1

    if y10 > 0:
        print 10, y10
    if y50 > 0:
        print 50, y50
    if y100 > 0:
        print 100, y100
    if y500 > 0:
        print 500, y500

Submission status: WA: Presentation Error

Solution code:
coins = [10, 50, 100, 500]

while True:
  P = int(raw_input())
  if P==0: break
  else: print ""
  c = map(int, raw_input().split())
  rest = -P
  for i in xrange(len(coins)):
    rest += coins[i] * c[i]
  k = [0]*len(coins)
  for i in xrange(len(coins)):
    idx = len(coins)-1-i
    k[idx] = c[idx] - (rest / coins[idx])
    rest -= coins[idx] * (c[idx] - k[idx])
  for i in xrange(len(coins)):
    if k[i] > 0:
      print "%d %d" % (coins[i], k[i])

Submission status: WA: Presentation Error

Solution code:
from __future__ import print_function

p = [10, 50, 100, 500]

while True:
    n = int(raw_input())
    if n == 0:
        break

    m = [int(_) for _ in raw_input().split()]

    s = sum(pi * mi for pi, mi in zip(p, m))
    r = s - n
    for i in xrange(3, -1, -1):
        pi = p[i]
        ni = r / pi
        m[i] -= ni
        r -= ni * pi

    for pi, mi in zip(p, m):
        if mi > 0:
            print(pi, mi)

    print()

Submission status: WA: Presentation Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Python 2 ??????????????§??????
# URL : http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2007

from __future__ import print_function

p = [10, 50, 100, 500]

first = True

while True:
    n = int(raw_input())
    if n == 0:
        break

    if not first:
        print()
        first = False

    m = [int(_) for _ in raw_input().split()]

    s = sum(pi * mi for pi, mi in zip(p, m))
    r = s - n
    for i in xrange(3, -1, -1):
        pi = p[i]
        ni = r / pi
        m[i] -= ni
        r -= ni * pi

    for pi, mi in zip(p, m):
        if mi > 0:
            print(pi, mi)

Submission status: WA: Presentation Error

Solution code:


def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))

if __name__ == "__main__":

    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)

Submission status: WA: Presentation Error

Solution code:

def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))

if __name__ == "__main__":

    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
    print('')

Submission status: WA: Presentation Error

Solution code:
# http://www.deqnotes.net/acmicpc/p0006/
import re


# def check_testcase():
#     with open('./2007-input.txt') as f:
#         input_testcase = f.read()
#     with open('./2007-output.txt') as f:
#         pre_output_testcase = f.read()
#     input_testcase = input_testcase.splitlines()
#     pre_output_testcase = re.findall('([0-9]*\s[0-9]*)(?=\n)', pre_output_testcase)
#
#     output_testcase = [''] * int(len(input_testcase) / 2)
#     cnt = 0
#     for x in pre_output_testcase:
#         if x == '\n':
#             cnt += 1
#         else:
#             output_testcase[cnt] = output_testcase[cnt] + x + '\n'
#
#     for i in range(0, len(output_testcase), 1):
#         fee = int(input_testcase[i * 2])
#         coin = [int(x) for x in input_testcase[i * 2 + 1].split(' ')]
#         coin_value = [10, 50, 100, 500]
#
#         result = back_oturigation(fee, coin_value, coin)
#
#         if result == output_testcase[i]:
#             print("PASS")
#         else:
#             import ipdb;
#             ipdb.set_trace()


def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))

if __name__ == "__main__":

    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
        print('')

Submission status: WA: Presentation Error

Solution code:

def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))

if __name__ == "__main__":

    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
        print('')

Submission status: WA: Presentation Error

Solution code:
while 1:
    m = int(raw_input())
    if m == 0: break
    cm = [10, 50, 100, 500]
    c = map(int, raw_input().split())
    mintn = 81
    fc = [0 for i in xrange(4)]
    mc = [0 for i in xrange(4)]
    t = 0
    for i in xrange(4):
        t += c[i]*cm[i]
        ch = t-m
    for i in xrange(3,-1,-1):
        while(ch >= cm[i]):
            ch -= cm[i]
            mc[i] += 1
    for i in xrange(4):
        fc[i] = c[i] - mc[i]
        if fc[i] < 0: fc[i] = 0
    for i in xrange(4):
        if fc[i] != 0: print "%d %d" % (cm[i], fc[i])
    print ''

Submission status: WA: Presentation Error

Solution code:
second = False

while True:
    if second: print ""
    second = True
    s = input()
    if s==0: break
    ls = map(int, raw_input().split())
    have = {}

    have[10], have[50], have[100], have[500] = ls
    have_c = sum(ls)

    ans = {}
    ans_c = 1<<30

    for i10 in range(have[10]+1):
        for i50 in range(have[50]+1):
            for i100 in range(have[100]+1):
                for i500 in range(have[500]+1):
                    pay = i10*10 + i50*50 + i100*100 + i500*500
                    if pay < s: continue
                    pay_c = i10 + i50 + i100 + i500
                    change = pay - s
                    change_c = change/500
                    change%=500
                    change_c += change/100
                    change%=100
                    change_c += change/50
                    change%=50
                    change_c += change/10
                    t_c = have_c - pay_c + change_c
                    if ans_c > t_c:
                        ans[10], ans[50], ans[100], ans[500] = i10, i50, i100, i500
                        ans_c = t_c

    if ans[10] is not 0: print 10, ans[10]
    if ans[50] is not 0: print 50, ans[50]
    if ans[100] is not 0: print 100, ans[100]
    if ans[500] is not 0: print 500, ans[500]