Problem:


500-yen Saving

"500-yen Saving" is one of Japanese famous methods to save money. The
method is quite simple; whenever you receive a 500-yen coin in your
change of shopping, put the coin to your 500-yen saving box.
Typically, you will find more than one million yen in your saving box
in ten years.

Some Japanese people are addicted to the 500-yen saving. They try
their best to collect 500-yen coins efficiently by using 1000-yen bills
and some coins effectively in their purchasing. For example, you will give
1320 yen (one 1000-yen bill, three 100-yen coins and two 10-yen coins)
to pay 817 yen, to receive one 500-yen coin (and three 1-yen coins)
in the change.

A friend of yours is one of these 500-yen saving addicts.  He is
planning a sightseeing trip and wants to visit a number of souvenir
shops along his way.  He will visit souvenir shops one by one
according to the trip plan. Every souvenir shop sells only one kind of
souvenir goods, and he has the complete list of their prices.  He
wants to collect as many 500-yen coins as possible through buying
at most one souvenir from a shop.  On his departure,
he will start with sufficiently many 1000-yen bills and no coins at
all.  The order of shops to visit cannot be changed.  As far as he can
collect the same number of 500-yen coins, he wants to cut his expenses
as much as possible.

Let's say that he is visiting shops with their souvenir prices of 800
yen, 700 yen, 1600 yen, and 600 yen, in this order.  He can collect at
most two 500-yen coins spending 2900 yen, the least expenses to collect
two 500-yen coins, in this case.  After skipping the first shop, the
way of spending 700-yen at the second shop is by handing over a
1000-yen bill and receiving three 100-yen coins.  In the next shop,
handing over one of these 100-yen coins and two 1000-yen bills for
buying a 1600-yen souvenir will make him receive one 500-yen coin. In
almost the same way, he can obtain another 500-yen coin at the last
shop.  He can also collect two 500-yen coins buying at the first shop,
but his total expenditure will be at least 3000 yen because he needs
to buy both the 1600-yen and 600-yen souvenirs in this case.

You are asked to make a program to help his collecting 500-yen coins
during the trip.  Receiving souvenirs' prices listed in the order
of visiting the shops, your program is to find the maximum number of
500-yen coins that he can collect during his trip, and the minimum
expenses needed for that number of 500-yen coins.

For shopping, he can use an arbitrary number of 1-yen, 5-yen, 10-yen,
50-yen, and 100-yen coins he has, and arbitrarily many 1000-yen bills.
The shop always returns the exact change, i.e., the difference between
the amount he hands over and the price of the souvenir.  The shop has
sufficient stock of coins and the change is always composed of the
smallest possible number of 1-yen, 5-yen, 10-yen, 50-yen, 100-yen, and
500-yen coins and 1000-yen bills.  He may use more money than the
price of the souvenir, even if he can put the exact money, to obtain
desired coins as change; buying a souvenir of 1000 yen, he can hand
over one 1000-yen bill and five 100-yen coins and receive a 500-yen
coin.  Note that using too many coins does no good; handing over ten
100-yen coins and a 1000-yen bill for a souvenir of 1000 yen, he will
receive a 1000-yen bill as the change, not two 500-yen coins.

Input

The input consists of at most 50 datasets, each in the following format.

n 

p1

...

pn 

n is the number of souvenir shops, which is a positive integer not
greater than 100.

pi is the price of the souvenir of the i-th souvenir shop.

pi is a positive integer not greater than 5000.

The end of the input is indicated by a line with a single zero.

Output

For each dataset, print a line containing two integers c and s separated by a space.

Here, c is the maximum number of 500-yen coins that he can get during his
trip, and s is the minimum expenses that he need to pay to get c
500-yen coins.

Sample Input

4
800
700
1600
600
4
300
700
1600
600
4
300
700
1600
650
3
1000
2000
500
3
250
250
1000
4
1251
667
876
299
0

Output for the Sample Input

2 2900
3 2500
3 3250
1 500
3 1500
3 2217



Sample input:
4
800
700
1600
600
4
300
700
1600
600
4
300
700
1600
650
3
1000
2000
500
3
250
250
1000
4
1251
667
876
299
0


Sample output:
2 2900
3 2500
3 3250
1 500
3 1500
3 2217

Submission status: Wrong Answer

