Problem:


Problem J: ICPC: Ideal Coin Payment and Change

Taro, a boy who hates any inefficiencies, pays coins so that the number of coins to be returned as change is minimized in order to do smoothly when he buys something.

One day, however, he doubt if this way is really efficient.  When he pays more number of coins, a clerk consumes longer time to find the total value.  Maybe he should pay with least possible number of coins.

Thinking for a while, he has decided to take the middle course.  So he tries to minimize total number of paid coins and returned coins as change.

Now he is going to buy a product of P yen having several coins.  Since he is not good at calculation, please write a program that computes the minimal number of coins.

You may assume following things:

There are 6 kinds of coins, 1 yen, 5 yen, 10 yen, 50 yen, 100 yen and 500 yen.

The total value of coins he has is at least P yen.

A clerk will return the change with least number of coins.

Input

Input file contains several data sets.
One data set has following format:

P N1 N5 N10 N50 N100 N500

Ni is an integer and is the number of coins of i yen that he have.

The end of input is denoted by a case where P = 0.  You should output nothing for this data set.

Output

Output total number of coins that are paid and are returned.

Constraints

Judge data contains at most 100 data sets.

0 ≤ Ni ≤ 1000  

Sample Input

123 3 0 2 0 1 1
999 9 9 9 9 9 9
0 0 0 0 0 0 0

Output for the Sample Input

6
3



Sample input:
123 3 0 2 0 1 1
999 9 9 9 9 9 9
0 0 0 0 0 0 0


Sample output:
6
3

Submission status: Wrong Answer

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

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def total_coins(n):
	sum = 0
	for i in range(6):
		sum += n[i] * coin[i]
	return sum
	
def compute(p, n):
	a = n
	remain = p
	
	pay = [0] * 6
	index = 5
	while remain > 0:
		x = int(remain / coin[index])
		y = min(x, a[index])
		pay[index] += y
		a[index] -= y
		remain -= coin[index] * y
		index -= 1
	ch = charge(remain)
	cand = [sum(pay)+sum(ch)]

	for i in range(5, 0, -1):
		b = a
		pay2 = pay
		if b[i] > 0:
			pay2[i] += 1
			for j in range(i):
				pay2[j] = 0
			total = total_coins(pay2)
			ch = charge(total - p)
			cand.append(sum(pay2) + sum(ch))
	
	return min(cand)

	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)

Submission status: Wrong Answer

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

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def total_coins(n):
	sum = 0
	for i in range(6):
		sum += n[i] * coin[i]
	return sum
	
def compute(p, n):
	a = n
	remain = p
	
	pay = [0] * 6
	for index in range(5, -1, -1):
		x = int(remain / coin[index])
		y = min(x, a[index])
		pay[index] += y
		a[index] -= y
		remain -= coin[index] * y
	ch = charge(remain)
	cand = [sum(pay)+sum(ch)]

	for i in range(5, 0, -1):
		pay2 = pay
		if a[i] > 0:
			pay2[i] += 1
			for j in range(i):
				pay2[j] = 0
			total = total_coins(pay2)
			ch = charge(total - p)
			cand.append(sum(pay2) + sum(ch))
	
	return min(cand)

	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)

Submission status: Wrong Answer

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

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	if remain == 0:
		return [0] * 6
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def total_coins(n):
	sum = 0
	for i in range(6):
		sum += n[i] * coin[i]
	return sum

def check(pay, ch):
	if ch[0] == 4:
		pay[0] += 1
		ch[0] = 0
		ch[1] += 1
	elif ch[0] == 3:
		pay[0] += 2
		ch[0] = 0
		ch[1] += 1
	if ch[1] == 2:
		ch[1] = 0
		ch[2] += 1
	if ch[2] == 5:
		ch[2] = 0
		ch[3] += 1
	elif ch[2] == 4:
		pay[2] += 1
		ch[2] = 0
		ch[3] += 1
	elif ch[2] == 3:
		pay[2] += 2
		ch[2] = 0
		ch[3] += 1
	if ch[3] == 2:
		ch[3] = 0
		ch[4] += 1
	if ch[4] == 5:
		ch[4] = 0
		ch[5] += 1
	elif ch[4] == 4:
		pay[4] += 1
		ch[4] = 0
		ch[5] += 1
	if ch[5] == 1:
		ch[5] = 0
		pay[5] -= 1
	if ch[1] == 1 and pay[2] == 1:
		pay[2] = 0
		ch[1] = 0
		pay[1] += 1
	if ch[3] == 1 and pay[4] == 1:
		pay[4] = 0
		ch[3] = 0
		pay[3] += 1
	return pay, ch

