Problem:


Coin Changing Problem

Find the minimum number of coins to make change for n cents using coins of denominations d1, d2,.., dm. The coins can be used any number of times.

Input

n m
d1 d2 ... dm

Two integers n and m are given in the first line. The available denominations are given in the second line.

Output

Print the minimum number of coins in a line.

Constraints

1 ≤ n ≤ 50000

1 ≤ m ≤ 20

1 ≤ denomination ≤ 10000

The denominations are all different and contain 1.

Sample Input 1

55 4
1 5 10 50

Sample Output 1

2

Sample Input 2

15 6
1 2 7 8 12 50

Sample Output 2

2

Sample Input 3

65 6
1 2 7 8 12 50

Sample Output 3

3



Sample input:
55 4
1 5 10 50


Sample output:
2

Submission status: Accepted

Solution code:
class DP2D(object):

    def __init__(self, item_n: int, border: int, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" + \
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        raise NotImplementedError

    def fill_0_idx_with(self, value: int) -> "DP2D":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


class DP2DOptimizer(DP2D):

    def __init__(self, item_n: int, border: int, obj_coef: list, sbj_coef: list, initializer: int = 0):
        super(DP2DOptimizer, self).__init__(item_n, border, initializer=initializer)

        if len(obj_coef) == self.item_n:  # to 1-base
            obj_coef = [0] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [0] + sbj_coef
        self.sbj_coef = sbj_coef

    def solve(self, expr: callable) -> list:
        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def coin_expr(self, target, coin_idx) -> int:
        if self.sbj_coef[coin_idx] == 1:
            res = target
        else:
            res = self.table[target][coin_idx - 1]
            if target - self.sbj_coef[coin_idx] >= 0:
                res = min(res, self.table[target - self.sbj_coef[coin_idx]][coin_idx] + self.obj_coef[coin_idx])
        return res


if __name__ == '__main__':
    n, m = map(int, input().split())
    values = [int(i) for i in input().split()]
    dp = DP2DOptimizer(m, n, [1 for _ in range(m)], values, 50000).fill_0_idx_with(0)
    print(dp.solve(dp.coin_expr)[n][m])

Submission status: Accepted

Solution code:
N, m = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

dp = [50001] * (N + 1)
dp[0] = 0

for c in C:
    for n in range(c, N + 1):
        dp[n] = min(dp[n], dp[n - c] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
    
dp = [0] * (n+1)
for i in range(1, n+1):
    dp[i] = min([dp[i - c[j]]+1 for j in range(m) if i-c[j]>=0])

print(dp[n])

Submission status: Accepted

Solution code:
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))

dp=list(range(51234)) # 最小枚数
n,m = miipt()
C=miipt()
for c in C:
    for i in range(c, n+1):
        dp[i]=min(dp[i], dp[i-c]+1)
print(dp[n])

Submission status: Accepted

Solution code:
#  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=jp
#  Coin Changing Problem : python3
#  2018.12.11 yonezawa

#from collections import deque
import sys
input = sys.stdin.readline
#import cProfile
#from math import cos,sin,radians,sqrt

def Reflection(p1,p2):
    (x,y) = p2
    (tx,ty) = Projection(p1,(x,y))
    rx = (tx - x) * 2 + x 
    ry = (ty - y) * 2 + y
    return (rx,ry)


def solve(cn:int,l:list):
    calc = [[0 for i in range(len(l))] for j in range(cn+1)]
    calc[0][0] = 0

    for i in range(cn+1):
        calc[i][0] = i // l[0] if i % l[0] == 0 else (i // l[0]) + 1

    for j in range(1,len(l)):
        for i in range(cn+1):
            if i-l[j] >= 0:
                calc[i][j] = min(calc[i][j-1],calc[i-l[j]][j]+1)
            else:
                calc[i][j] = calc[i][j-1]
    print (calc[cn][j])
    return 0

def main():
    (cn,n) = map(int,input().split())
    l = list(map(int,input().split()))

    solve(cn,l)
    
if __name__ == '__main__':
    main()
    #pr = cProfile.Profile()
    #pr.runcall(main)
    #pr.print_stats()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ds = list(map(int, input().split()))