Solution code:

def compute_max_num_500_coins(prices):
    num_500_coins = 0
    coin = 0
    possible_thousand_coin_prices = []
    for p in prices:
        if p % 1000 == 0:
            if coin >= 500:
                possible_thousand_coin_prices.append(p)
        elif p % 1000 <= 500:
            num_500_coins += 1
            coin += 500 - p % 500
        elif p % 500 <= coin:
            num_500_coins += 1
            coin -= p % 500
        else:
            coin += 500 - p % 500

    thousand_coin_price = 0
    if len(possible_thousand_coin_prices) > 0 and coin >= 500:
        thousand_coin_price = min(possible_thousand_coin_prices)
        num_500_coins += 1
        coin -= 500
    return num_500_coins, coin, thousand_coin_price

def find_unneeded_prices(prices, remaining_coin):
    table = []
    for i in range(len(prices) + 1):
        table.append([0] * (remaining_coin + 1))
    for i in range(1, len(prices) + 1):
        p = prices[i - 1]
        prev_row = table[i - 1]
        row = table[i]
        for j in range(remaining_coin + 1):
            r = 500 - p % 500
            if j < r:
                row[j] = prev_row[j]
            else:
                row[j] = max(prev_row[j], prev_row[j - r] + p)
    i = len(prices)
    j = remaining_coin
    unneeded_prices = []
    while i > 0 and j > 0:
        if table[i][j] > table[i - 1][j]:
            j -= (500 - prices[i - 1] % 500)
            unneeded_prices.append(prices[i - 1])
        i -= 1
    return unneeded_prices

while True:
    n = int(input())
    if n == 0:
        break
    prices = []
    for i in range(n):
        prices.append(int(input()))
    no_thousand_prices = [p for p in prices if p % 1000 != 0]
    max_num_500_coins, remaining_coin, thousand_coin_price = compute_max_num_500_coins(prices)
    target_prices = [p for p in prices if p % 1000 > 500]
    unneeded_prices = find_unneeded_prices(target_prices, remaining_coin)
    expense = sum(no_thousand_prices) - sum(unneeded_prices) + thousand_coin_price
    print(max_num_500_coins, expense)

Submission status: Wrong Answer

Solution code:
N = int(input())
while(N != 0):
    coin = [-1 for _ in range(50000)]
    coin[0] = 0
    minprice = [0 for i in range(50000)]
    for i in range(N):
        price = int(input())
        charge = (1000 - (price % 1000)) % 1000
        coin_tmp = coin[:]
        minprice_tmp = minprice[:]
        for state in range(50000):
            if(coin[state] != -1):
                #print("#", state, coin[state])
                getcoin = (charge+state) // 500
                newstate = max((charge+state) % 500, (charge+state) - 500)
                if(getcoin == 0):
                    if(coin[newstate] == -1):  # ??°??¶???
                        coin_tmp[newstate] = coin[state]
                        minprice_tmp[newstate] = minprice[state] + price
                    else:
                        minprice_tmp[newstate] = min(minprice[newstate], minprice[state] + price)
                else:
                    if(coin[newstate] < coin[state] + 1):
                        coin_tmp[newstate] = coin[state] + 1
                        minprice_tmp[newstate] = minprice[state] + price
                    elif(coin[newstate] == coin[state] + 1):
                        minprice_tmp[newstate] = min(minprice[newstate], minprice[state] + price)
        coin = coin_tmp[:]
        minprice = minprice_tmp[:]

    coin_ans = -1
    coin_ans_price = []
    for i in range(50000):
        if(coin_ans < coin[i]):
            coin_ans = coin[i]
            coin_ans_price = [minprice[i]]
        elif(coin_ans == coin[i]):
            coin_ans_price.append(minprice[i])
    print(coin_ans, min(coin_ans_price))
    N = int(input())

Submission status: Wrong Answer

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    dp = [[None]*1000 for i in xrange(n+1)]
    dp[0][0] = (0, 0)
    for i in xrange(n):
        cost = int(raw_input())
        for j in xrange(1000):
            if dp[i][j] is None:
                continue
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            c, s = dp[i][j]
            if cost <= 500:
                s -= cost
                dp[i+1][(-s) % 1000] = max(dp[i+1][(-s) % 1000], (c, s))
                dp[i+1][(-s+500) % 1000] = max(dp[i+1][(-s+500) % 1000], (c+1, s-500))
            else:
                s -= cost
                dp[i+1][(-s) % 1000] = max(dp[i+1][(-s) % 1000], (c, s))
                if 1 <= (-s) % 1000 <= 500:
                    dp[i+1][(-s+500) % 1000] = max(dp[i+1][(-s+500) % 1000], (c+1, s-500))
    c, s = max(dp[n])
    print c, -s-500*c

