Problem:


Score : 600 points

Problem Statement

AtCoDeer the deer has N cards with positive integers written on them. The number on the i-th card (1≤i≤N) is a_i.
Because he loves big numbers, he calls a subset of the cards good when the sum of the numbers written on the cards in the subset, is K or greater.

Then, for each card i, he judges whether it is unnecessary or not, as follows:

If, for any good subset of the cards containing card i, the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.

Otherwise, card i is NOT unnecessary.

Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

1≤a_i≤10^9 (1≤i≤N)

Partial Score

300 points will be awarded for passing the test set satisfying N,K≤400.

Input

The input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

There are two good sets: {2,3} and {1,2,3}.

Card 1 is only contained in {1,2,3}, and this set without card 1, {2,3}, is also good. Thus, card 1 is unnecessary.

For card 2, a good set {2,3} without card 2, {3}, is not good. Thus, card 2 is NOT unnecessary.

Neither is card 3 for a similar reason, hence the answer is 1.

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Runtime Error

Solution code:
def whatIsMinNumber(X_copy,K):
    pickupNum = X_copy[len(X_copy)//2]
    X_rest = X[:]
    X_rest.remove(pickupNum)
    if can_do_number(X_rest,0,K-pickupNum,K-1):
        if len(X_copy) > 2:
            return whatIsMinNumber(X_copy[len(X_copy)//2+1:len(X_copy)],K)
        else:
            return pickupNum
    else:
        if len(X_copy) > 1:
            return whatIsMinNumber(X_copy[0:len(X_copy)//2],K)
        else:
            return pickupNum+1

def can_do_number(X,sum,min,max):
    if len(X) == 0:
        return False
    for i in range(0,len(X)):
        if min <= sum+X[i] <= max:
            return True
        elif min > sum+X[i]:
            X_rest = X[:]
            sum = sum + X_rest.pop(i)
            can_do_number(X_rest,sum,min,max)
        else:
            pass
    return False

N,K = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort(reverse = True)
thenum = whatIsMinNumber(X[:],K)
print(len(list(filter((lambda x:x<thenum),X))))

Submission status: Runtime Error

Solution code:
def whatIsMinNumber(X_copy,K):
    pickupNum = X_copy[len(X_copy)//2]
    X_rest = X[:]
    X_rest.remove(pickupNum)
    if can_do_number(X_rest,pickupNum,K,K+pickupNum-1):
        if len(X_copy) > 2:
            return whatIsMinNumber(X_copy[len(X_copy)//2+1:len(X_copy)],K)
        else:
            return pickupNum
    else:
        if len(X_copy) > 1:
            return whatIsMinNumber(X_copy[0:len(X_copy)//2],K)
        else:
            return pickupNum+1

def can_do_number(X,sum,min,max):
    #残りのカードがない場合はFalseを返す
    if len(X) == 0:
        return False
    #残りのカードで順番に調べる
    for i in range(0,len(X)):
        if min <= sum+X[i] <= max:
            return True
        elif min > sum+X[i]:
            X_rest = X[:]
            sum = sum + X_rest.pop(i)
            can_do_number(X_rest,sum,min,max)
        else:
            pass
    return False

N,K = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort(reverse = True)
thenum = whatIsMinNumber(X[:],K)
print(len(list(filter((lambda x:x<thenum),X))))

Submission status: Runtime Error

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

import array


n, k = map(int, input().split())
cards = list(map(int, input().split()))

needs = 0
for i, val in enumerate(cards):
    if val >= k:
        needs += 1
        continue

    c_without_i = cards[:i] + cards[i + 1:]

    dp = array.array('b', [0] * k)
    dp2 = array.array('b', [0] * k)
    b = False
    for m in c_without_i:
        if m >= k: continue
        for j, v in enumerate(dp):
            dp2[i] = v
            if v is 1 and (j + m) < k:
                if k - val <= j + m:
                    needs += 1
                    b = True
                    break
                dp2[j + m] = 1

        if b:
            break

        dp2[m] = 1
        dp, dp2 = dp2, dp

print(n - needs)

Submission status: Runtime Error

Solution code:
def calc(lst, k):
	sum = 0
	i = 0
	
	while sum < k and i < len(inptsort):
		sum += lst[i]
		i += 1
	
	if sum < k:
		return i
	else:
		df = sum - k
		sum2 = 0
		j = 0
		
		while sum2 < df and j < i:
			sum2 += lst[j]
			j += 1
		
		if lst[j-1] != lst[j]:
			return j
		else:
			j -= 1
			while j >= 1:
				if lst[j-1] != lst[j]:
					return j
				j -= 1
			return 0

inpt1 = map(int, raw_input().split())
inpt2 = map(int, raw_input().split())

inptsort = sorted(inpt2)

print calc(inptsort, inpt1[1])

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = sorted(filter(lambda x: x < k, map(int, input().split())))


def check(start, end, l):
    s = set()
    s.add(0)
    for i in l:
        for x in s.copy():
            if start <= i + x and i + x < end:
                return True
            if i + x < start:
                s.add(i + x)
    return False


p1 = 0
p2 = len(a)
res = None
while p1 < p2:
    i = (p1 + p2) // 2
    b = a.copy()
    b.pop(i)
    res = check(k - a[i], k, b)
    if res:
        p2 = i
    else:
        p1 = i + 1
print(i if res else i + 1)

Submission status: Runtime Error

Solution code:
#### TLE ####

n, k = map(int, input().split())
a = sorted((filter(lambda x: x < k, map(int, input().split()))))


def check(start, end, l):
    s = set()
    s.add(0)
    for i in l:
        for x in s.copy():
            if start <= i + x and i + x < end:
                return True
            if i + x < start:
                s.add(i + x)
    return False


p1 = 0
p2 = len(a)
res = None
while p1 < p2:
    i = (p1 + p2) // 2
    b = a.copy()
    b.pop(i)
    res = check(k - a[i], k, b)
    if res:
        p2 = i
    else:
        p1 = i + 1
print(i if res else i + 1)

Submission status: Runtime Error

Solution code:

def main():
    N, K = map(int, raw_input().split())
    cards = map(int, raw_input().split())
    c = []
    while sum(c) <= K:
        c.append(cards.pop(cards.index(min(cards))))
        if len(cards) == 0 and sum(c) < K:
            print len(c)
            return 0
    count = 0
    while sum(c) >= K:
        c.pop(c.index(min(c)))
        count += 1
    print count-1


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/local/bin/python3

import bisect

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
l = bisect.bisect_left(a, k)
a = a[0:l]

minsum = k - a[-1]

stf = [[False for j in range(k)] for i in range(l)]
stb = [[False for j in range(k)] for i in range(l)]

stf[0][a[0]] = True
stf[0][0] = True
for i in range(1, l):
    for x in range(k):
        if x - a[i] >= 0:
            stf[i][x] = stf[i - 1][x] | stf[i - 1][x - a[i]]
        else:
            stf[i][x] = stf[i - 1][x]


stb[l - 1][a[l - 1]] = True
stb[l - 1][0] = True
for i in range(l - 2, -1, -1):
    for x in range(k):
        if x - a[i] >= 0:
            stf[i][x] = stf[i + 1][x] | stf[i + 1][x - a[i]]
        else:
            stf[i][x] = stf[i + 1][x]

cc = 0
for i in range(l):
    found = False
    for x in range(k - a[i], k):
        if i == 0:
            if stb[1][x] == True:
                found = True
                break
        elif i == l - 1:
            if stf[l - 2][x] == True:
                found = True
                break
        else:
            for y in range(x + 1):
                if stf[i - 1][y] == True and stb[i + 1][x - y] == True:
                    found = True
                    break
            if found:
                break

    if found:
        break
    else:
        cc += 1
        
print(cc)

Submission status: Runtime Error

Solution code:
#!/usr/local/bin/python3

import bisect

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
i = bisect.bisect_left(a, k)
a = a[0:i]

ct = {}
ad = []
prevnum = 0
cc = 1
for i in a:
    if prevnum != i:
        ct[prevnum] = cc

        ad.append(i)
        prevnum = i
        cc = 1
    else:
        cc += 1
else:
    ct[prevnum] = cc

a = ad

#print(a)
#print(ct)


def getSumComb(a, idx, cur, sl, minsum, maxsum):
    pairs = []
    num = a[idx]
    c = ct[num]
    for i in range(0, c + 1):
        if cur + num * i < minsum:
            slc = sl[:]            
            for j in range(i):
                slc.append(num)
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        slc,
                                        minsum,
                                        maxsum))                 
        elif minsum <= cur + num * i < maxsum:
            slc = sl[:]
            for j in range(i):
                slc.append(num)
            slcc = slc[:]
            if i > 0:
                pairs.append((cur + num * i, slc))
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        slcc,
                                        minsum,
                                        maxsum))
        elif maxsum <= cur + num * i:
            break
    
    return pairs

if len(a) > 0:
    pairs = getSumComb(a, 0, 0, [], k - a[-1], k)
else:
    pairs = []
    
pairs = sorted(pairs)

#print(pairs)

nn = 0
for num in a:
    minsum = k - num
    p = (minsum, [])
    idx = bisect.bisect_left(pairs, p)
    found = False
    for i in range(idx, len(pairs)):
        if pairs[i][1].count(num) < ct[num]:
            found = True
            break

    if not found:
      nn += ct[num]  

print(nn)

Submission status: Runtime Error

Solution code:
#!/usr/local/bin/python3

import bisect

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
i = bisect.bisect_left(a, k)
a = a[0:i]

ct = {}
ad = []
prevnum = 0
cc = 1
for i in a:
    if prevnum != i:
        ct[prevnum] = cc

        ad.append(i)
        prevnum = i
        cc = 1
    else:
        cc += 1
else:
    ct[prevnum] = cc

a = ad

#print(a)
#print(ct)


def getSumComb(a, idx, cur, sl, minsum, maxsum):
    pairs = []
    num = a[idx]
    c = ct[num]
    for i in range(0, c + 1):
        if cur + num * i < minsum:
            slc = sl[:]            
            for j in range(i):
                slc.append(num)
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        slc,
                                        minsum,
                                        maxsum))                 
        elif minsum <= cur + num * i < maxsum:
            slc = sl[:]
            for j in range(i):
                slc.append(num)
            slcc = slc[:]
            if i > 0:
                pairs.append((cur + num * i, slc))
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        slcc,
                                        minsum,
                                        maxsum))
        elif maxsum <= cur + num * i:
            break
    
    return pairs

pairs = getSumComb(a, 0, 0, [], k - a[-1], k)
pairs = sorted(pairs)

#print(pairs)

nn = 0
for num in a:
    minsum = k - num
    p = (minsum, [])
    idx = bisect.bisect_left(pairs, p)
    found = False
    for i in range(idx, len(pairs)):
        if pairs[i][1].count(num) < ct[num]:
            found = True
            break

    if not found:
      nn += ct[num]  

print(nn)

Submission status: Runtime Error

Solution code:
    import itertools
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    need = []
    iranaiko = []
    for a in A:
    	if a >= K:
    		need.append(a)
    	elif a in need:
    		need.append(a) 
    	elif a in iranaiko:
    		pass
    	else:
    		z = 0
    		B = A[:]
    		B.remove(a)
    		fusoku = [K - i - 1 for i in range(a)]
    		for bi,b in enumerate(B):
    			if b >= K:
    				break
    		B = B[:bi + 1]
    		for i in range(1,len(B) + 1):
    			C = list(itertools.combinations(B,i))
    			for c in C:
    				if sum(c) in fusoku:
    					need.append(a)
    					z = 1
    					break
    			if z == 1:
    				break
    		if z == 0:
    			iranaiko.append(a)
    print(N - len(need))

Submission status: Runtime Error

Solution code:
def main():
    global K,N,A,AM
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    flag = (max(A) >= K)  # よい部分集合がないということはない
    AM = sum(A)
    if not flag and AM < K:  # よい集合が存在しない
        print(len(A))
        return

    print(binary_search_for_integer(len(A)-1, -1)-1)


def binary_search_for_integer(ok, ng):
    while math.fabs(ok-ng) > 1:
        mid = (ok+ng)/2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def solve(x):
    if AM - x >= K:
        return False
    else:
        return True


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
a, b=map(int,input().split())
s=list(map(int,input().split()))
k=1
if(sum(s)<b):
	print(a)
	k=2
s.sort()
ss=list(filter(lambda x: x < b, s))
i=int(0)

while(k==1):
	del ss[0]
	if(sum(ss)==b):
		i=i+1
		print(i)
		k=2
	elif(sum(ss)<=b):
		print(i)
		k=2
	i=i+1

Submission status: Runtime Error

Solution code:
K = int(raw_input().split(" ")[1])
d = map(int, raw_input())
s = sum(d)
c = 0
for i in d:
	if s - i > K:
		c += 1
print c

Submission status: Runtime Error

Solution code:
a, b=map(int,input().split())
s=list(map(int,input().split()))
s.sort()
if(sum(s)<b):
	print(a)
	k=2
ss=list(filter(lambda x: x < b, s))
i=int(0)
k=1
while(k==1):
	del ss[0]
	if(sum(ss)==b):
		i=i+1
		print(i)
		k=2
	elif(sum(ss)<=b):
		print(i)
		k=2
	i=i+1

Submission status: Runtime Error

Solution code:
a, b=map(int,input().split())
s=list(map(int,input().split()))
s.sort()
if(sum(ss)<b):
	print(a)
	k=2
ss=list(filter(lambda x: x < b, s))
i=int(0)
k=1
while(k==1):
	del ss[0]
	if(sum(ss)==b):
		i=i+1
		print(i)
		k=2
	elif(sum(ss)<=b):
		print(i)
		k=2
	i=i+1

Submission status: Runtime Error

Solution code:
def calcsum(a, K, i, d=0, s=0):
    if K - a[i] <= s < K:
        return True
    elif i == d:
        return calcsum(a, K, i, d+1, s)
    elif d == len(a):
        return False
    else:
        return calcsum(a, K, i, d+1, s) | calcsum(a, K, i, d+1, s+a[d])
    

N, K = map(int, input().split())
a = list(map(int, input().split()))
a_sum = sum(a)

count = 0
for i in range(N):
    count += calcsum(a, K, i)
count = N - count
print(count)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int, input().split()))
sm = sum(a)
if k>sm: print(n)
else:
    table = [[0] for i in range(2*k)]
    table[0] = [-1]
    for elm in a:
        idxlist = []
        for i in range(2*k):
            if table[i] != [0]:
                if i+elm<2*k:
                    idxlist.append(i+elm)
        for idx in idxlist:
            table[idx].extend(table[idx-elm])
            table[idx].append(elm)

    need = 0
    for elm in a:
        if elm >= k: need += 1
        else:
            flag = False
            for i in range(k,k+elm):
                if elm in table[i]:
                    need += 1
                    break
    print(n-need)