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: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [False] * (K+1)
for i in range(1, K+1):
    for a in A:
        if i - a < 0: break
        dp[i] |= not dp[i-a]
print('First' if dp[K] else 'Second')

Submission status: Time Limit Exceeded

Solution code:
# K - Stones
def main():
    N, K, *A = map(int, open(0).read().split())
    dp = [0] * (K + 1)
    for i in range(K):
        for a in A:
            if i + a > K:
                break
            dp[i + a] |= dp[i] ^ 1
    print("First" if dp[-1] else "Second")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# K - Stones
def main():
    N, K, *A = map(int, open(0).read().split())
    dp = [0] * (K + 1)
    for i in range(1, K + 1):
        for a in A:
            if i - a >= 0:
                dp[i] |= dp[i - a] ^ 1
    print("First" if dp[-1] else "Second")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import resource
import sys
from functools import lru_cache
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.reverse()
sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(k, p):
  for a in A:
    if k >= a:
      if f(k-a, p ^ 1) == p:
        return p
  return p ^ 1

print('First' if f(K, 0) == 0 else 'Second')

Submission status: Time Limit Exceeded

Solution code:
import resource
import sys
from functools import lru_cache
N, K = map(int, input().split())
A = list(map(int, input().split()))

sys.setrecursionlimit(1000000)

@lru_cache(maxsize=None)
def f(k, p):
  w = set()
  for a in A:
    if k >= a:
      w.add(f(k-a, p ^ 1))
  if len(w) == 0:
    return p ^ 1
  elif None in w:
    return None
  elif p in w:
    return p
  else:
    return 1 ^ p


print('First' if f(K, 0) == 0 else 'Second')

Submission status: Time Limit Exceeded

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

dp = [-1]*(k+1)
dp[0] = 0

for i in range(1, k+1):
  temp = 1
  for j in range(n):
    if i - l[j] >= 0:
      temp *= dp[i-l[j]]
  dp[i] = 1-temp
      
if dp[k] == 0:
  print('Second')
else:
  print('First')

Submission status: Time Limit Exceeded

Solution code:
def solve(N, K, cards):
  min_elem = cards[0]

  TARO, JIRO = 0, 1
  dp = [[-1 for _ in range(K + 1)] for _ in range(2)]

  dp[TARO][0] = TARO
  dp[JIRO][0] = JIRO

  for i in range(min_elem):
    dp[JIRO][i] = TARO
    dp[TARO][i] = JIRO

  for k in range(1, K + 1):
    for turn in [TARO, JIRO]:
      opp = JIRO if turn == TARO else TARO
      dp[turn][k] = opp
      for c in cards:
        if c > k:
          break
        if k - c == 0:
          dp[turn][k] = turn
          break
        if k - c > 0 and dp[opp][k - c] == turn:
          dp[turn][k] = turn

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

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


N, K = iln()
cards = iln()
solve(N, K, cards)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

N, K = map(int, raw_input().split())
A = list(map(int, raw_input().split()))
memo = {}
def is_winner(i, k):
    if k == 0:
        return False

    if (i, k) in memo:
        return memo[i,k]
    ans = False
    for x in A:
        # print first, " Plays %s" % x
        if k >= x and not is_winner(1 if i==2 else 2, k - x):
            # print first, " winner for %s" % k
            ans = True
    memo[i, k] = ans
    return ans

print "First" if is_winner(1, K) else "Second"

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

def is_winner(k):
    if k == 0:
        return False

    ans = False
    for x in A:
        # print first, " Plays %s" % x
        if k >= x and not is_winner(k - x):
            # print first, " winner for %s" % k
            ans = True

    return ans

print "First" if is_winner(K) else "Second"

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5)

def rec(i, A, memo):
    if memo[i] != -1:
        return memo[i]

    for a in A:
        if i - a >= 0 and not rec(i - a, A, memo):
            memo[i] = True
            return True
    memo[i] = False
    return False


def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]
    memo = [-1] * (K + 1)
    print("First" if rec(K, A, memo) else "Second")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k, *a = map(int, open(0).read().split())
g = [0] * (k + 1)
for i in range(min(a), k + 1):
	s = set(g[i - x] for x in a if i >= x)
	r = 0
	while r in s:
		r += 1
	g[i] = r