Submission status: Wrong Answer

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    dp = [[None]*1000 for i in xrange(n+1)]
    dp[0][0] = (0, 0)
    for i in xrange(n):
        cost = int(raw_input())
        for j in xrange(1000):
            if dp[i][j] is None:
                continue
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            c, s = dp[i][j]
            if cost <= 500 or 1 <= cost % 1000 <= 500:
                s -= cost
                dp[i+1][(-s) % 1000] = max(dp[i+1][(-s) % 1000], (c, s))
                dp[i+1][(-s+500) % 1000] = max(dp[i+1][(-s+500) % 1000], (c+1, s-500))
            else:
                s -= cost
                dp[i+1][(-s) % 1000] = max(dp[i+1][(-s) % 1000], (c, s))
                if 1 <= (-s) % 1000 <= 500:
                    dp[i+1][(-s+500) % 1000] = max(dp[i+1][(-s+500) % 1000], (c+1, s-500))
    c, s = max(dp[n])
    print c, -s-500*c

Submission status: Accepted

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    L = 500*n
    dp = [None]*(L+1)
    dp[0] = (0, 0)
    for i in xrange(n):
        dp2 = dp[:]
        cost = int(raw_input())
        d3 = cost % 1000
        for j in xrange(L+1):
            if dp[j] is None:
                continue
            num, su = dp[j]
            if d3 == 0:
                if 500 <= j:
                    dp2[j - 500] = max(dp2[j - 500], (num+1, su-cost))
            elif 1 <= d3 <= 500+j:
                dp2[j + (500 - d3)] = max(dp2[j + (500 - d3)], (num+1, su-cost))
            else:
                dp2[j + (1000 - d3)] = max(dp2[j + (1000 - d3)], (num, su-cost))
        dp, dp2 = dp2, dp
    num, su = max(dp)
    print num, -su

Submission status: Accepted

Solution code:
from collections import defaultdict
def main(n):
    m = n * 499 + 1
    dp =  defaultdict(list)
    dp[0] = [0, 0]
    for _ in range(n):
        ndp = defaultdict(lambda:[-1,-1])
        for key, value in dp.items():
            ndp[key] = value[:]
        p = int(input())
        a = -p % 1000
        if a >= 500:
            b = a - 500
            for j in dp.keys():
                if dp[j][0] < 0: continue
                tmp = ndp[j + b]
                if tmp[0] < dp[j][0] + 1:
                    tmp[0] = dp[j][0] + 1
                    tmp[1] = dp[j][1] + p
                elif tmp[0] == dp[j][0] + 1 and tmp[1] > dp[j][1] + p:
                    tmp[0] = dp[j][0] + 1
                    tmp[1] = dp[j][1] + p
        else:
            b = 500 - a % 500
            for j in dp.keys():
                if dp[j][0] < 0: continue
                tmp = ndp[j + a]
                if tmp[0] < dp[j][0]:
                    tmp[0] = dp[j][0]
                    tmp[1] = dp[j][1] + p
                elif tmp[0] == dp[j][0] and tmp[1] > dp[j][1] + p:
                    tmp[1] = dp[j][1] + p
                if j - b >= 0:
                    tmp = ndp[j - b]
                    if tmp[0] < dp[j][0] + 1:
                        tmp[0] = dp[j][0] + 1
                        tmp[1] = dp[j][1] + p
                    elif tmp[0] == dp[j][0] + 1 and tmp[1] > dp[j][1] + p:
                        tmp[1] = dp[j][1] + p
        dp = ndp
    ans = [0, 0]
    for n, c in dp.values():
        if n > ans[0]:
            ans = [n, c]
        elif n == ans[0] and c < ans[1]:
            ans = [n, c]
    print(*ans)

if __name__ == "__main__":
    while 1:
        n = int(input())
        if n:
            main(n)
        else:
            break

