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: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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(a+1):
    for j in c:
        if i + j <= a:
            dp[i+j] = min(dp[i+j],dp[i] + 1)
            
print(dp[a])

Submission status: Wrong Answer

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

count = 0

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

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

print(coin(n, 0, money))

Submission status: Wrong Answer

Solution code:
nm = raw_input().split()
n = int(nm[0])
m = int(nm[1])
d = raw_input().split()

c = [0] * 100000
c[0] = 0

for i in range(n):
    min = 100000
    for j in range(m):
        if int(d[j]) > i + 1:
            break
        x = c[i + 1 - int(d[j])]
        if x < min:
            min = x
    c[i + 1] = min + 1

print c[n]

Submission status: Wrong Answer

Solution code:
n, m = map(int, raw_input().split())
l = map(int, raw_input().split())
dp = [False for i in range(n + 1)]
for i in range(m):
    if l[i] <= n: dp[l[i]] = True
cnt = 1
while 1:
    if dp[n]: break
    for i in range(n+1):
        if dp[i]:
            for j in range(m):
                if i + l[j] <= n: dp[i+l[j]] = True
    cnt += 1
print cnt

Submission status: Wrong Answer

Solution code:
import sys

def solution(money, A):
    # write your code in Python 2.7
    N = len(A)
    dp = [sys.maxint for x in xrange(money + 1)]
    dp[0] = 0
    for i in range(0, money + 1):
        for j in range(0, N):
            if i + A[j] <= money:
                dp[i + A[j]] = min(dp[i + A[j]], dp[i] + 1 )
        
    return dp[money]

Submission status: Wrong Answer

Solution code:
import sys

def solution(money,M, A):
    # write your code in Python 2.7
    N = len(A)
    dp = [sys.maxint for x in xrange(money + 1)]
    dp[0] = 0
    for i in range(0, money + 1):
        for j in range(0, N):
            if i + A[j] <= money:
                dp[i + A[j]] = min(dp[i + A[j]], dp[i] + 1 )
        
    return dp[money]

Submission status: Wrong Answer

Solution code:
n,m=map(int,raw_input().split())
c=map(int,raw_input().split())
dp=[[0]+[float('inf')]*n]+[[0]+[float('inf')]*n for i in xrange(m)]

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

Submission status: Wrong Answer

Solution code:
from collections import deque

n, m = map(int, input().split())
d = list(map(int, input().split()))
dp = [100000 for i in range(n + 1)]

dp[n] = 0
que = deque()
que.append(n)

while len(que) > 0:
    front = que.popleft()
    for i in d:
        if front - i == 0:
            print(dp[front] + 1)
            que.clear()
            break
        if front > i:
            dp[front - i] = min(dp[front] + 1, dp[front - i])
            que.append(front - i)
        else:
            break

Submission status: Wrong Answer

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

"""
input:
15 6
1 2 7 8 12 50

output:
2
"""

import sys


def solve():
    rec[0] = 0
    for i in range(c_num):
        for j in range(coins[i], money):
            rec[j] = min(rec[j], rec[j - coins[i]] + 1)

    return rec


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    money, c_num = map(int, _input[0].split())
    coins = list(map(int, _input[1].split()))
    # assert len(coins) == c_num
    rec = [float('inf')] * money
    ans = solve()
    print(ans[-1])

Submission status: Wrong Answer

Solution code:
n = int(input().split()[0])
c = list(filter(lambda x:x <= n,map(int,input().split())))

minimum = [ i for i in range(n+1) ]
for i in c:
    minimum[i] = 1

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

print(minimum[n])

Submission status: Wrong Answer

Solution code:
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)]
i=n-1
while i>=0:
    for j in range(m+1):
        if j==c[i]:
            dp[i][j]=1
        elif j<c[i]:
            dp[i][j]=dp[i+1][j]
        else:
            dp[i][j]=min(dp[i+1][j],dp[i+1][j-c[i]]+1,dp[i][j-c[i]]+1)
    i-=1
print(dp[0][m])

Submission status: Wrong Answer

Solution code:
n, m = [int(el) for el in input().split(' ')]
c = [int(el) for el in input().split(' ')]

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

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

print(t[n])

Submission status: Wrong Answer

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: Wrong Answer

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


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Wrong Answer

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])
c.reverse()


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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
			depth -= 1
			return min
		else:
			depth += 1
			sum -= i
			min = select(sum+i)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Wrong Answer

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])
#c.reverse()


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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
			depth -= 1
			return min
		else:
			depth += 1
			sum -= i
			min = select(sum+i)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Wrong Answer

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)


#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Wrong Answer

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,n+1):
	memo.append(0)

#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	global memo
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	if memo[sum] > 0:
		depth -= 1
		return min
	
	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[sum] = min
	depth -= 1
	return min

select(0)

print(min)

Submission status: Wrong Answer

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

# Coin Changing Problem
INF = float('inf')
T = [INF] * n
T[0] = 0

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

print(T[-1])

