Problem:


Score : 100 points

Problem Statement

There is a set A = \{ a_1, a_2, \ldots, a_N \} consisting of N positive integers.
Taro and Jiro will play the following game against each other.

Initially, we have a pile consisting of K stones.
The two players perform the following operation alternately, starting from Taro:

Choose an element x in A, and remove exactly x stones from the pile.

A player loses when he becomes unable to play.
Assuming that both players play optimally, determine the winner.

Constraints

All values in input are integers.

1 \leq N \leq 100

1 \leq K \leq 10^5

1 \leq a_1 < a_2 < \cdots < a_N \leq K

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 \ldots a_N

Output

If Taro will win, print First; if Jiro will win, print Second.

Sample Input 1

2 4
2 3

Sample Output 1

First

If Taro removes three stones, Jiro cannot make a move.
Thus, Taro wins.

Sample Input 2

2 5
2 3

Sample Output 2

Second

Whatever Taro does in his operation, Jiro wins, as follows:

If Taro removes two stones, Jiro can remove three stones to make Taro unable to make a move.

If Taro removes three stones, Jiro can remove two stones to make Taro unable to make a move.

Sample Input 3

2 7
2 3

Sample Output 3

First

Taro should remove two stones. Then, whatever Jiro does in his operation, Taro wins, as follows:

If Jiro removes two stones, Taro can remove three stones to make Jiro unable to make a move.

If Jiro removes three stones, Taro can remove two stones to make Jiro unable to make a move.

Sample Input 4

3 20
1 2 3

Sample Output 4

Second

Sample Input 5

3 21
1 2 3

Sample Output 5

First

Sample Input 6

1 100000
1

Sample Output 6

Second



Sample input:
2 4
2 3


Sample output:
First

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0,0]  for j in range(K+1)]
for i in range(1,K+1):
    for j in range(N):
        if i-a[j]>=0:
            dp[i][0]=max((dp[i-a[j]][1]+1)%2,dp[i][0])
            dp[i][1]=max((dp[i-a[j]][0]+1)%2,dp[i][1])
        
if dp[K][0]:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
dp=[0 for j in range(K+1)]
for i in range(1,K+1):
    for j in range(N):
        if i-a[j]>=0:
            dp[i]=max((dp[i-a[j]]+1)%2,dp[i])
if dp[K]:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


def main():
    N, K = map(int, input().split())
    A = tuple(sorted(map(int, input().split())))
    c = [0] * (K + 1)
    def dp(k, A, c, turn):
        if c[k] != 0:
            return c[k] * turn
        for i in A:
            if i > k:
                break
            if dp(k - i, A, c, -turn) == turn:
                c[k] = 1
                return turn
        c[k] = -1
        return -turn
    
    print('First' if dp(K, A, c, 1) == 1 else 'Second')


main()

Submission status: Accepted

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

def main():
    l = [False] * (K+1)
    for i in range(a[0] -1, K+1):
        l[i] = any(not l[i-j] if i >= j else False for j in a)
    if l[-1]:
        print('First')
    else:
        print('Second')


main()

Submission status: Accepted

Solution code:
def stones(a,k): # k個の石を取り合う a[i](sorted)個とることが可能な時必勝はどちらか
    n=len(a)
    dp=[False for _ in range(k+1)] #石がi個の時、dp[i]=Trueで勝利Falseで敗北
    for i in range(k+1):
        for j in range(n):
            if i-a[j]>=0:
                if not dp[i-a[j]]:
                    dp[i]=True
    if dp[k]:
        print("First")
    else:
        print("Second")


def main():
    n,k = map(int,input().split()) 
    a = list(map(int,input().split()))
    a.sort()
    stones(a,k)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline

N, K = map(int, readline().split())
a = list(map(int, readline().split()))

dp = [False] * (K + K + 1)
for i in range(K):
    if not dp[i]:
        for j in a:
            dp[i + j] = True

if dp[K]:
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K,*A = map(int,read().split())