Submission status: Accepted

Solution code:
from copy import deepcopy
from operator import itemgetter

def buy(p, cr):
    cnt, rem = cr
    r1000 = p % 1000
    r500 = p % 500
    m500 = 500 - r500
    m1000 = 1000 - r1000
    if r1000 == 0:
        if rem < 500:
            return ((cnt, rem),)
        else:
            return ((cnt+1, rem-500),)
    elif r1000 == 500:
        return ((cnt+1, rem),)
    elif r1000 < 500:
        return ((cnt+1, rem + m500), (cnt, rem + m1000))
    else:
        if rem - r500 >= 0:
            return ((cnt+1, rem - r500),)
        else:
            return ((cnt, rem + m500),)

INF = 10**20

def solve(plist):
    dp = {
        (0, 0): 0
    }
    for p in plist:
        ndp = {}
        for cr in list(dp.keys()):
            for ncr in buy(p, cr):
                ndp[ncr] = min(dp[cr] + p, dp.get(ncr, INF))

        dp.update(ndp)
        ndp = {}
        cc = -1
        mp = INF
        for c, r in sorted(dp.keys(), reverse=True):
            pp = dp[(c, r)]
            if cc != c:
                mp = INF
                cc = c
            if mp > pp:
                ndp[(c, r)] = pp
                mp = pp
        dp = ndp

    cplist = ((t[0][0], t[1]) for t in dp.items())
    return sorted(sorted(cplist, key=itemgetter(1)),
                  key=itemgetter(0), reverse=True)[0]

def main():
    while True:
        n = int(input().strip())
        if n == 0:
            break
        plist = [int(input().strip()) for _ in range(n)]
        print(" ".join(str(i) for i in solve(plist)))

if __name__ == '__main__':
    main()

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**13
mod = 10**9+9
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 = []

    def f(n):
        a = [I() for _ in range(n)]
        t = [(0,0,0)]
        for c in a:
            nt = collections.defaultdict(lambda: inf)
            c1 = c % 1000
            c5 = c % 500
            mc5 = 500 - c5
            for g,k,p in t:
                nt[(g,k)] = p
            if c1 == 0:
                for g,k,p in t:
                    if k >= 500 and nt[(g+1,k-500)] > p + c:
                        nt[(g+1,k-500)] = p + c
            elif c1 == 500:
                for g,k,p in t:
                    if nt[(g+1, k)] > p + c:
                        nt[(g+1, k)] = p + c
            elif c1 < 500:
                for g,k,p in t:
                    if nt[(g+1, k+mc5)] > p + c:
                        nt[(g+1, k+mc5)] = p + c
            else:
                for g,k,p in t:
                    if k + mc5 >= 500 and nt[(g+1,k+mc5-500)] > p + c:
                        nt[(g+1,k+mc5-500)] = p + c
                    if nt[(g, k+mc5)] > p + c:
                        nt[(g, k+mc5)] = p + c
            t = []
            cg = -1
            mk = -1
            mp = inf
            # print('nt',nt)
            for g,k in sorted(nt.keys(), reverse=True):
                p = nt[(g,k)]
                if p == inf:
                    continue
                if cg != g:
                    mp = inf
                    cg = g
                if mk < k or mp > p:
                    t.append((g,k,p))
                    if mk < k:
                        mk = k
                    if mp > p:
                        mp = p
            # print(len(t))
        r = 0
        rp = inf
        for g,k,p in t:
            if r < g or (r==g and rp > p):
                r = g
                rp = p
        return '{} {}'.format(r, rp)

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

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