Submission status: Wrong Answer

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 reversed(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: Wrong Answer

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

print(dp[-1])

Submission status: Wrong Answer

Solution code:
def solver(n ,m, coins):
  dp = [[20] * (n + 1) for i in range(m + 1)]
  for i in range(m + 1): dp[i][0] = 0
  for r in range(1, m + 1):
    for c in range(1, n + 1):
      if 0 > c - coins[r - 1]:
        dp[r][c] = dp[r - 1][c]
      else:
        dp[r][c] = min(dp[r - 1][c], dp[r][c - coins[r - 1]] + 1)
  print(dp[m][n])


n, m = map(int, input().split())
coins = sorted(list(map(int, input().split())))
solver(n, m, coins)

Submission status: Wrong Answer

Solution code:
n, m=[int(w) for w in input().split()]
cs=[int(w) for w in input().split()]
res=50001
def comb(i, acc):
    global cs, m
    if i>=m:
        compute(acc)
        return
    comb(i+1, acc)
    acc.append(cs[i])
    comb(i+1, acc)
    acc.pop()
def compute(lst):
    global res, n
    lst=reversed(sorted(lst))
    print(lst)
    r=0
    v=n
    for e in lst:
        r+=v//e
        v%=e
        if v==0:
            res=min(res, r)
            break
comb(0, [])
print(res)

Submission status: Wrong Answer

Solution code:
n, m=[int(w) for w in input().split()]
cs=[int(w) for w in input().split()]
res=50001
def comb(i, acc):
    global cs, m
    if i>=m:
        compute(acc)
        return
    comb(i+1, acc)
    acc.append(cs[i])
    comb(i+1, acc)
    acc.pop()
def compute(lst):
    global res, n
    lst=reversed(sorted(lst))
    r=0
    v=n
    for e in lst:
        r+=v//e
        v%=e
        if v==0:
            res=min(res, r)
            break
comb(0, [])
print(res)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
c = list(map(int, input().split()))
maisuu = 0
rem = n
for i in range(m-1, -1, -1):
    if rem >= c[i]:
        d = rem // c[i]
        maisuu += d
        rem -= c[i] * d
print(maisuu)

Submission status: Wrong Answer

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

maisuu = 0
rem = n
for i in range(m-1, -1, -1):
    if rem >= c[i]:
        d = rem // c[i]
        maisuu += d
        rem -= c[i] * d
print(maisuu)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort()
maisuu = 0
rem = n
for i in range(m-1, -1, -1):
    if rem >= c[i]:
        d = rem // c[i]
        maisuu += d
        rem -= c[i] * d
print(maisuu)

Submission status: Wrong Answer

Solution code:
def cs(n, p, c):
    global count, m
    if p >= count:
        return m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
print(c)
count = n
print(cs(n, 0, c))

Submission status: Wrong Answer

Solution code:
def cs(n, p, c):
    global count, m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] + 1 >= count:
        return m
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
print(c)
count = n
print(cs(n, 0, c))

Submission status: Wrong Answer

Solution code:
def cs(n, p, c):
    global count, m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] + 1 >= count:
        return m
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
count = n
print(cs(n, 0, c))

Submission status: Wrong Answer