ds = sorted(ds)
dp = [100000] * (n+1)
dp[0] = 0

for i in range(n):
	for d in ds:
		if (i + d <= n):
			dp[i + d] = min(dp[i + d], dp[i] + 1)

print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DPL_1_A: Combinatorial - Coin Changing Problem


def change(n, cs):
    ts = [[0] * (n+1) for _ in range(len(cs)+1)]
    for j in range(0, n+1):
        ts[0][j] = n+1

    for i, c in enumerate(cs):
        for j in range(1, n+1):
            if j >= c:
                ts[i+1][j] = min(ts[i][j], ts[i+1][j-c]+1)
            else:
                ts[i+1][j] = ts[i][j]

    return ts[-1][-1]


def run():
    n, m = [int(i) for i in input().split()]
    denoms = [int(i) for i in input().split()]

    print(change(n, denoms))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c_list = list(map(int, input().split()))


def get_coin_number(coin_list, n, m):
    t = [float("inf") for i in range(n + 1)]
    t[0] = 0

    for i in range(1, m + 1):
        for j in range(coin_list[i-1], n + 1):
            t[j] = min(t[j], t[j - coin_list[i-1]] + 1)
    return t[n]


print(get_coin_number(c_list, n, m))

Submission status: Accepted

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

n, m = [int(t) for t in input().split()]
c    = [int(t) for t in input().split()]
assert len(c) == m

# ncoin[k] = k円支払うときの最小枚数
ncoin = {0: 0}

for k in range(1, n + 1):
    ncoin[k] = min(ncoin[k - x] + 1 for x in c if k >= x)

print(ncoin[n])

Submission status: Accepted

Solution code:
BIG_NUM = 10**9

n, m = map(int, input().split(" "))
c = list(map(int, input().split(" ")))

l = [BIG_NUM] * (n+1)
l[0] = 0

for c_i in c:
	for j in range(1, n+1):
		if j < c_i:
			continue
		l[j] = min(l[j-c_i]+1, l[j])

	# print(l)
print(l[n])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
coins=list(map(int,input().split()))

data=[0,1]
for i in range(2,n+1):
    mini=i
    for coin in coins:
        if i-coin>=0:
            if data[i-coin]<mini:
                mini=data[i-coin]
    data.append(mini+1)
print(data[n])

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
 
#------------------------------------------#
 
BIG_NUM = 2000000000
HUGE_NUM = 9999999999999999
MOD = 1000000007
EPS = 0.000000001
 
#------------------------------------------#
 
W,N = map(int,input().split())
 
table = [BIG_NUM]*(W+1)
 
table[0] = 0
 
coin_list = list(map(int,input().split()))
 
for coin in coin_list:
    for i in range(coin,W+1):
        table[i] = min(table[i],table[i-coin]+1)
 
 
print("%d"%(table[W]))

Submission status: Accepted

Solution code:
n, m = map(int, input().strip().split())
d = [i for i in map(int, input().strip().split())]
assert len(d) == m

cands = sorted(d)
data = [i for i in range(n+1)]

for c in cands:
    for i in range(n+1):
        if i + c <= n and data[i+c] > data[i] + 1:
            data[i+c] = data[i] + 1