print(main())

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def compute(prices, max_sum_having_coin):
    """
    DP
    t?????????????????????????????????????????????????????£???????????????t??¨?????¶???
    ????????§??????????????\???????????????
    ??????t???????????????500?????????????????°???ct???????????\????????¬??¨???????¨????st??§?????????????????????????????????????????§
    ???????????§???????????£????????????????°?????????????????????¨??????????????????????????????????????????i(i < t)??§???
    500?????????????????°???ci, ????????\????????¬??¨???????¨????si??§????????¨????????¨??????????????§???????????£????????????????????¶?????¨???????????????????????§????°???§?????????
    ??????????°?????????????????????????????????¨?????????????????????t??????????????????????°?????????????????????????????????¨???????????¨??????????????????
    """
    n = len(prices)
    m = max_sum_having_coin
    # table[i][j] = ??????i???????????¬??¨j???????????? (500??????????????§???, 500??????????????§?????¨????????¨??????????????£????????????????°????)
    table = []
    for i in range(n + 1):
        table.append([None] * (m + 1))
    table[0][0] = (0, 0)
    for i in range(1, n + 1):
        for j in range(0, m + 1):
            price = prices[i - 1]
            states = []
            # ?????\???500?????????????????\???????????¨???
            if price % 1000 != 0 and j >= 500 - price % 500:
                temp = table[i - 1][j - (500 - price % 500)]
                if temp != None:
                    states.append((temp[0], temp[1] + price))
            # ?????\???????????¨???
            temp = table[i - 1][j]
            if temp != None:
                states.append(temp)
            # ?????\???500?????????????????\????????¨???
            if price % 1000 == 0:
                if j + 500 <= m:
                    temp = table[i - 1][j + 500]
                    if temp != None:
                        states.append((temp[0] + 1, temp[1] + price))
            elif price % 1000 <= 500:
                temp = table[i - 1][j - (500 - price % 500)]
                if temp != None:
                    states.append((temp[0] + 1, temp[1] + price))
            elif j + price % 500 <= m:
                temp = table[i - 1][j + price % 500]
                if temp != None:
                    states.append((temp[0] + 1, temp[1] + price))
            if len(states) > 0:
                states.sort(key=itemgetter(1))
                states.sort(key=itemgetter(0), reverse=True)
                table[i][j] = states[0]
    max_state = None
    for j in range(0, m + 1):
        state = table[n][j]
        if state == None:
            continue
        if max_state == None or state[0] > max_state[0] or (state[0] == max_state[0] and state[1] < max_state[1]):
            max_state = state
    return max_state

while True:
    n = int(input())
    if n == 0:
        break
    prices = []
    for i in range(n):
        prices.append(int(input()))
    # ???????????????????????????500????????\????????????????????????????¨??????????500??????????¢?????????????
    # ????????°????????????n????????§?????????????????????????¨????????????? 500 * n ??§??????
    max_sum_having_coin = 500 * n
    result = compute(prices, max_sum_having_coin)
    print(result[0], result[1])

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def compare(state1, state2):
    if state1 == None:
        return False
    if state2 == None:
        return True
    return state1[0] > state2[0] or (state1[0] == state2[0] and state1[1] < state2[1])

def compute(prices, max_sum_having_coin):
    """
    DP
    t?????????????????????????????????????????????????????£???????????????t??¨?????¶???
    ????????§??????????????\???????????????
    ??????t???????????????500?????????????????°???ct???????????\????????¬??¨???????¨????st??§?????????????????????????????????????????§
    ???????????§???????????£????????????????°?????????????????????¨??????????????????????????????????????????i(i < t)??§???
    500?????????????????°???ci, ????????\????????¬??¨???????¨????si??§????????¨????????¨??????????????§???????????£????????????????????¶?????¨???????????????????????§????°???§?????????
    ??????????°?????????????????????????????????¨?????????????????????t??????????????????????°?????????????????????????????????¨???????????¨??????????????????
    """
    n = len(prices)
    m = max_sum_having_coin
    # table[i][j] = ??????i???????????¬??¨j???????????? (500??????????????§???, 500??????????????§?????¨????????¨??????????????£????????????????°????)
    table = []
    for i in range(n + 1):
        table.append([None] * (m + 1))
    table[0][0] = (0, 0)
    for i in range(1, n + 1):
        price = prices[i - 1]
        for j in range(0, m + 1):
            state = None
            # ?????\???500?????????????????\???????????¨???
            if price % 1000 != 0 and j >= 500 - price % 500:
                temp = table[i - 1][j - (500 - price % 500)]
                if temp != None:
                    temp = (temp[0], temp[1] + price)
                    if compare(temp, state):
                        state = temp
            # ?????\???????????¨???
            temp = table[i - 1][j]
            if temp != None and compare(temp, state):
                state = temp
            # ?????\???500?????????????????\????????¨???
            if price % 1000 == 0:
                if j + 500 <= m:
                    temp = table[i - 1][j + 500]
                    if temp != None:
                        temp = (temp[0] + 1, temp[1] + price)
                        if compare(temp, state):
                            state = temp
            elif price % 1000 <= 500:
                temp = table[i - 1][j - (500 - price % 500)]
                if temp != None:
                    temp = (temp[0] + 1, temp[1] + price)
                    if compare(temp, state):
                        state = temp
            elif j + price % 500 <= m:
                temp = table[i - 1][j + price % 500]
                if temp != None:
                    temp = (temp[0] + 1, temp[1] + price)
                    if compare(temp, state):
                        state = temp
            if state != None:
                table[i][j] = state
    max_state = None
    for j in range(0, m + 1):
        state = table[n][j]
        if state == None:
            continue
        if compare(state, max_state):
            max_state = state
    return max_state