print("First" if g[-1] else "Second")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    # 再帰関数を使うときは，その上限回数に注意
    # https://docs.python.org/ja/3/library/sys.html#sys.setrecursionlimit
    from sys import setrecursionlimit

    setrecursionlimit(5 * 10 ** 7)

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    memo = [[-1 for _ in range(3)] for _ in range(k + 1)]

    def rec(i, j):
        if memo[i][j] != -1:
            return memo[i][j]

        result = 0

        for ak in a:
            if ak <= i:
                if rec(i - ak, (j + 1) % 2) == 0:
                    result = 1
                    break

        memo[i][j] = result

        return memo[i][j]

    ans = rec(k, 0)

    if ans == 1:
        print('First')
    else:
        print('Second')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp=[False]*(k+1)

for i in range(1,len(dp)):
  for x in a:
    if i-x>=0:
      dp[i]|=not dp[i-x]

print(("Second","First")[dp[k]])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)
N, K = map(int, input().split())
a = tuple(map(int, input().split()))

def main():
    if dfs(K):
        print('First')
    else:
        print('Second')
@lru_cache(maxsize=None)
def dfs(n):
    if n < a[0]:
        return False
    for i in a:
        if not dfs(n-i):
            return True
    return False

main()

Submission status: Time Limit Exceeded

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

@lru_cache(maxsize=None)
def dp(k, A, turn):
    for i in A:
        if i > k:
            break
        if dp(k - i, A, not turn) == turn:
            return turn
    return not turn
    

def main():
    N, K = map(int, input().split())
    A = tuple(sorted(map(int, input().split())))
    print('First' if dp(K, A, True) else 'Second')


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [[0]*2 for i in range(k+1)]



dp[0][0] = 1
dp[0][1] = 0

for kLeft in range(1, k+1):
    for player in range(2):
        done = False
        for i in range(n):
            x = 1-player
            if (kLeft-a[i]>=0):
                x = dp[kLeft-a[i]][1-player]
            if (x==player):
                dp[kLeft][player] = player
                done=True
                break
        if done==False:
            dp[kLeft][player] = 1-player

def solve(kLeft, player):
    if (kLeft<0):
        return player

    if (kLeft==0):
        return 1-player

    if (dp[kLeft][player]!=-1):
        return dp[kLeft][player]

    for i in range(n):
        x = solve(kLeft-a[i], 1-player)
        if (x==player):
            dp[kLeft][player] = player
            return dp[kLeft][player]
    dp[kLeft][player] = 1-player
    return dp[kLeft][player]


z = solve(k, 0)
# z = dp[k][0]

if (z==0):
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

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

dp = [[0]*2 for i in range(k+1)]

dp[0][0] = 1
dp[0][1] = 0

for kLeft in range(1, k+1):
    for player in range(2):
        done = False
        for i in range(n):
            x = 1-player
            if (kLeft-a[i]>=0):
                x = dp[kLeft-a[i]][1-player]
            if (x==player):
                dp[kLeft][player] = player
                done=True
                break
        if done==False:
            dp[kLeft][player] = 1-player

def solve(kLeft, player):
    if (kLeft<0):
        return player

    if (kLeft==0):
        return 1-player

    if (dp[kLeft][player]!=-1):
        return dp[kLeft][player]

    for i in range(n):
        x = solve(kLeft-a[i], 1-player)
        if (x==player):
            dp[kLeft][player] = player
            return dp[kLeft][player]
    dp[kLeft][player] = 1-player
    return dp[kLeft][player]


# z = solve(k, 0)
z = dp[k][0]

if (z==0):
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()

# メモ[山の残数] = 今の手番がこの局面から勝てるか
memo = [None] * (K+1)

def dfs(k):
    # 既に見た局面ならメモの内容を返す
    if memo[k] is not None:
        return memo[k]
    for i in range(N):
        # 山の残数より多くは取れない
        if k-aN[i] < 0:
            break
        # 1つでも負けを押し付ける手があれば勝てる
        if not dfs(k-aN[i]):
            memo[k] = True
            return True
    # 負けを押し付ける手がなかったので自分が負ける
    memo[k] = False
    return False

if dfs(K):
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
n,k=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:dp[i]=max((i-j>=0)*(dp[i-j]==0),dp[i])
print(["Second","First"][dp[-1]])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int, input().split())
a=list(map(int, input().split()))
x=[1]
dp=[0]*(k+1)
#先手勝利1

for i in range(1,k+1):
    for j in range(n):
        if i>=a[j]:
            x.append(dp[i-a[j]])
    if min(x)==0:
        dp[i]=1
    else:
        dp[i]=0
    x=[1]
if dp[k]==1:
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
def solve():
    k, a = read()
    result = think(k, a)
    write(result)


def read():
    n, k = read_int(2)
    a = read_int(n)
    return k, a


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(k, a):
    max_n = 100
    max_k = 10 ** 5

    # dp[i] = True/False; True means First player win if num of stone is i
    dp = [False] * (max_n * max_k + 1)

    for i in range(len(dp)):
        for elem in a:
            if i >= elem:
                dp[i] |= not dp[i - elem]

    return dp[k]


