Round 1C 2015: Problem C. Less Money, More Problems

c_small.py

from bisect import bisect_left

def ins_d(n):
	global d

	if n>=d[-1]:
		d+=[n]*C
	else:
		sep=bisect_left(d,n)
		d=d[:sep]+[n]*C+d[sep:]

def recur(n,m,s,l):
	global d,memo

	#print "Debug ",l

	if (n,m,s) in memo.keys():
		return memo[(n,m,s)]

	if s==n:
		if (n,m,s) not in memo.keys():
			memo[(n,m,s)]=True
		return True

	if m>=len(d) or d[m]>n:
		return False

	return recur(n,m+1,s+d[m],l+[d[m]]) or recur(n,m+1,s,l)

T=int(raw_input())
t=0
while t<T:
	C,D,V=map(lambda x:int(x),raw_input().split())
	d=sorted(map(lambda x:int(x),raw_input().split())*C)

	a=0
	for n in range(1,V+1):
		memo={}
		if not recur(n,0,0,[]):
			ins_d(n)
			a+=1
	t+=1
	print "Case #%d: %d"%(t,a)