# results = []
while True:
    n = int(input())
    if n == 0:
        break
    prices = []
    for i in range(n):
        prices.append(int(input()))
    # ???????????????????????????500????????\????????????????????????????¨??????????500??????????¢?????????????
    # ????????°????????????n????????§?????????????????????????¨????????????? 500 * n ??§??????
    # max_sum_having_coin = 500 * n
    max_sum_having_coin = 10000
    result = compute(prices, max_sum_having_coin)
    # results.append(result)
    print(result[0], result[1])

# for r in results:
#     print(r)

Submission status: Runtime Error

Solution code:
MAX_COINS = 500 * 100
INF = 10 ** 9


def dfs(idx, coins):
    if idx == N:
        return 0, 0
    elif dp[idx][coins] != -1:
        return dp[idx][coins]

    ret = (0, -INF)

    # not buy
    ret = max(ret, dfs(idx + 1, coins))

    # buy using only bills
    change = (1000 - P[idx] % 1000) % 1000
    cand, money = dfs(idx + 1, coins + change % 500)
    ret = max(ret, (cand + (change >= 500), money - P[idx]))

    # buy using both and get 500
    if (P[idx] + 500) % 1000 <= coins:
        cand, money = dfs(idx + 1, coins - (P[idx] + 500) % 1000)
        ret = max(ret, (cand + 1, money - P[idx]))
    dp[idx][coins] = ret
    # print(idx, coins, ret)
    return ret


while True:
    N = int(input())
    if not N:
        break
    P = [int(input()) for _ in range(N)]

    dp = [[-1] * (MAX_COINS + 1) for _ in range(N + 1)]
    ans, money = dfs(0, 0)
    print(ans, -money)

Submission status: Runtime Error

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
MAX_COINS = 500 * 100
INF = 10 ** 9


def dfs(idx, coins):
    if idx == N:
        return 0, 0
    elif dp[idx][coins] != -1:
        return dp[idx][coins]

    ret = (0, -INF)

    # not buy
    ret = max(ret, dfs(idx + 1, coins))

    # buy using only bills
    change = (1000 - P[idx] % 1000) % 1000
    cand, money = dfs(idx + 1, coins + change % 500)
    ret = max(ret, (cand + (change >= 500), money - P[idx]))

    # buy using both and get 500
    if (P[idx] + 500) % 1000 <= coins:
        cand, money = dfs(idx + 1, coins - (P[idx] + 500) % 1000)
        ret = max(ret, (cand + 1, money - P[idx]))
    dp[idx][coins] = ret
    # print(idx, coins, ret)
    return ret


while True:
    N = int(input())
    if not N:
        break
    P = [int(input()) for _ in range(N)]

    dp = [[-1] * (MAX_COINS + 1) for _ in range(N + 1)]
    ans, money = dfs(0, 0)
    print(ans, -money)

Submission status: Runtime Error

Solution code:
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
sys.setrecursionlimit(10 ** 6)
MAX_COINS = 500 * 100
INF = 10 ** 9


def dfs(idx, coins):
    if idx == N:
        return 0, 0
    elif dp[idx][coins] != -1:
        return dp[idx][coins]

    ret = (0, -INF)

    # not buy
    ret = max(ret, dfs(idx + 1, coins))

    # buy using only bills
    change = (1000 - P[idx] % 1000) % 1000
    cand, money = dfs(idx + 1, coins + change % 500)
    ret = max(ret, (cand + (change >= 500), money - P[idx]))

    # buy using both and get 500
    if (P[idx] + 500) % 1000 <= coins:
        cand, money = dfs(idx + 1, coins - (P[idx] + 500) % 1000)
        ret = max(ret, (cand + 1, money - P[idx]))
    dp[idx][coins] = ret
    # print(idx, coins, ret)
    return ret