def write(result):
    if result:
        print('First')
    else:
        print('Second')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
 
input = sys.stdin.readline
 
N, K = map(int, input().split())
a = [int(i) for i in input().split()]

dp = [True for j in range(K+1)]
dp[0] = False

for j in range(K):
    for i in range(N):
        if j+1 - a[i] >= 0:
            dp[j+1] = dp[j+1] and dp[j+1 - a[i]]
    dp[j+1] = not dp[j+1]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

dp = np.zeros(K+1)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

N,K = map(int, sys.stdin.readline().split())

A = list(map(int, sys.stdin.readline().split()))

dp = np.zeros(K+1)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

N,K = map(int, sys.stdin.readline().split())

A = list(map(int, sys.stdin.readline().split()))

dp = np.zeros(K+1)

for k in range(0,K+1):
    win = False
    for i in A:
        if win:
            break
        elif k-i >= 0 and dp[k-i] == 0:
            dp[k] = 1
            win = True
            
if win:
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

N,K = map(int, sys.stdin.readline().split())

A = list(map(int, sys.stdin.readline().split()))

dp = np.zeros(K+1)

for k in range(0,K+1):
    win = False
    for i in A:
        if k-i >= 0 and dp[k-i] == 0:
            dp[k] = 1
            win = True
            
if win:
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

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

def mex(L):
  L.sort()
  ans = 0
  for i in L:
    if i <= ans:
      ans += 1
    else:
      break
  return ans

DP = [0] * (K + 1)
M = 100000

for i in range(a[0], K + 1):
  L = []
  for j in range(N):
    if i - a[j] < 0:
      break
    L.append(DP[i - a[j]])
  DP[i] = mex(L)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
MOD = 1000000007
def POW(x, y): return pow(x, y, MOD)
def INV(x, m=MOD): return pow(x, m - 2, m)
def DIV(x, y, m=MOD): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,K=LI()
INL=LI()
DP=[False]*(K+1)

for i in range(0,K+1):
    for v in INL:
        if v+i <= K:
            DP[v+i] = DP[v+i] or not DP[i]

# print(DP)
print('First' if DP[K] else 'Second')

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
import threading
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

threading.stack_size(128*1024*1024)

N, K = LI()
A = LI()

dp = [-1]*(K+1)
for a in A:
    dp[a] = 1
for i in range(A[0]):
    dp[i] = 0

def rec(x):
    if (x<0):
        return 1
    if (dp[x]!=-1):
        return dp[x]
    res = 1
    for a in A:
        res &= rec(x-a)
    dp[x] = 1^res
    return dp[x]

print("First" if rec(K) else "Second")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
@lru_cache(maxsize=None)
def dp(x):
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

N, K = map(int, input().rstrip().split(' '))
A = np.array(list(map(int, input().rstrip().split(' '))))

dp = np.zeros(K + 1)

for i in range(K+1):
    dp[i] = np.sum(np.logical_not(dp[i - A[np.where(A <= i)]])) > 0

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

dp = [False] * (K + 1)

for i in range(K+1):
    for j in range(N):
        if i - A[j] >= 0:
            dp[i] = dp[i] or (not dp[i - A[j]])
    
if dp[K]:
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
# template


N, K = mi()
a = lmi()
a.insert(0, -12)
dp = [False] * (K + 1)

for i in range(1, K + 1):
    for j in range(1, N + 1):
        if i >= a[j] and not dp[i - a[j]]:
            dp[i] = True

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

Submission status: Time Limit Exceeded

Solution code:
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:
            dp[i] |= not dp[i - a[j]]

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

Submission status: Time Limit Exceeded

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

t = min(a)

dp = [0] * (k+1)

for x in a:
    dp[x] = 1

for i in range(k+1):
    for x in a:
        if i >= x:
            if dp[i] + (dp[i-x] + 1) % 2 > 0:
                dp[i] = 1
            else:
                dp[i] = 0

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,k=map(int,input().split())
t=np.int32(sorted(map(int,input().split())))
dp=np.ones((k+t.max()),dtype='int32')*-1
dp[:t[0]]=0
for i in range(k):
    dp[t+i]=np.maximum((dp[i]+1)%2,dp[t+i])