print(data[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = list(map(int, input().split()))

dp = [[0 for i in range(m)] for j in range(n + 1)]
for j in range(n + 1):
    dp[j][0] = j
for j in range(n + 1):
    for i in range(1, m):
        if j >= c[i]:
            dp[j][i] = min(dp[j][i - 1], dp[j - c[i]][i] + 1)
        else:
            dp[j][i] = dp[j][i - 1]
print(dp[n][m - 1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
C = list(map(int, input().split()))
T = [0]+[float('inf')]*n

for i in range(m):
  for j in range(C[i], n+1):
    T[j] = min(T[j], T[j-C[i]]+1)


# for i in range(m):
#   for j in range(n):
#     T[i][j] = min(T[i-1][j], T[i][j-C[i]] +1)
print(T[j])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
coin = list(map(int, input().split()))
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n+1):
    for j in coin:
        if i+j <= n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
N, m = map(int, input().split())
mlist = sorted(list(map(int, input().split())))

ilist = [i for i in range(N+1)] #1행 (앞으로 i행)

for i in range(m-1):  #i행
    cm = mlist[i+1]
    copy1 = ilist[:]   #(i-1)행
    for k in range(1,N+1):    #k열
        if (cm > k):
            ilist[k] = copy1[k]
        else:
            ilist[k] = min(copy1[k], (ilist[k-cm] + 1))
print(ilist[-1])

Submission status: Accepted

Solution code:
def getTheNumberOfCoin(n, m, c):
    INF = 1 << 29
    t = [INF] * (n + 1)
    t[0] = 0
    for i in range(m):
        for j in range(c[i], n + 1):
            t[j] = min(t[j], t[j - c[i]] + 1)

    return t[n]

if __name__ == '__main__':
    n, m = [int(v) for v in input().split()]
    c = [int(v) for v in input().split()]
    print(getTheNumberOfCoin(n, m, c))

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())

coins = map(int,raw_input().split())

dp = [i for i in range(n+1)]

for i in coins:
	for j in range(n+1):
		if j-i > -1:
			dp[j] = min(dp[j], dp[j-i] + 1)

print dp[n]

Submission status: Accepted

Solution code:
n,m=map(int,input().split(" "))
c=sorted(list(map(int,input().split(" "))))[1:]
ans=list(range(n+1))
for i in c:
    for j in range(i,n+1):
        ans[j]=min([ans[j],(ans[j-i]+1)])
print(ans[-1])

Submission status: Accepted

Solution code:
import sys
def get_min_no_of_coins(p, coins):
	dp = [sys.maxsize-1] * (p+1)
	dp[0] = 0
	for coin in coins:
		for i in range(coin, p+1):
			dp[i] = min(dp[i], dp[i-coin]+1)
	return dp[p]

p, n = map(int, input().split())
coins = list(map(int, input().split()))

ans = get_min_no_of_coins(p, coins)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
coins = list(map(int, input().split()))
dp = [float('inf') for i in range(n+1)]
dp[0] = 0
for i in range(n):
    for coin in coins:
        if coin <= i+1:
            dp[i+1] = min(dp[i+1 - coin] + 1, dp[i+1])
print(dp[n])

Submission status: Accepted

Solution code:
# DPL_1_A
# https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_A
MAX = 50005

n, m = map(int, input().split())
c = list(map(int, input().split()))

# dp[v] := 価値v円を支払うときに使用するコインの最小枚数
dp = [MAX for _ in range(n+1)]
dp[0] = 0

for i in range(m):
    for j in range(n+1):
        if j + c[i] > n: break
        dp[j + c[i]] = min(dp[j + c[i]], dp[j] + 1)
        # print(i, j, dp)

print(dp[n])

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input())
c = map(int, raw_input())
print 0

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
c = map(int, raw_input()_split())
print 0

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = list(map(int,input().split()))
c.reversed()
su = 0
for i in range(b):
    if a >= c[i]:
        a %= c[i]
        su += 1
        
print(su)

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = list(map(int,input(),split()))
dp = [float("inf") for i in range(n+2)]

for i in range(n+1):
    for j in c:
        if i + j <= n:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
            
print(dp[a])

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = list(map(int,input().split()))
dp = [float("inf") for i in range(n+2)]

for i in range(n+1):
    for j in c:
        if i + j <= n:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
            
print(dp[a])

Submission status: Runtime Error

Solution code:
a,b = map(int,input().split())
c = list(map(int,input().split()))
dp = [float("inf") for i in range(a+2)]

for i in range(n+1):
    for j in c:
        if i + j <= n:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
            
print(dp[a])

Submission status: Runtime Error

Solution code:
def coin(a, b, c):

    global count
    global m

    if a % c[0] == 0:

        count = min(count, b + a // c[0])

        return count

    elif b + a // c[0] >= count:

        return n

    elif c[0] < n:

        return min(cs(a - c[0], b + 1, c), cs(a, b, c[1:]))

    else:

        return coin(a, b, c[1:])


n, m = map(int, input().split())

money = sorted(list(map(int, input().split())), reverse = True)

count = print(coin(n, 0, money))

Submission status: Runtime Error

Solution code:
def coin(a, b, c):

    global count
    global m

    if a % c[0] == 0:

        count = min(count, b + a // c[0])

        return count

    elif b + a // c[0] >= count:

        return n

    elif c[0] < n:

        return min(coin(a - c[0], b + 1, c), cs(a, b, c[1:]))

    else:

        return coin(a, b, c[1:])


n, m = map(int, input().split())

money = sorted(list(map(int, input().split())), reverse = True)

count = print(coin(n, 0, money))

Submission status: Runtime Error

Solution code:
def coin(a, b, c):

    global count
    global m

    if a % c[0] == 0:

        count = min(count, b + a // c[0])

        return count

    elif b + a // c[0] >= count:

        return n

    elif c[0] < n:

        return min(coin(a - c[0], b + 1, c), coin(a, b, c[1:]))

    else:

        return coin(a, b, c[1:])


n, m = map(int, input().split())

money = sorted(list(map(int, input().split())), reverse = True)

count = n

print(coin(n, 0, money))

Submission status: Runtime Error

Solution code:
n, m =map(int,input().split())
c = list(map(int,input().split()))

INF = 10**10
dp = [INF]*50000
dp[0] = 0

for i in range (n+1):
    for j in c:
        dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Runtime Error

Solution code:
n, m =map(int,input().split())
c = list(map(int,input().split()))

INF = 10**10
dp = [INF]*500
dp[0] = 0

for i in range (n+1):
    for j in c:
        dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Runtime Error

Solution code:
n, m =map(int,input().split())
c = list(map(int,input().split()))

INF = 10**10
dp = [INF]*(n+max(c))
dp[0] = 0

for i in range (n+1):
    for j in c:
        dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Runtime Error

Solution code:
n, m =map(int,input().split())
c = list(map(int,input().split()))

INF = 10**10
dp = [INF]*(n**2)
dp[0] = 0

for i in range (n+1):
    for j in c:
        dp[i+j] = min(dp[i+j],dp[i]+1)
print(dp[n])

Submission status: Runtime Error

Solution code:
C = int(input().split()[0])
V = [int(i) for i in input().split()]
N = len(V)

M = [None for _ in range(C+1)]
for i in range(C+1):
	M[i] = [0 for _ in range(N)]
for j in range(n):
	M[0][j] = 0
for i in range(1, C+1):
	for j in range(n):
		M[i][j] = min([ (M[i-x*V[j]][j-1] + x) for x in range(C//V[j]) ])
print(M[-1][-1])

Submission status: Runtime Error

Solution code:
C = int(input().split()[0])
V = [int(i) for i in input().split()]
N = len(V)

M = [None for _ in range(C+1)]
for i in range(C+1):
	M[i] = [0 for _ in range(N)]
for j in range(n):
	M[0][j] = 0
for i in range(1, C+1):
	for j in range(N):
		M[i][j] = min([ (M[i-x*V[j]][j-1] + x) for x in range(C//V[j]) ])
print(M[-1][-1])

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())

t = [float('inf') for i in range(n+1)]
t[0] = 0

for i in range(n+1):
    if c[i] > n:
        break
    else:
        for j in range(c[i], n+1):
            t[j] = min([t[j], t[j-c[i]]+1])
print t[n]

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())

t = [float('inf') for i in range(n+1)]
t[0] = 0

for i in range(n):
    if c[i] > n:
        break
    else:
        for j in range(c[i], n+1):
            t[j] = min([t[j], t[j-c[i]]+1])
print t[n]

Submission status: Runtime Error

Solution code:
from itertools import product

value, variety = map(int, input().split())
coins = list(map(int, input().split()))
dp = [float("inf") for _ in range(value + 1)]
dp[0] = 0
for (c,j) in product(coins,list(range(value + 1))):
    dp[j] = min(dp[j], dp[j - c] + 1)
print(dp[value])

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())
memo = [-1] * (n+1)
def dfs(rest):
    if memo[rest] != -1:
        return memo[rest]
    if rest == 0:
        return 0
    res = n+1
    for i in xrange(m):
        if c[i] <= rest:
            res = min(res, 1 + dfs(rest - c[i]))
    memo[rest] = res
    return res
print dfs(n)

Submission status: Runtime Error

Solution code:
import functools


@functools.lru_cache(maxsize=None)
def rec(c):
    if c <= 0:
        return 0 if c == 0 else INF
    ret = INF
    for coin in coins:
        ret = min(ret, rec(c-coin) + 1)
    return ret

INF = 10**6
N, M = map(int, input().split())
coins = [int(x) for x in input().split()]
print(rec(N))

Submission status: Runtime Error

Solution code:
import functools, sys


@functools.lru_cache(maxsize=None)
def rec(c):
    if c == 0:
        return 0
    ret = INF
    for coin in coins:
        if c - coin >= 0:
            ret = min(ret, rec(c-coin) + 1)
    return ret

INF = 10**6
N, M = map(int, input().split())
sys.setrecursionlimit(N+1)
coins = [int(x) for x in input().split()]
print(rec(N))

Submission status: Runtime Error

Solution code:
import functools, sys


@functools.lru_cache(maxsize=None)
def rec(c):
    if c == 0:
        return 0
    ret = INF
    for coin in coins:
        if c - coin >= 0:
            ret = min(ret, rec(c-coin) + 1)
    return ret

INF = 10**6
N, M = map(int, input().split())
coins = [int(x) for x in input().split()]
sys.setrecursionlimit(INF)
print(rec(N))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
c = list(map(int,input().split()))

minimum = [50000] * (n+1)
minimum[0] = 0

for i in range(1,n+1):
    if c[j] <= 2:
        continue
    for j in range(m):
        if c[j]<=i and minimum[i-c[j]] + 1 < minimum[i]:
            minimum[i] = minimum[i-c[j]]+1

print(minimum[n])

Submission status: Runtime Error

Solution code:
def dfs(index,n,m,c,dp):
    if dp[index][m] != 30:
        return dp[index][m]

    if index==n:
        return n+1

    if m==c[index]:
        return 1

    if m<c[index]:
        return dfs(index+1,n,m,c,dp)

    ret=min(dfs(index+1,n,m,c,dp),
            dfs(index+1,n,m-c[index],c,dp)+1,
            dfs(index,n,m-c[index],c,dp)+1)
    dp[index][m]=ret
    return ret
m,n=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
dp=[[30 for i in range(m+1)] for j in range(n+1)]
print(dfs(0,n,m,c,dp))

Submission status: Runtime Error

Solution code:
n, m = map(int, raw_input().split())
c = map(int, raw_input().split())

INF = 1000000000

t = [INF] * n
t[0] = 0

for i in range(m):
    # print(c[i])
    for j in range(c[i], n):
        t[j] = min([t[j], t[j - c[i]] + 1])
    # print(t)

print(t[n - 1])
~

Submission status: Runtime Error

Solution code:
currency = list(map(int,input().split()))

gra = [[0 for i in range(n+1)] for i in range(m)]

for i in range(m):
    for j in range(1,n+1):
        if i == 0:
            gra[i][j] = j
        else:
            if j>=currency[i]:
                gra[i][j] = min(gra[i-1][j],gra[i][j-currency[i]]+1)
            else:
                gra[i][j] = gra[i-1][j]

print(gra[m][n+1])

Submission status: Runtime Error

Solution code:
currency = list(map(int,input().split()))

gra = [[0 for i in range(n+1)] for i in range(m)]

for i in range(m):
    for j in range(1,n+1):
        if i == 0:
            gra[i][j] = j
        else:
            if j>=currency[i]:
                gra[i][j] = min(gra[i-1][j],gra[i][j-currency[i]]+1)
            else:
                gra[i][j] = gra[i-1][j]

print(gra[m-1][n])

Submission status: Runtime Error

Solution code:
n, m = input().split()
n = int(n)
m = int(m)

c = []
c = input().split()
for i in range(0,m):
	c[i] = int(c[i])
d = c[:]
c.reverse()

y = n
min = 0
while 1:
	if len(d) == 0:
		break
	if y < max(d):
		d.pop()
	else:
		min += int(y/max(d))
		y = y % max(d)
		d.pop()

#print(min)

memo = {}

#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	try:
		if memo[depth,sum] > 0:
			depth -= 1
			return min
	except KeyError:
		pass
	
	for i in c:
#		if i in done:
#			continue
		sum += i
		done.append(i)
#		print(min, "/", sum, "/", depth, done)
		if sum == n:
			if depth + 1 < min:
				min = depth + 1
			sum -= i
		elif sum > n:
			sum -= i
			continue
		else:
			depth += 1
			sum -= i
			min = select(sum+i)
	memo[depth,sum] = min
	depth -= 1
	return min

select(0)

print(min)

Submission status: Runtime Error

Solution code:
#coding: cp932

n, m = input().split()
n = int(n)
m = int(m)

c = []
c = input().split()
for i in range(0,m):
	c[i] = int(c[i])
d = c[:]
c.reverse()

y = n
min = 0
while 1:
	if len(d) == 0:
		break
	if y < max(d):
		d.pop()
	else:
		min += int(y/max(d))
		y = y % max(d)
		d.pop()

#print(min)

memo = {}

#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	try:
		if memo[depth,sum] > 0:
			depth -= 1
			return min
	except:
		pass
	
	for i in c:
#		if i in done:
#			continue
		sum += i
		done.append(i)
#		print(min, "/", sum, "/", depth, done)
		if sum == n:
			if depth + 1 < min:
				min = depth + 1
			sum -= i
		elif sum > n:
			sum -= i
			continue
		else:
			depth += 1
			sum -= i
			min = select(sum+i)
	memo[depth,sum] = min
	depth -= 1
	return min

select(0)

print(min)

Submission status: Runtime Error

Solution code:
#coding: cp932

n, m = input().split()
n = int(n)
m = int(m)

c = []
c = input().split()
for i in range(0,m):
	c[i] = int(c[i])
d = c[:]
c.reverse()

y = n
min = 0
while 1:
	if len(d) == 0:
		break
	if y < max(d):
		d.pop()
	else:
		min += int(y/max(d))
		y = y % max(d)
		d.pop()

#print(min)

memo = []
for i in range(0,min+1):
	memo.append(0)

#min = 100000000
depth = 0

def select(sum):
	global n
	global depth
	global memo
	global min
	done = []
	for i in c:
		# ????????±???????§£????????????????????????????????????
		if memo[depth] > 0:
			return memo[depth]
		
		# 1????????¶
		if i in done:
			continue
		done.append(i)
		
		# ???????????´????????????
		sum += i
		depth += 1
		
		if sum == n:
			memo[depth] = depth
			min = depth
			sum -= i
			depth -= 1
		elif sum > n:
			sum -= i
			depth -= 1
		else:
			min = select(sum)
			sum -= i
			depth -= 1
	return min

min = select(0)

print(min)

Submission status: Runtime Error

Solution code:
n, m = input().split()
n = int(n)
m = int(m)

c = []
c = input().split()
for i in range(0,m):
	c[i] = int(c[i])
d = c[:]
c.reverse()

y = n
min = 0
while 1:
	if len(d) == 0:
		break
	if y < max(d):
		d.pop()
	else:
		min += int(y/max(d))
		y = y % max(d)
		d.pop()

#print(min)

memo = []
for i in range(0,min+1):
	memo.append(0)

#min = 100000000
depth = 0

def select(sum):
	global n
	global depth
	global memo
	global min
	done = []
	for i in c:
		if memo[depth] > 0:
			return memo[depth]
		
		if i in done:
			continue
		done.append(i)
		
		sum += i
		depth += 1
		
		if sum == n:
			memo[depth] = depth
			min = depth
			sum -= i
			depth -= 1
		elif sum > n:
			sum -= i
			depth -= 1
		else:
			min = select(sum)
			sum -= i
			depth -= 1
	return min

min = select(0)

print(min)

Submission status: Runtime Error

Solution code:
def calc_t(i,j):
    global t,c
    if i<0 or j<0:
        return n+2
    #print("get t["+str(i)+","+str(j)+"]")
    if t[i][j]==n+1:
        t[i][j]=min(calc_t(i-1,j),calc_t(i,j-c[i])+1)
    return t[i][j]

ri=raw_input().split(" ")
n=int(ri[0])
m=int(ri[1])
ri=raw_input().split(" ")
c=[0]*m
t=[0]*m
for i in range(m):
    c[i]=int(ri[i])
    t[i]=[0]+[n+1]*n if i!=0 else range(n+1)
#print(c)
#print(t)
print(calc_t(m-1,n))

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
'''
Author:    krishna
Created:   Sun Jan  7 12:52:35 2018 IST
File Name: minCoinChange.py
USAGE:
      minCoinChange.py
Description:

'''
import sys, traceback, math


def solve(count, sol):
    '''
    Solve the problem ;)
    '''
    if not (count in sol):
        s = math.inf

        for i in range(1, (count + 1 >> 1) + 1):
            # if (3 == len(traceback.extract_stack())):
            #     print(i, count - i, sol)
            s = min(s, solve(i, sol) + solve(count - i, sol))

        sol[count] = s

    return sol[count]


def main():
    '''   The Main   '''
    n, m = map(int, sys.stdin.readline().split())
    d = sorted(map(int, sys.stdin.readline().split()))
    sol = {i: 1 for i in d}

    print(solve(n, sol))


if __name__ == '__main__':
   main()

Submission status: Runtime Error

Solution code:
nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))

dp = {}

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t, num):
  # 使う/使わないの枝をたどって0になったらOK
  if (t == 0):
    return (True, num)
  # p, tが不正な値になればその枝は終了
  if (p == m or t < 0):
    return (False, num)

  # p番目を使ったらtを引いて次へ, 使わなければtのまま次へ
  ans1 = solve(p, t-c[p], num+1)
  ans2 = (False, 50000)
  ans3 = (False, 50000)
  if (p < m):
    ans2 = solve(p+1, t-c[p], num+1)
    ans3 = solve(p+1, t, num)

  # 最小のnumがansになる
  ans = 50000
  if (ans1[0] and ans1[1] < ans):
    ans = ans1[1]
  if (ans2[0] and ans2[1] < ans):
    ans = ans2[1]
  if (ans3[0] and ans3[1] < ans):
    ans = ans3[1]

  return (ans1[0] or ans2[0] or ans3[0], ans)

print(solve(0, n, 0)[1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(50001)

nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))

dp = {}

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t, num):
  if ((p, t, num) in dp):
    return dp[(p, t, num)]

  # 使う/使わないの枝をたどって0になったらOK
  if (t == 0):
    return (True, num)
  # p, tが不正な値になればその枝は終了
  if (p == m or t < 0):
    return (False, num)

  # p番目を使ったらtを引いて次へ, 使わなければtのまま次へ
  ans1 = solve(p, t-c[p], num+1)
  ans2 = (False, 50000)
  ans3 = (False, 50000)
  if (p < m):
    ans2 = solve(p+1, t-c[p], num+1)
    ans3 = solve(p+1, t, num)

  # 最小のnumがansになる
  ans = 50000
  if (ans1[0] and ans1[1] < ans):
    ans = ans1[1]
  if (ans2[0] and ans2[1] < ans):
    ans = ans2[1]
  if (ans3[0] and ans3[1] < ans):
    ans = ans3[1]

  ret = (ans1[0] or ans2[0] or ans3[0], ans)
  dp[(p, t, num)] = ret
  return ret

print(solve(0, n, 0)[1])

Submission status: Runtime Error

Solution code:
nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))

dp = {}

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t):
  if ((p, t) in dp):
    return dp[(p, t)]

  # 使う/使わないの枝をたどって0になったらOK
  if (p == m):
    return 0 if t == 0 else 50001

  # p番目を1枚だけ使う
  # p番目を使わずに次へ, 使ったらtから引いて結果に1を加えてもう一度
  ans = min(solve(p+1, t), solve(p, t-c[p])+1)
  dp[(p, t)] = ans
  return ans