dp = [0]*(K+K+1)
for n in range(K):
    if not dp[n]:
        for a in A:
            dp[n+a]=1

answer = 'First' if dp[K] else 'Second'
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K,*A = map(int,read().split())

dp = [0]*(K+K+1) # bitset
for n in range(K):
    if not dp[n]:
        for a in A:
            dp[n+a]=1

answer = 'First' if dp[K] else 'Second'
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,K,*A = map(int,read().split())

dp = [0]*(K+1) # bitset
for n in range(K):
    if not dp[n]:
        for a in A:
            if n+a>K:
                break
            dp[n+a]=1

answer = 'First' if dp[-1] else 'Second'
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import xor
from functools import reduce

N,K,*A = map(int,read().split())

a = reduce(xor,(1<<a for a in A))

dp = 0 # bitset
for n in range(K):
    if not(dp&(1<<n)):
        dp |= (a<<n)

answer = 'First' if dp&(1<<K) else 'Second'
print(answer)

Submission status: Accepted

Solution code:
WIN  = 1
LOSE = 0

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

Sa = set(a)
Sk = set()

dp = [LOSE] * (K+1)

for k in range(1, K+1):
    if k in Sa: 
        dp[k] = WIN
        Sk.add(k)
    else:
        for i in range(N):
            if k-a[i] >0:
                if k-a[i] not in Sk:
                    dp[k] = WIN
                    Sk.add(k)
                    break

#print(Sa, K, Sk)
#print(dp[1:])
if dp[-1] == 1:
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
import sys
n, k = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]
memo_ls = [-1 for i in range(k+1)]
memo_ls[0] = -1
for i in range(1, k+1):
    for a in a_ls:
        if a > i:
            continue
        memo_ls[i] = max(memo_ls[i - a] * (-1), memo_ls[i])
ans = ["","First", "Second"]
print(ans[memo_ls[-1]])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [-1]*(k+1) #dp[i]:i個の山の勝敗 -1の時後手の勝ち
for i in range(1,k+1):
    for a in A:
        if a <= i and dp[i-a] == -1:
            dp[i] = 1
            break

#print(dp)

print("First" if dp[k] == 1 else "Second")

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [-1]*(k+1) #dp[i]:i個の山の勝敗
dp[0] = -1 #後手の勝ち
for i in range(1,k+1):
    for a in A:
        if a <= i and dp[i-a] == -1:
            dp[i] = 1
            break

#print(dp)

print("First" if dp[k] == 1 else "Second")

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
dp=[0]*(k+1)
for i in range(a[0]):
    dp[i]="s"
for u in a:
    dp[u]="f"
for i in range(a[0]+1,k+1):
    if dp[i]==0:
        for u in a:
            if i<u:
                continue
            else:
                if dp[i-u]=="s":
                    dp[i]="f"
                    break
        else:
            dp[i]="s"
if dp[k]=="f":
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
def main():
    n, k = map(int, input().split())
    a_list = list(map(int, input().split()))

    dp = [0] * (k+1)
    # dp[0] == 0 ならばそのとき手番の者（先手）の負け
    for i in range(k+1):
        for a in a_list:
            if dp[i] == 0:
                idx = i + a
                if idx < k+1:
                    dp[idx] = 1

    if dp[k] == 0:
        print('Second')
    else:
        print('First')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,K=map(int,input().split())
a = list(map(int, input().split()))
dp = [False]*(K+1)

for i in range(1,K+1):
    for j in range(N):
        if i-a[j]<0: break
        if not(dp[i-a[j]]):
            dp[i]=True
            break
if dp[K]:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
import bisect

N,K = map(int,input().split())
A = list(map(int,input().split()))

# dp[i]:残りの石がi個の時、先手が負けなら0、勝ちなら1
dp = [0 for _ in range(K+1)]

for i in range(1,K+1):
  rank = bisect.bisect_right(A, i)
  if rank == 0:
    dp[i] = 0
  else:
    for j in range(rank):
      if i-A[j] >= 0 and dp[i-A[j]] == 0:
        dp[i] = 1
        break