print(['Second','First'][dp[k]%2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
A = list(map(int, input().split()))

dp = [0] * (k+1)

for i in range(1, k+1):
    for a in A:
        if i - a < 0:
            break
        if dp[i-a] == 0:
            dp[i] = 1

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

Submission status: Time Limit Exceeded

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for j in range(n):
        if i - a[j] < 0:
            break
        if dp[i-a[j]] == 0:
            dp[i] = 1

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

Submission status: Time Limit Exceeded

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

dp = [0] * (k+1)

for i in range(1, k+1):
    for j in range(n):
        if i - a[j] >= 0 and dp[i-a[j]] == 0:
            dp[i] = 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
min_a = min(a)

memo = [-1] * (k+1)
def rec(x):
    if memo[x] >= 0:
        return memo[x]
    if x < min_a:
        memo[x] = 0
        return 0
    flag = 0
    for i in range(n):
        if x - a[i] < 0:
            continue
        if rec(x - a[i]) == 0:
            flag = 1
    if flag == 1:
        memo[x] = 1
        return 1
    else:
        memo[x] = 0
        return 0

if rec(k) == 1:
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

memo = [-1] * (k+1)
def rec(x):
    if memo[x] >= 0:
        return memo[x]
    flag = 0
    for i in range(n):
        if x - a[i] < 0:
            continue
        if rec(x - a[i]) == 0:
            flag = 1
    if flag == 1:
        memo[x] = 1
        return 1
    else:
        memo[x] = 0
        return 0

if rec(k) == 1:
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

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

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

memo = [-1] * (k+1)
def rec(x):
    if memo[x] >= 0:
        return memo[x]
    flag = 0
    for i in range(n):
        if x - a[i] < 0:
            continue
        if rec(x - a[i]) == 0:
            flag = 1
    if flag == 1:
        memo[x] = 1
        return 1
    else:
        memo[x] = 0
        return 0

if rec(k) == 1:
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

"""
参考：https://kyopro-friends.hatenablog.com/entry/2019/01/12/231000
・メモ化再帰
・手番はメモしなくていい
・負け状態を押し付けられるかどうか
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()

# メモ[山の残数] = 今の手番がこの局面から勝てるか
memo = [None] * (K+1)

def dfs(k):
    # 既に見た局面ならメモの内容を返す
    if memo[k] != None:
        return memo[k]
    for i in range(N):
        # 山の残数より多くは取れない
        if k-aN[i] < 0:
            break
        # 1つでも負けを押し付ける手があれば勝てる
        if not dfs(k-aN[i]):
            memo[k] = True
            return True
    # 負けを押し付ける手がなかったので自分が負ける
    memo[k] = False
    return False

if dfs(K):
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()

# メモ[手番]][山の残数] = この局面から勝てるか
memo = [[None] * (K+1) for i in range(2)]

def dfs(turn, k):
    # 山がもう足りないので決着
    if k < 0:
        if turn == 0:
            return True
        else:
            return False
    # 先手番
    if turn == 0:
        # 既に見た局面ならメモの内容を返す
        if memo[turn][k] != None:
            return memo[turn][k]
        mx = -1
        for i in range(N):
            mx = max(mx, dfs(turn+1, k-aN[i]))
            # この先はやっても同じ
            if k-aN[i] < 0:
                break
        # ここより深い所を探し終わったので結果をメモする
        memo[turn][k] = mx
        return mx
    # 後手番
    else:
        if memo[turn][k] != None:
            return memo[turn][k]
        mn = float('inf')
        for i in range(N):
            mn = min(mn, dfs(turn-1, k-aN[i]))
            if k-aN[i] < 0:
                break
        memo[turn][k] = mn
        return mn

if dfs(0, K):
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = sorted(LIST())

# メモ[手番]][山の残数] = この局面から勝てるか
memo = [[None] * (K+1) for i in range(2)]

def dfs(turn, k):
    # 山がもう足りないので決着
    if k < 0:
        if turn == 0:
            return True
        else:
            return False
    # 先手番
    if turn == 0:
        # 既に見た局面ならメモの内容を返す
        if memo[turn][k] != None:
            return memo[turn][k]
        mx = -1
        for i in range(N):
            mx = max(mx, dfs(turn+1, k-aN[i]))
        # ここより深い所を探し終わったので結果をメモする
        memo[turn][k] = mx
        return mx
    # 後手番
    else:
        if memo[turn][k] != None:
            return memo[turn][k]
        mn = float('inf')
        for i in range(N):
            mn = min(mn, dfs(turn-1, k-aN[i]))
        memo[turn][k] = mn
        return mn

if dfs(0, K):   
    print('First')
else:
    print('Second')

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans = [False]*(k+1)
for i in range(1,k+1):
    ok = False
    for j in a:
        if i-j<0:
            continue
        if ans[i-j] == False:
            ans[i] = True

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