#   ans.append(solve(p, t-c[p], num+1))
#   ans.append(solve(p+1, t-c[p], num+1))
#   ans.append(solve(p+1, t, num))
  # p番目を0から使える枚数ギリギリまで使い次へ（再帰が深くなり過ぎるケースの対策）
#   cnt = math.floor(t / c[p])
#   for i in range(0, cnt+1):
#     ans.append(solve(p+1, t-c[p]*i, num+i))

  # 最小のnumがansになる
#   ansNum = 50000
#   for e in ans:
#     if (e[0] and e[1] < ansNum):
#       ansNum = e[1]

#   ret = (list(map(lambda e: e[0], ans)).count(True) > 0, ansNum)
#   dp[(p, t, num)] = ret
#   return ret

print(solve(0, n))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(65532)

nm = input().split(' ')
n = int(nm[0])
m = int(nm[1])
c = list(map(int, input().split(' ')))

dp = {}

# cの要素のうちp番目以降を組み合わせてtを作れるか?作れるならその数を返す
def solve(p, t):
  if ((p, t) in dp):
    return dp[(p, t)]

  # 使う/使わないの枝をたどって0になったらOK
  if (p == m):
    return 0 if t == 0 else 50001

  # p番目を1枚だけ使う
  # p番目を使わずに次へ, 使ったらtから引いて結果に1を加えてもう一度
  ans = min(solve(p+1, t), solve(p, t-c[p])+1)
  dp[(p, t)] = ans
  return ans
