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: Accepted

Solution code:
clst = [10,50,100,500]
def sgn(t):
    for I in range(0,4):
        if clst[I] == t:
            return I
def cnt(l1,l2,N): 
    s = sgn(l1[N])
    l2[s] = l2[s] + 1
def shiharai(bill,purse):
    B = bill
    lst1 = []
    lst2 = [0]
    for i in range(0,4):
        for j in range(0,purse[i]):
            lst1.append(clst[i])
    lst2[0] = lst1[0]
    for i in range(1,len(lst1)):
        k = lst1[i] + lst2[i-1]
        lst2.append(k)
    pay = [0,0,0,0]
    while B > 0:
        i = 0
        while lst2[i] < B:
            i = i + 1
        if lst2[i] == B:
            for j in range(0,i+1):
                cnt(lst1,pay,j)
                B = B - lst1[j]
        else:
            cnt(lst1,pay,i)
            B = B - lst1[i]
    for i in range(4):
        purse[i] = purse[i] - pay[i]
    purse[0] = purse[0] - B//10
    return purse
def exchng(purse,n,r):
    while purse[n] >= r:
        purse[n] = purse[n] - r
        purse[n+1] = purse[n+1] + 1
def ryogae(purse):
    exchng(purse,0,5)
    exchng(purse,1,2)
    exchng(purse,2,5)
    return purse
L = 0
while True:
    bill = int(input().strip())
    if bill == 0:
        break
    if L != 0:
        print()
    lst = list(map(int,input().strip().split(" ")))
    purse = [0,0,0,0]
    for A in range(0,4):
        purse[A] = lst[A]
    purse = shiharai(bill,purse)
    purse = ryogae(purse)
    shouldpay = [0,0,0,0]
    for B in range(0,4):
        if lst[B] > purse[B]:
            shouldpay[B] = lst[B] - purse[B]
    for i in range(0,4):
        if shouldpay[i] != 0:
            print(clst[i],shouldpay[i])
    L = L + 1

Submission status: Accepted

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

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        kind = [10, 50, 100, 500]
        first = True
        while True:            
            payment = input()
            if payment == 0:
                break
            p = map(int, raw_input().split())

            change = sum(i * j for i, j in zip(kind, p)) - payment
            c = [0 for i in range(4)]
            tmp = change
            for i in reversed(range(4)):
                c[i] = tmp / kind[i]
                tmp %= kind[i]
            ans = [max(0, i - j) for i, j in zip(p, c)]
            if first:
                first = False
            else:
                print
            for i in range(4):
                if ans[i] == 0:
                    continue
                print str(kind[i]) + ' ' + str(ans[i])
        
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
coins = [10, 50, 100, 500]
def s(value):
    a = list(map(int, input().split()))
    pay = [0, 0, 0, 0]
    ms = sum([a[i] * coins[i] for i in range(4)]) - value
    m = [ms % 50 // 10, ms % 100 // 50, ms % 500 // 100, ms // 500]
    for cc, aa, mm in zip(coins, a, m):
        if aa > mm:
            print(cc, aa - mm)

s(int(input()))
while True:
    value = int(input())
    if not value:
        break
    print()
    s(value)

Submission status: Accepted

Solution code:
coins = (10,50,100,500)
isfirst = True
while 1:
    cost = int(raw_input())
    if cost == 0: break
    if not isfirst: print
    have = map(int,raw_input().split())

    budget = sum(i*j for i,j in zip(coins,have))
    change = budget-cost

    ans = [0]*4
    for i in reversed(range(4)):
        c = change/coins[i]
        ans[i] = c
        change -= c*coins[i]

    for i in range(4):
        if have[i]-ans[i] <= 0: continue
        print coins[i],have[i]-ans[i]

    isfirst = False

Submission status: Accepted

Solution code:
coins = (10,50,100,500)
isfirst = True
while 1:
    cost = int(raw_input())
    if cost == 0: break
    if not isfirst: print
    have = map(int,raw_input().split())

    budget = sum(i*j for i,j in zip(coins,have))
    change = budget-cost

    ret = [0]*4
    for i in reversed(range(4)):
        c = change/coins[i]
        ret[i] = c
        change -= c*coins[i]

    for i in range(4):
        if have[i]-ret[i] <= 0: continue
        print coins[i],have[i]-ret[i]

    isfirst = False

Submission status: Accepted

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

flag = True
while True:
    price = int(input())
    if price == 0:
        break

    if flag:
        flag = False
    else:
        print()

    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])