while True:
    N = int(input())
    if not N:
        break
    P = [int(input()) for _ in range(N)]

    dp = [[-1] * (MAX_COINS + 1) for _ in range(N + 1)]
    ans, money = dfs(0, 0)
    print(ans, -money)

Submission status: Runtime Error

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    dp = [[None]*2001 for i in xrange(n+1)]
    dp[0][0] = (0, 0)
    for i in xrange(n):
        cost = int(raw_input())
        dost = cost % 1000
        for j in xrange(2001):
            if dp[i][j] is None:
                continue
            c, s = dp[i][j]
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            if dost == 0:
                if j >= 500:
                    dp[i+1][j + (500 - dost)] = max(dp[i+1][j + (500 - dost)], (c+1, s-cost))
                else:
                    dp[i+1][j] = max(dp[i+1][j], (c, s-cost))
            elif 1 <= dost <= 500+j:
                dp[i+1][j + (500 - dost)] = max(dp[i+1][j + (500 - dost)], (c+1, s-cost))
            else:
                dp[i+1][j + (1000 - dost)] = max(dp[i+1][j + (1000 - dost)], (c, s-cost))
    c, s = max(dp[n])
    print c, -s

Submission status: Runtime Error

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    dp = [[None]*2001 for i in xrange(n+1)]
    dp[0][0] = (0, 0)
    for i in xrange(n):
        cost = int(raw_input())
        dost = cost % 1000
        for j in xrange(2001):
            if dp[i][j] is None:
                continue
            c, s = dp[i][j]
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            if dost == 0:
                if j >= 500:
                    dp[i+1][j - 500] = max(dp[i+1][j - 500], (c+1, s-cost))
                else:
                    dp[i+1][j] = max(dp[i+1][j], (c, s-cost))
            elif 1 <= dost <= 500+j:
                dp[i+1][j + (500 - dost)] = max(dp[i+1][j + (500 - dost)], (c+1, s-cost))
            else:
                dp[i+1][j + (1000 - dost)] = max(dp[i+1][j + (1000 - dost)], (c, s-cost))
    c, s = max(dp[n])
    print c, -s

Submission status: Runtime Error

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    dp = [[None]*10001 for i in xrange(n+1)]
    dp[0][0] = (0, 0)
    for i in xrange(n):
        cost = int(raw_input())
        dost = cost % 1000
        for j in xrange(10001):
            if dp[i][j] is None:
                continue
            c, s = dp[i][j]
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            if dost == 0:
                if j >= 500:
                    dp[i+1][j - 500] = max(dp[i+1][j - 500], (c+1, s-cost))
                else:
                    dp[i+1][j] = max(dp[i+1][j], (c, s-cost))
            elif 1 <= dost <= 500+j:
                dp[i+1][j + (500 - dost)] = max(dp[i+1][j + (500 - dost)], (c+1, s-cost))
            else:
                dp[i+1][j + (1000 - dost)] = max(dp[i+1][j + (1000 - dost)], (c, s-cost))
    c, s = max(dp[n])
    print c, -s

Submission status: Runtime Error

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    dp = [[None]*100001 for i in xrange(n+1)]
    dp[0][0] = (0, 0)
    for i in xrange(n):
        cost = int(raw_input())
        dost = cost % 1000
        for j in xrange(100001):
            if dp[i][j] is None:
                continue
            c, s = dp[i][j]
            dp[i+1][j] = max(dp[i][j], dp[i+1][j])
            if dost == 0:
                if j >= 500:
                    dp[i+1][j - 500] = max(dp[i+1][j - 500], (c+1, s-cost))
                else:
                    dp[i+1][j] = max(dp[i+1][j], (c, s-cost))
            elif 1 <= dost <= 500+j:
                dp[i+1][j + (500 - dost)] = max(dp[i+1][j + (500 - dost)], (c+1, s-cost))
            else:
                dp[i+1][j + (1000 - dost)] = max(dp[i+1][j + (1000 - dost)], (c, s-cost))
    c, s = max(dp[n])
    print c, -s