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

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
V.sort()
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    K0 = K-V[i]
    VM = 2**(V[i]+1)-2
    l = 1
    if a & 1 == 0:
        l = a.bit_length()-1
        a >>= l
        b >>= l
    while a and b and l:
        if b & VM:
            ans -= 1
            break
        l = a.bit_length()-1
        a >>= l; b >>= l
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
*V, = map(int, input().split())
V.sort()
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    K0 = K-V[i]
    VM = 2**(V[i]+1)-2
    l = 1
    while a and b and l:
        l = a.bit_length()-1
        a >>= l; b >>= l
        if b & VM:
            ans -= 1
            break
print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)

def need(idx):
    a = src[idx]
    dp = [0 for i in range(K+1)]
    dp[0] = 1
    for i in range(N):
        if i == idx: continue
        b = src[i]
        for v, canmake in enumerate(list(dp)):
            if not canmake: continue
            if v+b < K-a:
                dp[v+b] = 1
            elif v+b < K:
                return True
    return False

l = 0
r = N
while r-l > 0:
    m = (l+r)//2
    if need(m):
        l = m+1
    else:
        r = m
print(N - l)

Submission status: Wrong Answer

Solution code:
N,K = map(int,raw_input().split())
src = map(int,raw_input().split())
src.sort(reverse=True)

def need(idx):
  a = src[idx]
  nums = set([0])
  for i in range(N):
    b = src[i]
    if i == idx: continue
    for v in list(nums):
      if K-a <= v+b < K:
        return True
      nums.add(v+b)
  return False

l = 0
r = N
while r-l > 0:
  m = (l+r) // 2
  if need(m):
    l = m+1
  else:
    r = m

print(N - l)

Submission status: Wrong Answer

Solution code:
ini=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
b=[]
for i in a:
    b.append(i)
b.reverse()
d_num=ini[0]
l_l=ini[0]
ans=0
c=0
while True:
    sum=0
    add=0
    for i in b:
        sum+=i
    if sum<ini[1] and c>0:
        b=[]
        ans+=d_num+1
        for i in range(l_l-d_num-1):
            b.append(a[i])
        c=0
        d_num=len(b)
        l_l=len(b)
        b.reverse()
    elif sum<ini[1] and c==0:
        break
    else:
        c=b[-1]
        b.pop(-1)
        d_num-=1
print ini[0]-ans

Submission status: Wrong Answer

Solution code:
ini=map(int,raw_input().split())
a=map(int,raw_input().split())
b=[]
for i in a:
    b.append(i)
b.sort()
c=[]
while True:
    sum=0
    add=0
    for i in b:
        sum+=i
    if sum<ini[1] and len(c)>=1:
        b.append(c[-1])
        c.pop(-1)
        c.reverse()
        time=0
        sum=0
        for i in c:
            sum+=i
            time+=1
            if sum>=ini[1]:
                add+=time
                sum=0
                time=0
        break
    elif sum<ini[1] and len(c)==0:
        b=c
        break
    else:
        c.append(b[0])
        b.pop(0)
print ini[0]-len(b)-add

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def can_discard(p, K, a_list):
    dp = [0] * K
    dp[0] = 1
    for i in range(len(a_list)):
        if i == p:
            continue

        for j in range(len(dp) - 1, -1, -1):
            if dp[j] == 0:
                continue
            if j + a_list[i] < len(dp):
                dp[j + a_list[i]] = 1

    x = a_list[p]
    for i in range(len(dp)):
        if dp[i] != 0 and i < K <= i + x:
            return False
    return True


def main():
    N, K = map(int, input().split())
    a_list = sorted(list(list(map(int, input().split()))))

    # [low, high)
    low, high, ans = -1, len(a_list), len(a_list)
    while high - low > 1:
        middle = (low + high) // 2
        if can_discard(middle, K, a_list):
            ans = middle + 1
            low = middle
        else:
            high = middle

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a, reverse=True)
ans = N
for i in range(N-1, -1, -1) :
    psum = 0
    for j in range(i, -1, -1) :
        if psum+a[j] < K :
            psum += a[j]
        else :
            ans = min(ans, j)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