def compute(p, n):
	a = n
	remain = p
	
	pay = [0] * 6
	for index in range(5, -1, -1):
		x = int(remain / coin[index])
		y = min(x, a[index])
		pay[index] += y
		a[index] -= y
		remain -= coin[index] * y
	if remain > 0:
		for index in range(0,6):
			if remain < coin[index]:
				pay[index] += 1
				a[index] -= 1
				remain -= coin[index]
				break
	ch = charge(-remain)
	cand = [sum(pay)+sum(ch)]
	pay2, ch2 = check(pay, ch)
	cand.append(sum(pay2) + sum(ch2))

	for i in range(5, 0, -1):
		pay2 = list(pay)
		if a[i] > 0:
			pay2[i] += 1
			for j in range(i):
				pay2[j] = 0
			total = total_coins(pay2)
			ch = charge(total - p)
			#print i, pay2, ch, total, p
			cand.append(sum(pay2) + sum(ch))
			pay2, ch2 = check(pay2, ch)
			total = total_coins(pay2)
			#print i, pay2, ch2, total, p
			cand.append(sum(pay2) + sum(ch2))

	#print cand
	return min(cand)

	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)

Submission status: Wrong Answer

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

def greedy(M,P):
    S=0
    if P==0:
        return 0
    for i in range(6):
        if M[i]!=0:
            MM=M[:]
            MM[i]=0
            payable=min( P/coins[i],M[i])
            payable2=min( P/coins[i]+1 ,M[i])
            return min(tsuri(coins[i]*payable2-P)+payable2, greedy(MM,P-coins[i]*payable )+payable)
    return 1000000000
        
        
def tsuri(Q):
    if Q<0:
        return 1000000000
    r=0
    for c in coins:
        r+=Q/c
        Q%=c
    return r

while(1):
    A=map(int, raw_input().split())
    P=A[0]
    N=A[1:]
    N.reverse()
    ans=100000000
    if P==0:    break
    for i in range(2**6):
        M=[N[x]*((i>>x)%2) for x in range(6)]
        ans=min(ans,greedy(M,P))
    print ans

Submission status: Wrong Answer

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

def greedy(M,P):
    S=0
    if P==0:
        return 0
    for i in range(6):
        if M[i]!=0:
            MM=M[:]
            MM[i]=0
            payable=min( P/coins[i],M[i])
            payable2=min( P/coins[i]+1 ,M[i])
            return min(tsuri_adj(coins[i]*payable2-P, MM)+payable2, greedy(MM,P-coins[i]*payable )+payable)
    return 1000000000
        
        
def tsuri(Q):
    r=0
    R=[0 for i in range(6)]
    if Q<0:
        return 1000000000,R
    for i in range(6):
        c=coins[i]
        r+=Q/c
        R[i]=Q/c
        Q%=c
    return r,R

def tsuri_adj(Q,M):
    [r,R]=tsuri(Q)
    lev=[100000000,5,2,5,2,5]
    S=map(lambda x,y,z: x+y%z , R,M,lev)
    for i in range(1,6):
        if S[-i]>=lev[-i]:
            r+=lev[-i]-R[-i]
            r-=R[-i]
            r+=1
            S[-i-1]+=1
            R[-i-1]+=1
    return r

while(1):
    A=map(int, raw_input().split())
    P=A[0]
    N=A[1:]
    N.reverse()
    ans=100000000
    if P==0:    break
    for i in range(2**6):
        M=[N[x]*((i>>x)%2) for x in range(6)]
        ans=min(ans,greedy(M,P))
    print ans

Submission status: Time Limit Exceeded

Solution code:
price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(p_sum - p + 1):
        coins = 0
        _change = change
        for i in reversed(range(6)):
            while _change >= price[i]:
                _change -= price[i]
                coins += 1

        total = p + change
        pay = [0] * 6
        for i in reversed(range(6)):
            while total >= price[i] and n[i] > pay[i]:
                total -= price[i]
                pay[i] += 1

        if total > 0:
            break

        coins += sum(pay)

        ans = min(ans, coins)
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(p_sum - p + 1):
        coins = 0
        _change = change
        for i in reversed(range(6)):
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        total = p + change
        pay = [0] * 6
        for i in reversed(range(6)):
            if total >= price[i]:
                pay[i] = min(n[i], int(total / price[i]))
                total -= pay[i] * price[i]

        if total > 0:
            break

        coins += sum(pay)

        ans = min(ans, coins)
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(p_sum - p + 1):
        total = p + change
        pay = [0] * 6
        #for i in reversed(range(6)):
        #    if total >= price[i]:
        #        pay[i] = min(n[i], int(total / price[i]))
        #        total -= pay[i] * price[i]

        #if total > 0:
        #    break

        coins = sum(pay)

        _change = change
        for i in reversed(range(6)):
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        ans = min(ans, coins)
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(p_sum - p + 1):
        total = p + change
        pay = [0] * 6
        #for i in reversed(range(6)):
        #    if total >= price[i]:
        #        pay[i] = min(n[i], int(total / price[i]))
        #        total -= pay[i] * price[i]

        #if total > 0:
        #    break

        coins = sum(pay)

        _change = change
        for i in [5, 4, 3, 2, 1, 0]:
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        ans = min(ans, coins)
    
    print(ans)