print('First' if dp[K] == 1 else 'Second')

Submission status: Accepted

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

dp = [-1] * (K+1)
ans = int(0)

for i in a:
    dp[i] = int(1)
#print(dp)
for i in range(K+1):
    v = int(-1)
    for j in a:
        if i>j and dp[i-j]==-1:
            v = int(1)
    if dp[i]==-1:
        dp[i] = v

if dp[K]==1:
    ans = "First"
else:
    ans = "Second"

print(ans)

Submission status: Accepted

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

dp = [None] * (K + 1)
dp[0] = False  # 手番が回ってきた時に0個の場合は必ず負け
for i in range(1, K + 1):
    # 手番を回して、相手が負けのものが一つでもあれば勝ち
    dp[i] = any(not dp[i - x] for x in a if x <= i)

if dp[K]:
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
n,k = list(map(int,input().split()))
a = list(map(int,input().split()))
dp=[0]*(k+1)
for i in range(1,k+1):
    for j in a:
        if i>=j and dp[i-j]==0:
            dp[i]=1
            break
if dp[k]:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[0]*(k+1)
    for i in range(k):
        if dp[i]: continue
        for j in range(n):
            if i+A[j]<=k: dp[i+A[j]]=1
    print("First" if dp[k] else "Second")
resolve()

Submission status: Accepted

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

objs = [None for i in range(K+1)]

objs[0] = -1

for i in range(K+1):
    score = -1
    for a in vals:
        if a <= i:
            score = max(score, -objs[i-a])
    objs[i] = score

if objs[-1] == 1:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC K

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,k = LI()
a = LI()
dp = [False]*(k+1)
for i in range(k+1):
    for j in a:
        if j <= i:
            if not dp[i-j]:
                dp[i] = True
if dp[-1]:
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
n, k = map(int, input().split())

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

dp = [0]*(k+1)
#0は先手負け、1が先手勝ち

for i in range(a[0],k+1):
    for p in a:#負かす手があれば勝ち
        if i-p >= 0 and dp[i-p] == 0:
            dp[i] = 1
            break
if dp[k] == 1:
    print("First")
else:
    print("Second")

Submission status: Accepted

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

dp = [''] * (K + 1)
dp[0] = 'Second'

for i in range(K+1):
    if dp[i] == '':
        dp[i] = 'Second'
        for j in a:
            if j > i:
                break
            if dp[i-j] == 'Second':
                dp[i] = 'First'
                break
    if dp[i] == 'Second':
        for j in a:
            if i + j > K:
                break
            dp[i+j] = 'First'

print(dp[K])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, k = map(int, input().split())
a = tuple(map(int, input().split()))

dp = [None] * (k + k + 1)
# dp[手番の石の数] := 手番の勝敗
# True(勝ち) / None(負け)

for opponent_remains in range(k):  # 自分が石を取った残りなので、k未満
    if dp[opponent_remains] is None:  # 相手が負ける場合
        for my_take in a:  # 自分が取る石の数
            my_remains = opponent_remains + my_take  # 相手が負けるようにできる、自分の手番の石の数
            dp[my_remains] = True

ans = dp[k]
print('First' if ans else 'Second')

# 内側のループに入る前に枝刈りしているので、速い

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = tuple(map(int, input().split()))

dp = [None] * (k + k + 1)
# dp[手番の石の数] := 手番の勝敗
# True(勝ち) / None(負け)

for opponent_remains in range(k):  # 自分が石を取った残りなので、k未満
    if dp[opponent_remains] is None:  # 相手が負ける場合
        for my_take in a:  # 自分が取る石の数
            my_remains = opponent_remains + my_take  # 相手が負けるようにできる、自分の手番の石の数
            dp[my_remains] = True

ans = dp[k]
print('First' if ans else 'Second')

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = tuple(map(int, input().split()))

dp = [None] * (k + 1)
# dp[手番の石の数] := 手番の勝敗
# True(勝ち) / None(負け)