n, k = read_int_list()
a = read_int_list()
c = 0

for x in a:
    if x < k//2:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<K:#全部不必要
  print(N)
  sys.exit()
if sum==K:#全部必要
  print(0)
  sys.exit()
a.sort()
a.reverse()
 
#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break
 
if l==N:
  print(0)
  sys.exit()
 
count=N
#lまでの要素が必要か不要かチェック(使いまわし可能)
sum=0
l_list=[]
for j in range(l,N):
  if sum+a[j]<K:
    sum+=a[j]
    l_list.append(a[j])
for i in range(0,l):  
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  if a[i] in l_list:
    count-=1
  else:
    sum=0
    b=a[:]
    C=b.pop(i)
    for j in range(l-1,N-1):
      if sum+b[j]<K:
        sum+=b[j]
    if sum+C>=K:#必要ってことだ
      count-=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<=K:
  print(N)
  sys.exit()
a.sort()
a.reverse()

#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break

if l==N:
  print(N)
  sys.exit()

count=N
#lまでの要素が必要か不要かチェック
for i in range(0,l):
  sum=0
  for j in range(l,N):
    if sum+a[j]<K:
      sum+=a[j]
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  sum=0
  b=a[:]
  C=b.pop(i)
  for j in range(l-1,N-1):
    if sum+b[j]<K:
      sum+=b[j]
  if sum+C>=K:#必要ってことだ
    count-=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<=K:
  print(N)
  sys.exit()
a.sort()
a.reverse()

#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break

if l==N:
  print(0)
  sys.exit()

count=N
#lまでの要素が必要か不要かチェック
for i in range(0,l):
  sum=0
  for j in range(l,N):
    if sum+a[j]<K:
      sum+=a[j]
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  sum=0
  b=a[:]
  C=b.pop(i)
  for j in range(l-1,N-1):
    if sum+b[j]<K:
      sum+=b[j]
  if sum+C>=K:#必要ってことだ
    count-=1
print(count)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
tmp = list(map(int, input().split()))
card = []
ans = 0
for c in tmp:
    if(c < K) :
        card.append(c)

dpf = []
dpr = []
dpf.append([0] * K)
dpr.append([0] * K)
dpf[0][0] = 1
dpr[0][0] = 1
for i in range(len(card)) :
    tmp = [0] * K
    c = card[i]
    for j in range(K - c) :
        if(dpf[-1][j] == 1) :
            tmp[j+c]  =1
            tmp[j] = 1
    dpf.append(tmp)
for i in reversed(range(len(card))) :
    tmp = [0] * K
    c = card[i]
    for j in range(K - c) :
        if(dpr[-1][j] == 1) :
            tmp[j+c] = 1
            tmp[j] = 1
    dpr.append(tmp)
reversed(dpr)

#print(dpf)
#print(dpr)
ans = len(card)
for i in range(len(card)) :
    x = dpf[i]
    y = dpr[len(card) - i - 1]
    itx = 0
    ity = K - 1
    c = card[i]
    for j in range(K) :
        if x[itx] == 1 :
            break
        itx += 1
    for j in range(K) :
        if y[ity] == 1 :
            break
        ity -= 1
    while True :
        if (itx + ity >= K - c and itx + ity < K) :
            ans -= 1
            break
        if (itx + ity < K - c) :
            if itx == K - 1 :
                itx += 1
            while itx+1 < K :
                itx += 1
                if x[itx] == 1 :
                    break
            if itx == K - 1 and x[itx]==0:
                itx += 1
            if itx  >= K :
                break
        if itx + ity >= K :
            if ity == 0 :
                ity -= 1
            while ity - 1 >= 0 :
                ity -= 1
                if y[ity]== 1 :
                    break
            if ity == 0 and y[ity] == 0:
                ity -= 1
            if ity < 0 :
                break

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
tmp = list(map(int, input().split()))
card = []
ans = 0
for c in tmp:
    if(c < K) :
        card.append(c)