Submission status: Time Limit Exceeded

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

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def total_coins(n):
	sum = 0
	for i in range(6):
		sum += n[i] * coin[i]
	return sum
	
def compute(p, n):
	a = n
	remain = p
	
	pay = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			if a[index] > 0:
				pay[index] += 1
				a[index] -= 1
				remain -= coin[index]
		index -= 1
	ch = charge(remain)
	cand = [sum(pay)+sum(ch)]

	for i in range(5, 0, -1):
		b = a
		pay2 = pay
		if b[i] > 0:
			pay2[i] += 1
			for j in range(i):
				pay2[j] = 0
			total = total_coins(pay2)
			ch = charge(total - p)
			cand.append(sum(pay2) + sum(ch))
	
	return min(cand)

	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)

Submission status: Accepted

Solution code:
# AOJ 1028: ICPC: Ideal Coin Payment and Change
# Python3 2018.7.5 bal4u

c = (500, 100, 50, 10, 5, 1)

def pay(p):
	cnt = 0
	for i in range(6):
		if c[i] <= p:
			k = p//c[i]
			if k > n[i]: k = n[i]
			cnt += k
			p -= c[i]*k
	return -1 if p > 0 else cnt

k = [0]*1001
for p in range(1, 1001):
	cnt, q = 0, p
	for j in range(6):
		if c[j] <= q:
			cnt += q//c[j]
			q %= c[j]
	k[p] = cnt;

while True:
	a = list(map(int, input().split()))
	p = a[0]
	if p == 0: break
	del a[0]
	n = a[::-1]
	ans = 0x7fffffff
	for i in range(p, p+1001):
		j = pay(i)
		if j < 0: continue
		ans = min(ans, j + k[i-p])
	print(ans)

Submission status: Accepted

Solution code:
price = [1, 5, 10, 50, 100, 500]

while True:
    values = list(map(int, input().split()))
    p, n = values[0], values[1:]
    ans = 1e100
    if p == 0:
        break

    p_sum = sum(map(lambda s: s[0] * s[1], zip(price, n)))

    for change in range(1000):
        total = p + change
        pay = [0] * 6
        for i in reversed(range(6)):
            if total >= price[i]:
                pay[i] = min(n[i], int(total / price[i]))
                total -= pay[i] * price[i]

        if total > 0:
            break

        coins = sum(pay)

        _change = change
        for i in reversed(range(6)):
            if _change >= price[i]:
                coins += int(_change / price[i])
                _change %= price[i]

        ans = min(ans, coins)

    print(ans)

Submission status: Accepted

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

import sys

coin = [1, 5, 10, 50, 100, 500]

def charge(remain):
	if remain == 0:
		return [0] * 6
	ch = [0] * 6
	index = 5
	while remain > 0:
		while remain >= coin[index]:
			ch[index] += 1
			remain -= coin[index]
		index -= 1
	return ch

def compute(p, n):
	candidates = []
	for r in range(500):
		pay = [0] * 6
		q = p + r
		for i in range(5, -1, -1):
			m = q / coin[i]
			pay[i] = min(m, n[i])
			q -= pay[i] * coin[i]
		if q == 0:
			candidates.append(sum(pay) + sum(charge(r)))
	return min(candidates)
	
if __name__ == '__main__':
	for input in sys.stdin:
		input = map(int, input.split())
		p, n = input[0], input[1:]
		if p == 0:
			break
		print compute(p, n)

Submission status: Accepted

Solution code:
while True:
    p, n1, n5, n10, n50, n100, n500 = map(int, input().split())
    if p == 0:break
    values = (500, 100, 50, 10, 5, 1)
    values_cnt = (n500, n100, n50, n10, n5, n1)
    INF = 10 ** 20


    def return_cnt(x):
        ret = 0
        for value in values:
            ret += x // value
            x %= value
        return ret


    def make_price(x):
        ret = 0
        for value, cnt in zip(values, values_cnt):
            available_cnt = x // value
            ret += min(available_cnt, cnt)
            x -= value * min(available_cnt, cnt)
        if x == 0:return ret
        return INF


    print(min([make_price(i) + return_cnt(i - p) for i in range(p, p + 500)]))