Submission status: Accepted

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

flag = 0
while 1:
	price = int(raw_input())
	if price == 0:
		break
	if flag == 0:
		flag = 1
	else :
		print "" 
	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

Submission status: Accepted

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

n = int(raw_input())
cnt = 0
while n!=0:
    if cnt > 0:
        print
    (c10, c50, c100, c500) = map(int, raw_input().split())
    Sum = 10*c10+50*c50+100*c100+500*c500
    while Sum-500 >= n:
        Sum -= 500
        c500 -= 1
    while Sum-100 >= n:
        Sum -= 100
        c100 -= 1
    while Sum-50 >= n:
        Sum -= 50
        c50 -= 1
    while Sum-10 >= n:
        Sum -= 10
        c10 -= 1

    if c10 > 0:
        print 10, c10
    if c50 > 0:
        print 50, c50
    if c100 > 0:
        print 100, c100
    if c500 > 0:
        print 500, c500

    n = int(raw_input())
    cnt += 1

Submission status: Accepted

Solution code:
ansOut = []
coin = [10, 50, 100, 500]
while True:
    price = int(input())
    if price == 0:
        break
    cash = list(map(int, input().split()))
    sumCash = sum(c * n for c, n in zip(coin, cash))
    change = sumCash - price
    changeCoins = [(change % 50) // 10, (change % 100) // 50, (change % 500) // 100, change // 500]

    out = []
    for i in range(4):
        if cash[i] > changeCoins[i]:
            out.append('{} {}'.format(coin[i], cash[i] - changeCoins[i]))
    ansOut.append('\n'.join(out))
print('\n\n'.join(ansOut))

Submission status: Accepted

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

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]

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

Submission status: Accepted

Solution code:
cnt = 0
while True:
    n = input()

    if n == 0:
        break

    if cnt > 0:
        print

    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

    cnt += 1

Submission status: Accepted

Solution code:
def best_coins(r, i=3, bc=[0] * 4):
    global coins
    bc[i], r = divmod(r, coins[i])
    if i:
        best_coins(r, i - 1, bc)
    return bc


coins = (10, 50, 100, 500)
output = []

while True:
    price = int(input())
    if not price:
        break
    pocket = tuple(map(int, input().split()))
    remains = best_coins(sum(c * p for c, p in zip(coins, pocket)) - price)
    output.append('\n'.join('{} {}'.format(c, p - r) for c, p, r in zip(coins, pocket, remains) if p - r > 0))

print('\n\n'.join(output))

Submission status: Accepted

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

is_beginning = True
while True:
  P = int(raw_input())
  if P==0: break
  else:
    if is_beginning == False:
      print ""
    is_beginning = False
  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: Accepted

Solution code:
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()

    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)

    first = False

Submission status: Accepted

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__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        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: Accepted

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__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        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: Accepted

Solution code:
import math
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__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        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: Accepted