dpf = []
dpr = []
dpf.append([0] * K)
dpr.append([0] * K)
dpf[0][0] = 1
dpr[0][0] = 1
for i in range(len(card)) :
    tmp = [0] * K
    c = card[i]
    for j in range(K - c) :
        if(dpf[-1][j] == 1) :
            tmp[j+c]  =1
            tmp[j] = 1
    dpf.append(tmp)
for i in reversed(range(len(card))) :
    tmp = [0] * K
    c = card[i]
    for j in range(K - c) :
        if(dpr[-1][j] == 1) :
            tmp[j+c] = 1
            tmp[j] = 1
    dpr.append(tmp)
reversed(dpr)

print(dpf)
print(dpr)
ans = len(card)
for i in range(len(card)) :
    x = dpf[i]
    y = dpr[len(card) - i - 1]
    itx = 0
    ity = K - 1
    c = card[i]
    for j in range(K) :
        if x[itx] == 1 :
            break
        itx += 1
    for j in range(K) :
        if y[ity] == 1 :
            break
        ity -= 1
    while True :
        if (itx + ity >= K - c and itx + ity < K) :
            ans -= 1
            break
        if (itx + ity < K - c) :
            if itx == K - 1 :
                itx += 1
            while itx+1 < K :
                itx += 1
                if x[itx] == 1 :
                    break
            if itx == K - 1 and x[itx]==0:
                itx += 1
            if itx  >= K :
                break
        if itx + ity >= K :
            if ity == 0 :
                ity -= 1
            while ity - 1 >= 0 :
                ity -= 1
                if y[ity]== 1 :
                    break
            if ity == 0 and y[ity] == 0:
                ity -= 1
            if ity < 0 :
                break

print(ans)

Submission status: Wrong Answer

Solution code:

import numpy as np

if 1:
    n,k = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
elif 0:
    n,k = 5000,500
    a = list(np.random.randint(5000,size=5000))
else:
    n,k = 6,20
    a = [10,4,3,10,25,2]

sum1 = np.zeros((n,k),dtype=bool)
sum1[0,0] = True
for i,a_ in enumerate(a[:-1]):
    for j in range(k):
        if j-a_ >= 0 and j < k:
            sum1[i+1,j] = (sum1[i,j-a_] or sum1[i,j])
        else:
            sum1[i+1,j] = sum1[i,j]

sum2 = np.zeros((n,k),dtype=bool)
sum2[0,0] = True
for i,a_ in enumerate(a[:0:-1]):
    for j in range(k):
        if j-a_ >= 0 and j < k:
            sum2[i+1,j] = (sum2[i,j-a_] or sum2[i,j])
        else:
            sum2[i+1,j] = sum2[i,j]   

res_sum = sum1+sum2[::-1]
ret = 0
for i,a_ in enumerate(a):
    sum_ = np.where(res_sum[i])
    max_ = max(sum_[0])
    if max_ >= k-a_:
        ret += 1
print(n-ret)

Submission status: Wrong Answer

Solution code:

import numpy as np

if 1:
    n,k = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
elif 0:
    n,k = 5000,500
    a = list(np.random.randint(5000,size=5000))
else:
    n,k = 6,20
    a = [10,4,3,10,25,2]

sum1 = np.zeros((n,k),dtype=bool)
sum1[0,0] = True
for i,a_ in enumerate(a[:-1]):
    for j in range(k):
        if j-a_ >= 0 and j < k:
            sum1[i+1,j] = (sum1[i,j-a_] or sum1[i,j])
        else:
            sum1[i+1,j] = sum1[i,j]

sum2 = np.zeros((n,k),dtype=bool)
sum2[0,0] = True
for i,a_ in enumerate(a[:0:-1]):
    for j in range(k):
        if j-a_ >= 0 and j < k:
            sum2[i+1,j] = (sum2[i,j-a_] or sum2[i,j])
        else:
            sum2[i+1,j] = sum2[i,j]   

res_sum = sum1+sum2
ret = 0
for i,a_ in enumerate(a):
    sum_ = np.where(res_sum[i])
    max_ = max(sum_[0])
    if max_ >= k-a_:
        ret += 1
print(n-ret)

Submission status: Wrong Answer

Solution code:
import numpy as np

if 0:
    n,k = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
