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

c_large.py

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

	a=0;n=1;s=0;pn=0
	while n<=V:

		if n in d:
			n,s,pn=(n*C)+s+1,(n*C)+s,n

		else:
			for j in range(D):
				if n>d[j] and d[j]>pn:
					k=0
					while j+k<D and n>d[j+k] and d[j+k]>pn:
						s+=d[j+k]*C
						k+=1
					n,pn=s+1,n
					break

				if d[j]>n:
					a+=1
					n,s,pn=(n*C)+s+1,(n*C)+s,n
					break

			else:
				a+=1
				n,s,pn=(n*C)+s+1,(n*C)+s,n

	t+=1
	print "Case #%d: %d"%(t,a)