Solution code:
first = True
while True:
    P = int(input())
    if P== 0: break
    if first:
        first = False
    else:
        print('')
    c1,c2,c3,c4 = map(int,input().split())
    v = c1*10 + c2*50 + c3*100 + c4*500
    n = c1 + c2 + c3 + c4
    ans = {}
    rem = v - P
    ans[10] = c1 - (rem//10) % 5
    ans[50] = c2 - (rem//50) % 2
    ans[100] = c3 - (rem//100) % 5
    ans[500] = c4 - rem//500
    for k,v in sorted(ans.items()):
        if v <= 0: continue
        print('{0} {1}'.format(k,v))

Submission status: Accepted

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

while True:
    y = int(input())
    if y == 0:
        break

    if not first:
        print()
    else:
        first = False

    coin = list(map(int, input().split()))
    coinsum = sum(coin[i] * c[i] for i in range(4))
    rem = coinsum - y
    change = [rem % c[i + 1] // c[i] for i in range(4)]

    for i in range(4):
        if change[i] < coin[i]:
            print(c[i], coin[i] - change[i])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    rr = []

    t = [10,50,100,500]

    while True:
        n = I()
        if n == 0:
            break
        a = LI()
        sm = [0] * 4
        sm[0] = t[0] * a[0]
        for i in range(1,4):
            sm[i] = sm[i-1] + t[i] * a[i]

        tr = []
        for i in range(3,-1,-1):
            if i == 0 and n > 0:
                tr.append('{} {}'.format(t[i], n//t[i]))
                break
            tn = n - sm[i-1]
            c = (tn + t[i] - 1) // t[i]
            n -= t[i] * c
            if c > 0:
                tr.append('{} {}'.format(t[i], c))
        if len(rr) > 0:
            rr.append('')
        rr += tr[::-1]



    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
loop = False
while 1:
    m = int(raw_input())
    if m == 0: break
    if loop is True: print ''
    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])
    loop = True

Submission status: Accepted

Solution code:
P=(10,50,100,500)
price=input()
while True:
    L=map(int,raw_input().split())
    sumMoney=sum(map(lambda x,y:x*y,L,P))
    extra=sumMoney-price
    A=[0]*4
    for i in range(4)[::-1]:
        c=extra/P[i]
	A[i]=c
        extra-=c*P[i]
    for i in range(4):
        if L[i]-A[i]>0:
	    print P[i],L[i]-A[i]
    price=input()
    if price==0:break
    print

Submission status: Accepted

Solution code:
second = False

while True:
    s = input()
    if s==0: break
    if second: print ""
    second = True
    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]

Submission status: Accepted

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

def solve():
    r = calc(N)
    return map(lambda a, b: max(0, a - b), N, r)

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

M = int(raw_input())
while M != 0:
    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: Accepted

Solution code:
L = (10, 50, 100, 500)

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

M = int(raw_input())
while M != 0:
    N = map(int, raw_input().split())
    for i, n in zip(L, map(lambda a, b: max(0, a - b), N, calc(N))):
        if n == 0:
            continue
        print i, n
    M = int(raw_input())
    if M == 0:
        break
    print

Submission status: Accepted

Solution code:
L = (10, 50, 100, 500)
def calc():
    ret = [0] * 4
    r = sum(L[i] * N[i] for i in xrange(4)) - M
    for i in xrange(3, -1, -1):
        ret[i] += r / L[i]
        r -= ret[i] * L[i]
    return ret

M = int(raw_input())
while M != 0:
    N = map(int, raw_input().split())
    for i, n in zip(L, map(lambda a, b: max(0, a - b), N, calc())):
        if n == 0:
            continue
        print i, n
    M = int(raw_input())
    if M == 0:
        break
    print

Submission status: Accepted

Solution code:
#演習2-17

coins = [10, 50, 100, 500]
def solve(price):
    maisuu = list(map(int, input().split()))
    pay = [0, 0, 0, 0]
    otsuri = sum([maisuu[i] * coins[i] for i in range(len(coins))]) - price
    otsuri_maisuu = [otsuri % 50 // 10, otsuri % 100 // 50, otsuri % 500 // 100, otsuri // 500]
    for types, saifu, tsuri in zip(coins, maisuu, otsuri_maisuu):
        if saifu > tsuri:
            print(types, saifu - tsuri)
            
p = int(input())
solve(p)
while True:
    p = int(input())
    if not p:
        break
    print()
    solve(p)

Submission status: Accepted

Solution code:

coin=[10, 50, 100, 500, 500000]
first = True
while True:
    
    bill = int(input())
    if bill == 0:
        break;
    if not first:
        print()
    else:
        first = False
    posses = list(map(int, input().split()))
    Sumcoin= sum(coin[i] * posses[i] for i in range(4))
    change = Sumcoin - bill
    ChangeCoin = [change % coin[i+1] // coin[i] for i in range(4)]
    hand = [posses[i] - ChangeCoin[i] for i in range(4)]
    for i in range(4):
        if posses[i] > ChangeCoin[i]:
            print(coin[i], hand[i])

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    ans = ''
    
    while True:
        pay = int(f_i.readline())
        if pay == 0:
            break
        
        n10, n50, n100, n500 = map(int, f_i.readline().split())
        tot = n10 * 10 + n50 * 50 + n100 * 100 + n500 * 500
        
        chg = tot - pay
        tmp_ans = ''
        for coin, paid_num in zip((500, 100, 50, 10), (n500, n100, n50, n10)):
            chg_num, chg = divmod(chg, coin)
            
            ans_num = paid_num - chg_num
            if ans_num > 0:
                tmp_ans = f"{coin} {ans_num}\n" + tmp_ans
        
        ans += tmp_ans
        ans += '\n'
    
    print(ans.rstrip())

solve()

Submission status: Accepted

Solution code:
INF = 10 ** 15
MOD = 10 ** 9 + 7
money = (10,50,100,500)

def solve(N):
    coins = list(map(int,input().split()))
    tot = sum(coins[i]*money[i] for i in range(4))
    ans = [0] * 4
    tot -= N
    for i in range(3,-1,-1):
        X = tot//money[i]
        tot %= money[i]
        ans[i] = max(coins[i] - X,0)
    for i in range(4):
        if ans[i] == 0:
            continue
        print(money[i],ans[i])
    
def main():
    i = 0
    while True:
        N = int(input())
        if N == 0:
            break
        if i > 0:
            print('')
        i += 1
        solve(N)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

cnt = 0

while True:



    N = int(input())

    if N == 0:
        break

    if cnt != 0:
        print ("")
    cnt = 1

    A,B,C,D = map(int,input().split())

    mon = A * 10 + B * 50 + C * 100 + D * 500

    mon -= N

    d = mon // 500
    mon %= 500
    c = mon // 100
    mon %= 100
    b = mon // 50
    mon %= 50
    a = mon // 10

    if A-a > 0:
        print (10,A-a)
    if B-b > 0:
        print (50,B-b)
    if C-c > 0:
        print (100,C-c)
    if D-d > 0:
        print (500,D-d)

Submission status: Accepted

Solution code:
count = 0
while True:
    money = int(input())
    
    if money == 0:
        break
    
    if count > 0:
        print()
    
    coins = list(map(int,input().split()))
    
    needs = [0]*4
    yen = [10,50,100,500]

    summoney = coins[0]*yen[0] + coins[1]*yen[1] + coins[2]*yen[2] + coins[3]*yen[3]
    sur = summoney-money
    arr = [sur % 50// 10, sur %100// 50, sur % 500//100, sur // 500]    
    count +=1    
    for i in range(4):
        if coins[i] > arr[i]:
            print(yen[i],coins[i]-arr[i])

Submission status: Accepted

Solution code:
coin = [10,50,100,500,999999]
J = True
while True:
    n = int(input())
    if n == 0:
        break
    else:
        if not J:
            print()
        else:
            J = False
        L = list(map(int,input().split()))
        S = 10*L[0]+50*L[1]+100*L[2]+500*L[3]
        res = S-n #とりあえず硬貨を全部使ったものと仮定する
        change = [res%coin[i+1]//coin[i] for i in range(4)] #ここでお釣りとしてどの硬貨が何枚戻ってくるかを計算している
        
        for i in range(4):
            if change[i] < L[i]: #お釣りとして戻ってくる枚数の方が少なければ採用
                print(coin[i],L[i]-change[i])

Submission status: Accepted

Solution code:
money = [10,50,100,500]
c = 0
while True:
    ans = [0,0,0,0]
    amount = int(input())
    if amount == 0:
        break
    li = list(map(int,input().split())) #[a,b,c,d]
    change = []
    m = sum(li[i] * money[i] for i in range(4)) - amount
    lis = [(m % 50) // 10,(m % 100) // 50,(m % 500) // 100,m // 500]
    if c != 0:
        print()
    for i in range(4):
        if lis[i] < li[i]:
            print(money[i],li[i] - lis[i])
    c = 1

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
import copy

def main():
    flag = False
    while True:
        t = int(input())
        if not t:
            return
        if flag:
            print()
        flag = True
        cclist = (10,50,100,500)
        cc = list(map(int,input().split())) # 10 50 100 500
        csum = sum([c*n for c,n in zip(cclist,cc)])
        ots = otsuri(csum-t)
        for c,n1,n2 in zip(cclist, cc, ots):
            n = n1-n2
            if n <= 0:
                continue
            print(c,n)



def otsuri(n: int):
    res = [0]*4
    l = len(res)-1
    for i,c in enumerate([500,100,50,10]):
        res[l-i] = n // c
        n %= c
    return res


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
coins = [10, 50, 100, 500]
flg = 0
while 1:
    subtotal = int(input())
    if subtotal == 0:
        break
    if flg == 1:
        print()
    s_purse = list(map(int, input().split()))
    ans = [0, 0, 0, 0]
    for id in range(len(coins)):
        if id == 0: 
            continue
        payable = 0
        for i in range(len(coins) - id):
            payable += coins[i] * s_purse[i]
        while 1:
            if payable < subtotal:
                ans[-id] += 1
                s_purse[-id] -= 1
                subtotal -= coins[-id]
            else:
                break
    if 0 < subtotal:
        ans[0] += subtotal // 10
        s_purse[0] -= subtotal // 10
        subtotal -= coins[0] * ans[0]
    
    charge = -subtotal
    cha_coins = [charge//10, 0, 0, 0]
    hitsuyou = [5, 2, 5]

    for i in range(len(coins) - 1):
        if hitsuyou[i] <= cha_coins[i]:
            cha_coins[i + 1] = cha_coins[i] // hitsuyou[i]
            cha_coins[i] = cha_coins[i] % hitsuyou[i]
        if hitsuyou[i] <= cha_coins[i] + s_purse[i]:
            ans[i] += (cha_coins[i] + s_purse[i]) // hitsuyou[i] * hitsuyou[i] - cha_coins[i]
            cha_coins[i + 1] += (cha_coins[i] + s_purse[i]) // hitsuyou[i] 

    for i in range(len(coins)):
        if ans[i]:
            print(coins[i], int(ans[i]))
    flg = 1

Submission status: Accepted

Solution code:
coin = [10,50,100,500]
c = 0
while True:
    c += 1
    price = int(input())
    if (price == 0):
        break
    pur = list(map(int,input().split()))
    sumpur = sum(c*n for c,n in zip(coin, pur))
    change = sumpur - price
    afterpur = [(change%50)//10, (change%100)//50, (change%500)//100, change//500]
    if (c > 1):
        print()
    for i in range(4):
        if (afterpur[i] < pur[i]):
            print(coin[i], pur[i] - afterpur[i])

Submission status: Accepted

Solution code:
# coding: utf-8
f=0
while 1:
    n=int(input())
    if f and n!=0:
        print()
    f+=1
    if n==0:
        break
    a,b,c,d=map(int,input().split())
    mny=a*10+b*50+c*100+d*500
    mny=mny-n
    m500=mny//500
    mny-=500*(mny//500)
    m100=mny//100
    mny-=100*(mny//100)
    m50=mny//50
    mny-=50*(mny//50)
    m10=mny//10
    mny-=10*(mny//10)
    print('10 %d\n'%(max(a-m10,0)) if max(a-m10,0)!=0 else '', end='')
    print('50 %d\n'%(max(b-m50,0)) if max(b-m50,0)!=0 else '', end='')
    print('100 %d\n'%(max(c-m100,0)) if max(c-m100,0)!=0 else '', end='')
    print('500 %d\n'%(max(d-m500,0)) if max(d-m500,0)!=0 else '', end='')

Submission status: Runtime Error

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

while 1:
    cost = int(raw_input())
    if cost == 0: break
    c = map(int,raw_input().split())
    num = sum(c)

    mn = num
    ans = [0,0,0,0]
    for i in range(c[0]+1):
        for j in range(c[1]+1):
            for k in range(c[2]+1):
                for l in range(c[3]+1):
                    pay = 10*i+50*j+100*k+500*l
                    change = pay-cost
                    if change < 0: continue

                    tmp = [0,0,0,0]
                    for m in range(3,-1,-1):
                        while change-coins[m] >= 0:
                            change -= coins[m]
                            tmp[m] += 1
                    
                    for c1,c2 in zip([i,j,k,l],tmp):
                        if c1 > 0 and c2 > 0: break
                    else:
                        if num - (i+j+k+l) + sum(tmp) < mn:
                            mn = num - (i+j+k+l) + sum(tmp)
                            ans = [i,j,k,l]

    for ci,ki in zip(coins,ans):
        if ki == 0: continue
        print ci,ki
    print