elif 0:
    n,k = 5000,500
    a = list(np.random.randint(5000,size=5000))
else:
    n,k = 6,20
    a = [10,4,3,10,25,2]

sum1 = np.zeros((n,k),dtype=bool)
sum1[0,0] = True
for i,a_ in enumerate(a[:-1]):
    for j in range(k):
        if j-a_ >= 0 and j < k:
            sum1[i+1,j] = (sum1[i,j-a_] or sum1[i,j])
        else:
            sum1[i+1,j] = sum1[i,j]

sum2 = np.zeros((n,k),dtype=bool)
sum2[0,0] = True
for i,a_ in enumerate(a[:0:-1]):
    for j in range(k):
        if j-a_ >= 0 and j < k:
            sum2[i+1,j] = (sum2[i,j-a_] or sum2[i,j])
        else:
            sum2[i+1,j] = sum2[i,j]   

res_sum = sum1+sum2
ret = 0
for i,a_ in enumerate(a):
    sum_ = np.where(res_sum[i])
    max_ = max(sum_[0])
    if max_ >= k-a_:
        ret += 1
print(n-ret)

Submission status: Wrong Answer

Solution code:
import copy
import bisect

if 1:
    n,k = map(int, input().split(' '))
    a = list(map(int, input().split(' ')))
else:
    n,k = 3,6
    a = [1,4,3]

sum1 = []
sum_ = set([0])
sum1.append(sum_)
for a_ in a[:-1]:
    sum1_ = copy.deepcopy(sum_)
    for s_ in sum_:
        sum1_.add(s_+a_)
    sum1.append(sum1_)
    sum_ = sum1_

sum2 = []
sum_ = set([0])
sum2.append(sum_)
for a_ in a[:0:-1]:
    sum2_ = copy.deepcopy(sum_)
    for s_ in sum_:
        sum2_.add(s_+a_)
    sum2.append(sum2_)
    sum_ = sum2_
    
sum2 = sum2[::-1]
ret = 0
for i,a_ in enumerate(a):
    sum_ = sum1[i].union(sum2[i])
    sum_ = sorted(list(sum_))
    idx = bisect.bisect_left(sum_,k)-1
    if sum_[idx] >= k-a_:
        ret += 1
print(n-ret)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
for k in range(N):
    tmp = a[k]
    a[k] = 0
    dp = []
    for i in range(N):
      dp.append([])
      for j in range(K+1):
        if(j == 0):
          dp[i].append(True)
          continue
        dp[i].append(False)

    for i in range(N):
      for j in range(K+1):
        if(i == 0 and k != 0):
          if(j == a[i]): dp[i][j] = True
          continue
        elif(i == 1 and k == 0):
          if(j == a[i]): dp[i][j] = True
          continue
        elif(j - a[i] >= 0):
          if(dp[i - 1][j - a[i]] or dp[i - 1][j]): dp[i][j] = True
          else: dp[i][j] = False

        else:
          if(dp[i - 1][j]): dp[i][j] = True
          else: dp[i][j] = False

    for j in range(K-a[k], K+1):
      if(dp[N-1][j] == True):
        break
   
    ans += 1
    a[k] = tmp

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
cards = [int(i) for i in input().split()]

cards.sort()
gokei = 0
cnt = 0

for i in range(N):
    gokei += cards[i]
    if gokei >= K:
        break
    
if gokei < K:
    print(N)

else:
    for i in range(N):
        gokei -= cards[i]
        if gokei < K:
            break
        cnt +=1
    print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
cards = [int(i) for i in input().split()]

cards.sort()
gokei = 0
cnt = 0

for i in range(N):
    gokei += cards[i]
    if gokei >= K:
        print(i-1)
        break
    
if gokei < K:
    print(N)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
cards = [int(i) for i in input().split()]

cards.sort()
gokei = 0
cnt = 0

for i in range(N):
    gokei += cards[i]
    if gokei >= K:
        break
    
if gokei < K:
    print(N)

else:
    for i in range(N):
        gokei -= cards[i]
        if gokei < K:
            break
        cnt +=1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

N, K = map(int, input().split())
cards = [int(i) for i in input().split()]