for my_remains in range(k + 1):
    for my_take in a:
        opponent_remains = my_remains - my_take  # 相手が操作を行う石の数
        if opponent_remains >= 0 and dp[opponent_remains] is None:
            dp[my_remains] = True

ans = dp[k]
print('First' if ans else 'Second')

Submission status: Accepted

Solution code:
n, k = map(int, input().split( ))

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

dp = [0]*(k+1)

for i in range(k+1):
    win = 0
    for j in a:
        if i>=j and dp[i-j] == 0:
            win = 1
            break
    dp[i] = win
#print(*dp)            
if dp[k] == 1:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
# At DP K
def solve(K, A):
    dp = [ False ] * (K + 1)
    # dp[i] - true if current player wins if there are i stones remaining
    for stones in range(K + 1):
        for w in A:
            if stones >= w: # there must be more stones than we are removing
                if not dp[stones - w]: # does the opponent win after we remove `w` stones?
                    dp[stones] = True # then this player does win
    return "First" if dp[K] else "Second"

assert solve(7, [2, 3]) == "First"
assert solve(5, [2, 3]) == "Second"
assert solve(4, [2, 3]) == "First"
assert solve(20, [1, 2, 3]) == "Second"
assert solve(21, [1, 2, 3]) == "First"
assert solve(100000, [1]) == "Second"

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

ans = solve(k, A)
print(ans)

Submission status: Accepted

Solution code:
import sys
import unittest

class Solution(object):
	def __init__(self):
		self.n = 0
		self.k = 0
		self.a = []
		
	def readInput(self):
		a = sys.stdin.readline().split()
		self.n = int(a[0])
		self.k = int(a[1])
		a = sys.stdin.readline().split()
		for i in xrange(self.n):
			self.a.append(int(a[i]))
		
	def findWinner(self):
		dp = [False] * (self.k + 1)
		for i in xrange(self.k+1):
			for j in xrange(self.n):
				if i >= self.a[j] and not dp[i-self.a[j]]:
					dp[i] = True
		print "First" if dp[self.k] else "Second"
	
	
if __name__ == '__main__':
	s = Solution()
	s.readInput()
	s.findWinner()

Submission status: Accepted

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

firstWin = [None] * (K + 1)

firstWin[0] = False

for k in range(K + 1):
    for a in A:
        if k - a >= 0:
            if firstWin[k - a] == False:
                firstWin[k] = True
                break
    else:
        firstWin[k] = False

if firstWin[K]:
    print('First')
else:
    print('Second')

Submission status: Accepted

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

dp = [0]*(K+1)
for k in range(1,K+1) :
    for a in A :
        if k-a >= 0 and dp[k-a] == 0 :
            dp[k] = 1

print("First" if dp[K] else "Second")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
INF = float('inf')

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [0] * (K+1)
for i in range(K+1):
    for j in range(N):
        if a[j] <= i:
            dp[i] |= dp[i-a[j]] == 0
ans = 'First' if dp[K] else 'Second'
print(ans)

Submission status: Accepted

Solution code:
n,k = [int(j) for j in input().split()]
l = [int(j) for j in input().split()]
dp = {0:False}
for j in range(1,k+1):
    flag  =True
    for i in l:
        if j-i>-1:
            if not dp[j-i]:
                dp[j] = True
                flag =False
                break
    if flag:
        dp[j] = False
if dp[k]:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    canWin = [None] * (K + 1)
    canWin[0] = False

    for k in range(1, K + 1):
        for a in A:
            if k - a >= 0 and canWin[k - a] == False:
                canWin[k] = True
                break
        else:
            canWin[k] = False

    if canWin[K]:
        print('First')
    else:
        print('Second')

sol()

Submission status: Accepted

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

dp = [0 for _ in range(K+100)]

for i in range(K+1):
    flg = False
    for a in A:
        if i-a >= 0 and dp[i-a] == -1:
            flg = True
    if flg:
        dp[i] = 1
    else:
        dp[i] = -1

if dp[K] == 1:
    print('First')
else:
    print('Second')