#   ans.append(solve(p, t-c[p], num+1))
#   ans.append(solve(p+1, t-c[p], num+1))
#   ans.append(solve(p+1, t, num))
  # p番目を0から使える枚数ギリギリまで使い次へ（再帰が深くなり過ぎるケースの対策）
#   cnt = math.floor(t / c[p])
#   for i in range(0, cnt+1):
#     ans.append(solve(p+1, t-c[p]*i, num+i))

  # 最小のnumがansになる
#   ansNum = 50000
#   for e in ans:
#     if (e[0] and e[1] < ansNum):
#       ansNum = e[1]

#   ret = (list(map(lambda e: e[0], ans)).count(True) > 0, ansNum)
#   dp[(p, t, num)] = ret
#   return ret

print(solve(0, n))

Submission status: Runtime Error

Solution code:
import math
n, m = map(int,input().split(' '))
d = list(map(int,input().split(' ')))
d.sort()
inf = n

dp = [ [ inf for i in range(m+1)] for j in range(n+1) ]

# dp
for j in range(m+1):
    dp[0][j]=0

for j in range(m-1,-1,-1):
    for i in range(n+1):
        #for k in range(math.floor(i/d[j])+1):
        k=1
        r = k*d[j]
        #print(i,j,k)
        dp[i][j] = min( dp[i][j], dp[i][j+1], dp[i-r][j]+k ) 
        #print("dp:",i,j,dp[i][j])
print(dp[n][0])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 26 12:16:54 2018
DPL-1A Rec Call Revised
@author: maezawa
"""

n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
c.sort(reverse=True)
dp = [float('inf') for _ in range(n+1)]
dp[0] = 0
#print(n,m)
#print(c)
#print(*dp, sep='\n')

def min_number(nn):
    if dp[nn] != float('inf'):
        return dp[nn]
    temp = []
    for i in range(m):
        if nn < c[i]:
            continue
        else:
            temp.append(min_number(nn-c[i])+1)
    dp[nn] = min(temp)
    return dp[nn]

print(min_number(n))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
DP = {}

def func(num, yen):
	if num < 0 or yen < 0:
		return 10 ** 18
	if num == 0 and yen == 0:
		return 0
	if not (num, yen) in DP:
		DP[(num, yen)] = min(func(num - 1, yen), func(num, yen - c[num]) + 1)
	return DP[(num, yen)]

print(func(m - 1, n))