cards.sort()
gokei = 0
cnt = 0

for i in range(N):
    gokei += cards[i]
    if gokei > K:
        break
    
if gokei < K:
    print(N)

else:
    for i in range(N):
        gokei -= cards[i]
        if gokei < K:
            break
        cnt +=1
    print(cnt)

Submission status: Wrong Answer

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 = [6,20,10,4,3,10,25,2]
N = X.pop(0)
K = X.pop(0)
X.sort(reverse = True)
thenum = whatIsMinNumber(X[:],K)
print(len(list(filter((lambda x:x<whatIsMinNumber(X[:],K)),X))))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split(' '))
a = list(map(int,input().split(' ')))
a = sorted(a, reverse=True)

result = 0
for i in range(n):
    buf = a[:i]+a[i+1:]
    dp = [0]
    for j in range(n-1):
        buf2 = [dp[j_]+buf[j] for j_ in range(j+1)]
        buf2 = [-1 if buf2_ >= k else buf2_ for buf2_ in buf2]
        dp.append(max(buf2))
    if max(dp) + a[i] < k:
        print(n-i)
        break

Submission status: Wrong Answer

Solution code:
# 合計がKを超えるINDEXを返す 何しても超えないときは-1を返す
def poppin(a, k):
    if len(a) == 0:
        return -1
    sum_ = 0
    for i in range(len(a)):
        sum_ += a[i]
        if(sum_ >= k):
            return i
    return -1


# 返ってきたindexまでの要素を消す
def pop_(a, ind):
    for i in range(ind + 1):
        a.pop(0)


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
while 0 == 0:
    d = poppin(a, k)
    if d == -1:
        break
    pop_(a, d)
print(len(a))

Submission status: Wrong Answer

Solution code:
# 合計がKを超えるINDEXを返す 何しても超えないときは-1を返す
def poppin(a, k):
    if len(a) == 0:
        return -1
    sum_ = 0
    for i in range(len(a)):
        sum_ += a[i]
        if(sum_ >= k):
            return i
    return -1


# 返ってきたindexまでの要素を消す
def pop_(a, ind):
    for i in range(ind + 1):
        a.pop(0)


def main():
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    a.sort()
    a = a[::-1]

    while 0 == 0:
        d = poppin(a, k)
        if d == -1:
            break
        pop_(a, d)
    print(len(a))

Submission status: Wrong Answer

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[j] = 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: Wrong Answer

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

import array


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

ar = array.array('b', (0 for _ in range(max_k + 1)))
ar2 = array.array('b', (0 for _ in range(max_k + 1)))

total = 0
over = 0
for a in cards:
    if a >= 5000:
        over += 1
        continue

    total += a
    for i, v in enumerate(ar[:total + 1]):
        ar2[i] = v or ar2[i]
        if (v is 1) and ((i + a) <= max_k):
            ar2[i + a] = 1
    ar2[a] = 1
    ar, ar2 = ar2, ar

if total < k:
    print(n)
else:
    for a in cards:
        if a >= 5000: continue
        if any(ar[k:k + a]): over += 1
    print(n - over)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
unnec = 0
if sum(A) < K:
    print(len(A))
    exit()

for i in range(0,N):
    B = list(A)
    v = B.pop(i)
    #print("%s, %d" % (str(B), v))
    nec = False
    for j in range(len(B),0,-1):
        if sum(B[-j:]) + v < K:
            break
        for l in list(itertools.combinations(B,j)):
            s = sum(l)
            if s < K and s + v >= K:
                nec = True
                break
        if nec == True:
            break
    if nec == False:
        unnec = unnec + 1
print(unnec)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
unnec = 0
for i in range(0,N):
    B = list(A)
    v = B.pop(i)
    nec = False
    for j in range(len(B),0,-1):
        for l in list(itertools.combinations(B,j)):
            s = sum(l)
            #print("%s, %d, %d" % (str(l), s, v))
            if s >= K:
                continue
            elif s + v >= K:
                nec = True
                break
        if nec == True:
            break
    if nec == False:
        unnec = unnec + 1
print(unnec)

Submission status: Wrong Answer

