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:
# 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__":
    total_fee = int(input('total_fee:'))

    while (total_fee != 0):
        coins = input('total_coins:')
        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: Runtime 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__":
    total_fee = int(input('total_fee:'))

    while (total_fee != 0):
        coins = input('total_coins:')
        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: Runtime Error

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


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
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = all - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in reversed(range(0,len(coin_values))):
        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: Runtime Error

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

def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = all - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in reversed(range(0,len(coin_values))):
        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: Runtime Error

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

def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1
    coin_values=numpy.array(coin_values)
    coin_nums=numpy.array(coin_nums)
    all = numpy.dot(coin_values, coin_nums)
    oturi = all - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in reversed(range(0,len(coin_values))):
        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: Runtime Error

Solution code:
import numpy

def back_oturigation(fee, coin_values, coin_nums):

    coin_values=numpy.array(coin_values)
    coin_nums=numpy.array(coin_nums)
    all = numpy.dot(coin_values, coin_nums)
    oturi = all - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    for i in reversed(range(0,len(coin_values))):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    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: Runtime Error

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


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
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = int(all - fee)

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in reversed(range(0,len(coin_values))):
        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: Runtime Error

Solution code:
import numpy as np
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: Runtime Error

Solution code:
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = int(all - 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: Runtime Error

Solution code:
import numpy
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = int(all - 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: Runtime Error

Solution code:
import math
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = int(all - 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: Runtime Error

Solution code:
def calc(c1,c2,c3,c4):
    return c1*10 + c2*50 + c3*100 + c4*500

def coindiff(p,c1,c2,c3,c4):
    n = c1+c2+c3+c4
    over = calc(c1,c2,c3,c4) - p
    n -= (over%50) // 10
    n -= (over%100) // 50
    n -= (over%500) // 100
    n -= over // 500
    return n

while True:
    N = int(input())
    if N == 0: break
    c1,c2,c3,c4 = map(int,input().split())
    s1 = (N//10) % 5
    maxdiff = -9999999
    ans = None
    for n1 in range(s1,c1+1,5):
        for n2 in range(c2+1):
            for n3 in range(c3+1):
                rem = (N - n1*10 - n2*50 - n3*100)
                n4 = max(0, (rem-1)//500 + 1)
                d = coindiff(N,n1,n2,n3,n4)
                if d > maxdiff:
                    maxdiff = d
                    ans = {10:n1,50:n2,100:n3,500:n4}
    for k,v in sorted(ans.items()):
        print('{0} {1}'.format(k, v))
    print('')

Submission status: Runtime Error

Solution code:
def calc(c1,c2,c3,c4):
    return c1*10 + c2*50 + c3*100 + c4*500

def coindiff(p,c1,c2,c3,c4):
    n = c1+c2+c3+c4
    over = calc(c1,c2,c3,c4) - p
    n -= (over%50) // 10
    n -= (over%100) // 50
    n -= (over%500) // 100
    n -= over // 500
    return n

while True:
    N = int(input())
    if N == 0: break
    c1,c2,c3,c4 = map(int,input().split())
    s1 = (N//10) % 5
    maxdiff = -9999999
    ans = None
    for n1 in range(s1,c1+1,5):
        for n2 in range(c2+1):
            for n3 in range(c3+1):
                rem = (N - n1*10 - n2*50 - n3*100)
                n4 = max(0, (rem-1)//500 + 1)
                d = coindiff(N,n1,n2,n3,n4)
                if d > maxdiff:
                    maxdiff = d
                    ans = {10:n1,50:n2,100:n3,500:n4}
    for k,v in sorted(ans.items()):
        if v == 0: continue
        print('{0} {1}'.format(k, v))
    print('')

Submission status: Runtime Error

Solution code:
def calc(c1,c2,c3,c4):
    return c1*10 + c2*50 + c3*100 + c4*500

def coindiff(p,c1,c2,c3,c4):
    n = c1+c2+c3+c4
    over = calc(c1,c2,c3,c4) - p
    n -= (over%50) // 10
    n -= (over%100) // 50
    n -= (over%500) // 100
    n -= over // 500
    return n

first = True
while True:
    N = int(input())
    if N == 0: break
    if first:
        first = False
    else:
        print('')
    c1,c2,c3,c4 = map(int,input().split())
    s1 = (N//10) % 5
    maxdiff = -9999999
    ans = None
    for n1 in range(s1,c1+1,5):
        for n2 in range(c2+1):
            for n3 in range(c3+1):
                rem = (N - n1*10 - n2*50 - n3*100)
                n4 = max(0, (rem-1)//500 + 1)
                d = coindiff(N,n1,n2,n3,n4)
                if d > maxdiff:
                    maxdiff = d
                    ans = {10:n1,50:n2,100:n3,500:n4}
    for k,v in sorted(ans.items()):
        if v == 0: continue
        print('{0} {1}'.format(k, v))

Submission status: Runtime Error

Solution code:
def calc(c1,c2,c3,c4):
    return c1*10 + c2*50 + c3*100 + c4*500

def coindiff(p,c1,c2,c3,c4):
    n = c1+c2+c3+c4
    over = calc(c1,c2,c3,c4) - p
    n -= (over%50) // 10
    n -= (over%100) // 50
    n -= (over%500) // 100
    n -= over // 500
    return n

first = True
while True:
    N = int(input())
    if N == 0: break
    if first:
        first = False
    else:
        print('')
    c1,c2,c3,c4 = map(int,input().split())
    s1 = (N//10) % 5
    maxdiff = -9999999
    ans = None
    for n1 in range(s1,c1+1,5):
        for n2 in range(c2+1):
            rem2 = N - n1*10 - n2*50
            s3 = ((rem2-1)//100 + 1) % 5
            for n3 in range(s3,c3+1,5):
                rem3 = rem2 - n3*100
                n4 = max(0, (rem3-1)//500 + 1)
                d = coindiff(N,n1,n2,n3,n4)
                if d > maxdiff:
                    maxdiff = d
                    ans = {10:n1,50:n2,100:n3,500:n4}
    for k,v in sorted(ans.items()):
        if v == 0: continue
        print('{0} {1}'.format(k, v))

Submission status: Runtime Error

Solution code:
while 1:
    n=int(input())
    if not n:break
    a,b,c,d=map(int,input().split())
    y=(10,50,100,500)
    l=[[i,j,k,l] for i in range(a+1) for j in range(b+1) for k in range(c+1) for l in range(d+1) if i*10+j*50+k*100+l*500==n]
    t=sorted(l,key=lambda x:sum(x))[-1]
    [print(i,j) for (i,j) in zip(y,t) if j]

Submission status: Runtime Error

Solution code:
while 1:
    n=int(input())
    if not n:break
    a,b,c,d=map(int,input().split())
    y=(10,50,100,500)
    l=[[i,j,k,l] for i in range(a+1) for j in range(b+1) for k in range(c+1) for l in range(d+1) if i*10+j*50+k*100+l*500==n]
    t=sorted(l,key=lambda x:sum(x))[-1]
    [print(i,j) for (i,j) in zip(y,t) if j]
    print()

Submission status: Runtime Error

Solution code:
while 1:
    n=int(input())
    if not n:break
    a,b,c,d=map(int,input().split())
    y=(10,50,100,500)
    l=[[i,j,k,l] for i in range(a+1) for j in range(b+1) for k in range(c+1) for l in range(d+1) if i*10+j*50+k*100+l*500==n]
    t=sorted(l,key=lambda x:sum(x))[-1]
    es=[a-t[0],b-t[1],c-t[2],d-t[3]]
    print(es)
    print(es)

Submission status: Runtime Error

Solution code:
while 1:
    n=int(input())
    if not n:break
    a,b,c,d=map(int,input().split())
    y=(10,50,100,500)
    l=[[i,j,k,l] for i in range(a+1) for j in range(b+1) for k in range(c+1) for l in range(d+1) if i*10+j*50+k*100+l*500==n]
    t=sorted(l,key=lambda x:sum(x))[-1]
    es=[((a-t[0])//5)*5,((b-t[1])//2)*2,((c-t[2])//5)*5,0]
    [print(i,j+k) for (i,j,k) in zip(y,t,es) if j+k]

Submission status: Runtime Error

Solution code:
while 1:
    n=int(input())
    if not n:break
    a,b,c,d=map(int,input().split())
    y=(10,50,100,500)
    l=[[i,j,k,l] for i in range(a+1) for j in range(b+1) for k in range(c+1) for l in range(d+1) if i*10+j*50+k*100+l*500==n]
    t=sorted(l,key=lambda x:sum(x))[-1]
    es=[((a-t[0])//5)*5,((b-t[1])//2)*2,((c-t[2])//5)*5,0]
    [print(i,j+k) for (i,j,k) in zip(y,t,es) if j+k]
    print()

Submission status: Runtime 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)]
    for i in xrange(c[0]+1):
        for j in xrange(c[1]+1):
            for k in xrange(c[2]+1):
                for l in xrange(c[3]+1):
                    t = i*cm[0] + j*cm[1] + k*cm[2] + l*cm[3]
                    if t >= m:
                        mc = [0 for n in xrange(4)]
                        mc = [c[0]-i,c[1]-j,c[2]-k,c[3]-l]
                        ch = t-m
                        for n in xrange(3,-1,-1):
                            while(ch >= cm[n]):
                                ch -= cm[n]
                                mc[n] += 1
                        tn = sum(mc)
                        if (tn < mintn):
                            mintn = tn
                            fc = [i,j,k,l]
    for i in xrange(4):
        if fc[i] != 0: print "%d %d" % (cm[i], fc[i])
    print ''

Submission status: Runtime Error

Solution code:
def coin(n):
    return n / 500 + (n % 500) / 100 + (n % 100) / 50 + (n % 50) / 10

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

Submission status: Runtime Error

Solution code:
def coin(n):
    return n / 500 + (n % 500) / 100 + (n % 100) / 50 + (n % 50) / 10

ret = ''

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

print ret[:-1]

Submission status: Runtime Error

Solution code:
def coin(n):
    return n / 500 + (n % 500) / 100 + (n % 100) / 50 + (n % 50) / 10

ret = ''

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