Solution code:
def cs(n, p, c):
    global count, m
    if n % c[0] == 0:
        count = min(count, p + n // c[0])
        return count
    elif p + n // c[0] >= count:
        return m
    elif c[0] < n:
        return min(cs(n - c[0], p + 1, c), cs(n, p, c[1:]))
    else:
        return cs(n, p, c[1:])

n, m = map(int, input().split())
c = list(map(int, input().split()))
c.sort(reverse = True)
count = n
print(cs(n, 0, c))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

table = [[0 for j in range(n+1)] for i in range(m)]
table[0][1:] = [float('inf') for j in range(1, n+1)]
for i in range(1, m):
    for j in range(1, n+1):
        if j - c[i] < 0:
            table[i][j] = table[i-1][j]
        else:
            table[i][j] = min(table[i-1][j], table[i][j-c[i]]+1)

print(table[-1][-1])

Submission status: Wrong Answer

Solution code:
import itertools as it
n, m = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
for i in range(m):
    for comb in it.combinations(c, i):
        if sum(comb) == n:
            print(i)
            exit()

Submission status: Wrong Answer

Solution code:
import itertools as it
n, m = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
for i in range(m):
    for comb in it.combinations_with_replacement(c, i):
        if sum(comb) == n:
            exit()

Submission status: Wrong Answer

Solution code:
import itertools as it
n, m = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
for i in range(m):
    for comb in it.combinations_with_replacement(c, i):
        if sum(comb) == n:
            print(i)
            exit()

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
cs = list(map(int, input().split()))
dp = [True]*(n+1)
dp[0] = 0
while 1:
    if dp[n]:
        break
    for d in range(n+1):
        if (dp[d]):
            continue
        for c in cs:
            if (dp[d+c]):
                dp[d+c] = dp[d]+1
            elif d+c < n+1:
                dp[d+c] = min(dp[d+c], dp[d] + 1)
print(dp[n])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
cs = list(map(int, input().split()))
dp = [10*9]*(n+1)
dp[0] = 0
for i in range(n+1):
    for c in cs:
        if i+c < n+1:
            dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
cs = list(map(int, input().split()))
dp = [10*5]*(n+1)
dp[0] = 0
for i in range(n+1):
    for c in cs:
        if i+c < n+1:
            dp[i+c] = min(dp[i+c], dp[i]+1)
print(dp[n])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
INF = 1000000000000000000000000

@lru_cache(None)
def dp(m, n):
    if n == N:
        return 0
    if n > N or m == M:
        return INF
    i = 0
    a = INF
    while c[m] * i + n <= N:
        a = min(a, dp(m + 1, n + c[m] * i) + i)
        i += 1
    return a
N, M = map(int, input().split())
c = list(map(int, input().split()))
print(dp(0, 0))

Submission status: Time Limit Exceeded

Solution code:
n, M = map(int, raw_input().split())
C = map(int, raw_input().split())
c1 = C[0]
chart = {c1*x1: [x1] for x1 in range((n / c1) + 2) if (c1*x1) <= n}
for m in range(1, M):
    c = C[m]
    tmp = {}
    for xi in range((n / c) + 2):
        for price, x_comb in chart.items():
            p = price + (c * xi)
            if p > n:
                break
            c_count = sum(x_comb) + xi
            if sum(chart[p]) >= c_count:
                tmp[p] = [x for x in x_comb]
                tmp[p].append(xi)

    chart = {price: tmp[price] if price in tmp.keys() else x_comb for price, x_comb in chart.items()}

print sum(chart[n])

Submission status: Time Limit Exceeded

Solution code:
import copy
n, M = map(int, raw_input().split())
C = map(int, raw_input().split())
c1 = C[0]
chart = {c1*x1: [x1] for x1 in range((n / c1) + 2) if (c1*x1) <= n}
for m in range(1, M):
    c = C[m]
    tmp = {}
    if c > n:
        continue
    else:
        for xi in range((n / c) + 2):
            tmp_chart = copy.copy(chart)
            for price, x_comb in tmp_chart.items():
                p = price + (c * xi)
                if p > n:
                    break
                c_count = sum(x_comb) + xi
                if sum(chart[p]) >= c_count:
                    chart[p] = copy.copy(x_comb)
                    chart[p].append(xi)
print sum(chart[n])

Submission status: Time Limit Exceeded

Solution code:
import copy
n, M = map(int, raw_input().split())
C = map(int, raw_input().split())
c1 = C[0]
chart = {c1*x1: x1 for x1 in range((n / c1) + 2) if (c1*x1) <= n}
for m in range(1, M):
    c = C[m]
    tmp = {}
    if c > n:
        continue
    else:
        for xi in range((n / c) + 2):
            tmp_chart = copy.copy(chart)
            for price, x_sum in tmp_chart.items():
                p = price + (c * xi)
                c_count = x_sum + xi
                if p > n:
                    break
                if chart[p] >= c_count:
                    chart[p] = c_count
print chart[n]

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, raw_input().split())
l = map(int, raw_input().split())
dp = [False for i in range(n + 1)]
for i in range(m):
    if l[i] <= n: dp[l[i]] = True
cnt = 1
while 1:
    if dp[n]: break
    ndp = [False for i in range(n + 1)]
    for i in range(n+1):
        if dp[i]:
            ndp[i] = True
            for j in range(m):
                if i + l[j] <= n: ndp[i+l[j]] = True
    cnt += 1
    dp = ndp
print cnt

Submission status: Time Limit Exceeded

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] = [None for _ in range(N)]
for j in range(N):
	M[0][j] = 0
for i in range(C+1):
	M[i][0] = i
for i in range(1, C+1):
	for j in range(1, N):
		M[i][j] = min([ (M[i-x*V[j]][j-1] + x) for x in range(i//V[j] + 1) ])
print(M[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools

def coin_change(coins, val):
    num = 1
    while True:
        for subset in itertools.combinations_with_replacement(coins, num):
            if sum(subset) == val:
                return num
        num += 1

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

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

ans = coin_change(c, n)

print(ans)

Submission status: Time Limit Exceeded

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


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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])
c.reverse()


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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])
c.reverse()


min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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

while 1:
	if n < max(d):
		d.pop()
	else:
		x = max(d)
		break

min = int(n/x) + (n%x)
#print(min)


#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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

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

#print(min)


#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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)


#min = 100000000
depth = 0

def select(sum):
	global min
	global depth
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
	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)
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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 min
	global depth
	global memo
	done = []
	
	if depth > min:
		depth -= 1
		return min
	
#	if memo[depth] > 0:
#		depth -= 1
#		return min
	
	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] = min
	depth -= 1
	return min

select(0)

print(min)

Submission status: Time Limit Exceeded

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 min < depth:
			return min
		
		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: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
l = list(map(int, input().split()))
d = [0] * (n+1)

for i in range(1,n+1):
    if i in l:
        d[i] = 1
    else:
        min = 50000
        for j in range(i+1):
            if d[i-j]+d[j] < min and d[i-j]+d[j]>0:
                min = d[i-j] + d[j]
        d[i] = min

print(d[n])

Submission status: Time Limit Exceeded

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 reversed(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()