Solution code:
import copy
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

cnt = 0
for s in range(N):
    if a[s]<K:
        a2 = copy.deepcopy(a)
        a2.pop(s)
        dp = [[False for i in range(K + 1)] for j in range(N + 1)]
        dp[0][0] = True
        for i in range(1, N):
            for j in range(K + 1):
                if dp[i - 1][j] or (j >= a2[i - 1] and dp[i - 1][j - a2[i - 1]]):
                    dp[i][j] = True
        result = False
        for j in range(K-a[s], K-1):
            if dp[N-1][j]:
                result = True
                break
        if result:
            cnt += 1
    else :
        cnt +=1


print(N-cnt)

Submission status: Wrong Answer

Solution code:
from copy import deepcopy
from itertools import combinations


N, K = [int(i) for i in input().split()]
card_list = [int(i) for i in input().split()]

noneed_card_list = []
counter = 0

for i in range(N):
    iter_list = []
    target = card_list[i]
    counter = 0

    card_list_copy = deepcopy(card_list)
    del(card_list_copy[i])

    for k in range(1, N):
        iter_list.append(combinations(card_list_copy, k))

    for itr in iter_list:
        for lst in itr:
            if K-i <= sum(lst) < K:
                noneed_card_list.append(target)
                counter += 1
                break
        if counter > 0:
            break

print(noneed_card_list)

print(N - len(noneed_card_list))

Submission status: Wrong Answer

Solution code:
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

def sum(list,x,k):
    sum1 = list[x]
    for i in range(N):
        if i == x:
            continue
        else:
            sum1 += list[i]
            if sum1 >= k:
                break
    return sum1

a.sort()
count = 0
for i in range(N):
    if sum(a,i,K) <= K or sum(a,i,K) - a[i] >= K:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

def sum(list,x,k):
    sum1 = list[x]
    for i in range(N):
        if i == x:
            continue
        else:
            sum1 += list[i]
            if sum1 >= k:
                break
    return sum1

a.sort()
count = 0
for i in range(N):
    if a[i] >= K:
        break
    else:
        if sum(a,i,K) <= K or sum(a,i,K) - a[i] >= K:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

def sum(list,x,k):
    sum1 = list[x]
    for i in range(len(list)):
        if i == x:
            continue
        else:
            sum1 += list[i]
            if sum1 >= k:
                break
    return sum1

a.sort()
count = 0
for i in range(len(a)):
    if a[i] >= K:
        break
    else:
        if sum(a,i,K) - a[i] >= K:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
As = list(map(int, input().split()))
cnt = {}
for a in As:
    if a in cnt:
        cnt[a] += 1
    else:
        cnt[a] = 1

As = list(sorted(set(As)))
ans = 0
s0 = sum(As)
s = 0
for a in As:
    x = cnt[a]
    s += a * x
    if s < K and K <= s0 - s:
        ans += x
    else:
        break

if ans == 0:
    print(N)
else:
    print(ans)

Submission status: Wrong Answer

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

import bisect
import sys

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
l = bisect.bisect_left(a, k)
if l == 0:
    print(0)
    sys.exit()
    
    

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] or 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] or 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] and stb[i + 1][x - y]:
                    found = True
                    break
            if found:
                break

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

Submission status: Wrong Answer

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

import bisect
import sys

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
l = bisect.bisect_left(a, k)
if l == 0:
    print(0)
    sys.exit()
    
    

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

Solution code:
import functools
N, K = map(int, input().split())
As = list(map(int, input().split()))
As = list(sorted(As))
ans = 0
memo = {}
for i in range(N):
    a = As[i]
    if a in memo:
        ans += 1
        continue
    xs = As[0:i] + As[i + 1:]
    dp = [False for _ in range(K + 1)]
    dp[0] = True
    for x in xs:
        if K < x:
            break
        for j in range(K - x - 1, -1, -1):
            dp[j + x] |= dp[j]
    if not(functools.reduce(lambda x, y: x or y,
                            [dp[j] for j in range(max(K - a, 0), K)], False)):
        ans += 1
        memo[a] = True

if ans == 0:
    print(N)
else:
    print(ans)