Problem:


Score : 500 points

Problem Statement

A robot is put at the origin in a two-dimensional plane.
Initially, the robot is facing in the positive x-axis direction.

This robot will be given an instruction sequence s.
s consists of the following two kinds of letters, and will be executed in order from front to back.

F : Move in the current direction by distance 1.

T : Turn 90 degrees, either clockwise or counterclockwise.

The objective of the robot is to be at coordinates (x, y) after all the instructions are executed.
Determine whether this objective is achievable.

Constraints

s consists of F and T.

1 \leq |s| \leq 8 000

x and y are integers.

|x|, |y| \leq |s|

Input

Input is given from Standard Input in the following format:

s
x y

Output

If the objective is achievable, print Yes; if it is not, print No.

Sample Input 1

FTFFTFFF
4 2

Sample Output 1

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning clockwise in the second T.

Sample Input 2

FTFFTFFF
-2 -2

Sample Output 2

Yes

The objective can be achieved by, for example, turning clockwise in the first T and turning clockwise in the second T.

Sample Input 3

FF
1 0

Sample Output 3

No

Sample Input 4

TF
1 0

Sample Output 4

No

Sample Input 5

FFTTFF
0 0

Sample Output 5

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning counterclockwise in the second T.

Sample Input 6

TTTT
1 0

Sample Output 6

No



Sample input:
FTFFTFFF
4 2


Sample output:
Yes

Submission status: Time Limit Exceeded

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

from collections import defaultdict, deque

S = input()
X, Y = map(int, input().split())
# [x][y][現在の移動距離][現在の向き]をメモする
memo = defaultdict(lambda :defaultdict(lambda :defaultdict(lambda :defaultdict(int))))
len_F = S.count('F')
# ゴールまでの距離と進む予定の距離の偶奇が違えば論外
if (X + Y) % 2 != len_F % 2:
    print('No')
    exit()

def bfs():
    que = deque()
    que.append([0,0,0,'r',len_F])
    while len(que) != 0:
        x, y, cur, dirc, rest = que.popleft()
        # 訪問済
        if memo[x][y][cur][dirc] == 1:
            continue
        memo[x][y][cur][dirc] = 1
        # もうゴールに届かない場合
        if rest < abs(X-x) + abs(Y-y):
            continue
        # 最後までいった時
        if cur == len(S):
            if x == X and y == Y:
                break
            else:
                continue
        # まっすぐ
        if S[cur] == 'F':
            if dirc == 'r': x += 1
            elif dirc == 'l': x -= 1
            elif dirc == 'u': y += 1
            elif dirc == 'd': y -= 1
            que.append([x,y,cur+1,dirc,rest-1])
        # 曲がる
        elif S[cur] == 'T':
            if dirc == 'r' or dirc == 'l':
                que.append([x,y,cur+1,'u',rest])
                que.append([x,y,cur+1,'d',rest])
            elif dirc == 'u' or dirc == 'd': 
                que.append([x,y,cur+1,'r',rest])
                que.append([x,y,cur+1,'l',rest])

bfs()
if any(memo[X][Y][len(S)]):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

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

from collections import defaultdict, deque

S = input()
X, Y = map(int, input().split())
# [x][y][現在の移動距離][現在の向き]をメモする
memo = defaultdict(lambda :defaultdict(lambda :defaultdict(lambda :defaultdict(int))))
len_F = S.count('F')
# ゴールまでの距離と進む予定の距離の偶奇が違えば論外
if (X + Y) % 2 != len_F % 2:
    print('No')
    exit()

def bfs():
    que = deque()
    que.append([0,0,0,'r',len_F])
    while len(que) != 0:
        x, y, cur, dirc, rest = que.popleft()
        # 訪問済
        if memo[x][y][cur][dirc] == 1:
            continue
        memo[x][y][cur][dirc] = 1
        # もうゴールに届かない場合
        if rest < abs(X-x) + abs(Y-y):
            continue
        # 最後までいった時
        if cur == len(S):
            continue
        # まっすぐ
        if S[cur] == 'F':
            if dirc == 'r': x += 1
            elif dirc == 'l': x -= 1
            elif dirc == 'u': y += 1
            elif dirc == 'd': y -= 1
            que.append([x,y,cur+1,dirc,rest-1])
        # 曲がる
        elif S[cur] == 'T':
            if dirc == 'r' or dirc == 'l':
                que.append([x,y,cur+1,'u',rest])
                que.append([x,y,cur+1,'d',rest])
            elif dirc == 'u' or dirc == 'd': 
                que.append([x,y,cur+1,'r',rest])
                que.append([x,y,cur+1,'l',rest])

bfs()
if any(memo[X][Y][len(S)]):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = list(input())

a = []
k = 0
for z in s:
  if z == "T":
    a += [k]
    k = 0
  else:
    k += 1
a += [k]
# print(a)

l = [a[0]]
for k in a[2::2]:
  l = [t+k for t in l] + [t-k for t in l]

m = [0]
for k in a[1::2]:
  m = [t+k for t in m] + [t-k for t in m]

x,y = map(int,input().split())
print("Yes" if x in l and y in m else "No")

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
for k in range(2):
    tt = t[k]
    z = [x, y]
    if k == 0:
        p = [tt[0]]
    else:
        p = [tt[0], -tt[0]]
    for i in range(1, len(tt)):
        pp = []
        for j in range(len(p)):
            pp.append(p[j] + tt[i])
            pp.append(p[j] - tt[i])
        p = pp
    if z[k] in p:
        flag[k] = True
if flag[0] and flag[1]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
count = 0
d = []
s = s.split('T')
d = [len(x) for x in s]

if len(d) == 0:
    d.append(0)
if len(d) == 1:
    d.append(0)
dpx = [d[0]]
dpy = [d[1],-d[1]]
for i in range(len(d)-2):
    if i%2==0:
        trans = set()
        for xj in dpx:
            trans.add(xj+d[i+2])
            trans.add(xj-d[i+2])
        dpx = list(trans)
    else:
        trans = set()
        for yj in dpy:
            trans.add(yj+d[i+2])
            trans.add(yj-d[i+2])
        dpy = list(trans)
ans = (x in dpx)&(y in dpy)

if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
count = 0
d = []
s = s.split('T')
d = [len(x) for x in s]

if len(d) == 0:
    d.append(0)
if len(d) == 1:
    d.append(0)
dpx = [d[0]]
dpy = [d[1],-d[1]]
for i in range(len(d)-2):
    if i%2==0:
        trans = set()
        for j in range(len(dpx)):
            trans.add(dpx[j]+d[i+2])
            trans.add(dpx[j]-d[i+2])
        dpx = list(trans)
    else:
        trans = set()
        for j in range(len(dpy)):
            trans.add(dpy[j]+d[i+2])
            trans.add(dpy[j]-d[i+2])
        dpy = list(trans)
ans = (x in dpx)&(y in dpy)

if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
count = 0
d = []
for i in range(len(s)):
    if s[i] == 'F':
        count += 1
    else:
        d.append(count)
        count = 0
if count != 0:
    d.append(count)

dx = [d[i] for i in range(len(d)) if i%2==0]
dy = [d[i] for i in range(len(d)) if i%2==1]
if len(dx) == 0:
    dx = [0]
if len(dy) == 0:
    dy = [0]
dpx = [dx[0]]
dpy = [dy[0],-dy[0]]
for i in range(len(dx)-1):
    trans = set()
    for j in range(len(dpx)):
        trans.add(dpx[j]+dx[i+1])
        trans.add(dpx[j]-dx[i+1])
    dpx = list(trans)
for i in range(len(dy)-1):
    trans = set()
    for j in range(len(dpy)):
        trans.add(dpy[j]+dy[i+1])
        trans.add(dpy[j]-dy[i+1])
    dpy = list(trans)
ans = (x in dpx)&(y in dpy)

if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
count = 0
d = []
for i in range(len(s)):
    if s[i] == 'F':
        count += 1
    else:
        d.append(count)
        count = 0
if count != 0:
    d.append(count)

dx = [d[i] for i in range(len(d)) if i%2==0]
dy = [d[i] for i in range(len(d)) if i%2==1]
if len(dx) == 0:
    dx = [0]
if len(dy) == 0:
    dy = [0]
dpx = [[],[]]
dpx[1] = [dx[0]]
dpy = [[],[]]
dpy[1] = [dy[0],-dy[0]]
for i in range(len(dx)-1):
    trans = set()
    for j in range(len(dpx[1])):
        trans.add(dpx[1][j]+dx[i+1])
        trans.add(dpx[1][j]-dx[i+1])
    dpx[0] = dpx[1]
    dpx[1] = list(trans)
for i in range(len(dy)-1):
    trans = set()
    for j in range(len(dpy[1])):
        trans.add(dpy[1][j]+dy[i+1])
        trans.add(dpy[1][j]-dy[i+1])
    dpy[0] = dpy[1]
    dpy[1] = list(trans)
ans = (x in dpx[-1])&(y in dpy[-1])

if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x,y = map(int,input().split())
count = 0
d = []
for i in range(len(s)):
    if s[i] == 'F':
        count += 1
    else:
        d.append(count)
        count = 0
if count != 0:
    d.append(count)

dx = [d[i] for i in range(len(d)) if i%2==0]
dy = [d[i] for i in range(len(d)) if i%2==1]
if len(dx) == 0:
    dx = [0]
if len(dy) == 0:
    dy = [0]
dpx = [[] for i in range(len(dx))]
dpx[0] = [dx[0]]
dpy = [[] for i in range(len(dy))]
dpy[0] = [dy[0],-dy[0]]
for i in range(len(dx)-1):
    trans = set()
    for j in range(len(dpx[i])):
        trans.add(dpx[i][j]+dx[i+1])
        trans.add(dpx[i][j]-dx[i+1])
    dpx[i+1] = list(trans)
for i in range(len(dy)-1):
    trans = set()
    for j in range(len(dpy[i])):
        trans.add(dpy[i][j]+dy[i+1])
        trans.add(dpy[i][j]-dy[i+1])
    dpy[i+1] = list(trans)
ans = (x in dpx[-1])&(y in dpy[-1])

if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

s = input()
x,y = map(int,input().split())
count = 0
d = []
for i in range(len(s)):
    if s[i] == 'F':
        count += 1
    else:
        d.append(count)
        count = 0
if count != 0:
    d.append(count)

dx = [d[i] for i in range(len(d)) if i%2==0]
dy = [d[i] for i in range(len(d)) if i%2==1]

if len(dx) == 0:
    dx = [0]
if len(dy) == 0:
    dy = [0]

def dpx(n,x):
    if n == 1:
        return x == dx[0]
    else:
        return dpx(n-1,x+dx[n-1]) or dpx(n-1,x-dx[n-1])

def dpy(n,y):
    if n == 1:
        return y == dy[0] or y == -dy[0]
    else:
        return dpy(n-1,y+dy[n-1]) or dpy(n-1,y-dy[n-1])

ans = dpx(len(dx),x)&dpy(len(dy),y)
if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
s = input()
x,y = map(int,input().split())
count = s.count('F')
ans = abs(x)+abs(y) <= count
def bfs(x,y,s,count):
    if count < abs(x)+abs(y):
        return False
    elif x==0 and y==0 and s == '':
        return True
    else:
        if s[0] == 'F':
            x -= 1
            s = s[1:]
            count -= 1
            return bfs(x,y,s,count)
        else:
            s = s[1:]
            return bfs(y,-x,s,count) or bfs(-y,x,s,count)
ans = bfs(x,y,s,count)
if ans:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = map(int, input().split())

x_list = []
y_list = []

st = s.split("T")
x -= len(st[0])

for i, ls in enumerate(st[1:]):
    if i % 2:
        x_list.append(len(ls))
    else:
        y_list.append(len(ls))

dpx = [[0 for i in range(16001)] for j in range(len(x_list)+1)]
dpy = [[0 for i in range(16001)] for j in range(len(y_list)+1)]

dpx[0][8000] = 1
dpy[0][8000] = 1

for i in range(len(x_list)):
    for num in range(16001):
        if num + x_list[i] <= 16000 and dpx[i][num] == 1:
            dpx[i+1][num+x_list[i]] = 1
        if num - x_list[i] >= 0 and dpx[i][num] == 1:
            dpx[i+1][num-x_list[i]] = 1

for i in range(len(y_list)):
    for num in range(16001):
        if num + y_list[i] <= 16000 and dpy[i][num] == 1:
            dpy[i+1][num+y_list[i]] = 1
        if num - y_list[i] >= 0 and dpy[i][num] == 1:
            dpy[i+1][num-y_list[i]] = 1

if dpx[len(x_list)][x+8000] == 1 and dpy[len(y_list)][y+8000] == 1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
def search(keys,dic,now,sum_):
    if sum_ < 0:
        return -1
    elif now==len(keys):
        if sum_==0:
            return True
        else:
            return 0
    k=keys[now]
    for i in range(dic[k]+1):
        res=search(keys,dic,now+1,sum_-2*i*k)
        if res == 0:
            continue
        elif res==-1:
            break
        else:
            return True
            
    return 0

s=input()+'T'
x,y=list(map(int,input().split()))
xlist=[0 for _ in range(8000)]
ylist=[0 for _ in range(8000)]
flag='x+'
ini=0
tmp=0
xsum=0
ysum=0
for c in s:
    if c =='F':
        tmp+=1
    else:
        if flag=='x':
            xlist[tmp]+=1
            xsum+=tmp
        elif flag=='y':
            ylist[tmp]+=1
            ysum+=tmp
        else:
            ini=tmp
        tmp=0
        if flag=='y':
            flag='x'
        else:
            flag='y'
xlist[0]=0
ylist[0]=0
xkey=[]
ykey=[]
for i in range(8000):
    if xlist[i]>0:
        xkey.append(i)
    if ylist[i]>0:
        ykey.append(i)
xkey.reverse()
ykey.reverse()

if search(xkey,xlist,0,xsum-x+ini)==1 and search(ykey,ylist,0,ysum-y)==1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
S = input()
x, y = map(int, input().split())

a = []
t = 0
for s in S:
    if s == "F":
        t += 1
    else:
        a.append(t)
        t = 0
a.append(t)

if a == []:
    if x == y == 0:
        print("Yes")
        exit(0)
    else:
        print("No")
        exit(0)

d = [[a[0],0]]
for k in range(1,len(a)):
    n = []
    if k%2 == 1:
        for e in d:
            n.append([e[0],e[1]+a[k]])
            n.append([e[0],e[1]-a[k]])
    else:
        for e in d:
            n.append([e[0]+a[k],e[1]])
            n.append([e[0]-a[k],e[1]])
    d = n

print("Yes" if [x,y] in d else "No")

Submission status: Time Limit Exceeded

Solution code:
def search(keys,dic,now,goal):
    if len(keys)==now:
        if goal==0:
            return True
        else:
            return False
    k=keys[now]
    for i in range(dic[k]+1):
        if search(keys,dic,now+1,goal-k*i+k*(dic[k]-i)):
            return True
    return False

s=input()+'T'
x,y=list(map(int,input().split()))
xdic={}
ydic={}

flag='x+'
ini=0
tmp=0
for c in s:
    if c =='F':
        tmp+=1
    else:
        if flag=='x':
            if xdic.get(tmp,0)==0:
                xdic[tmp]=1
            else:
                xdic[tmp]+=1
        elif flag=='y':
            if ydic.get(tmp,0)==0:
                ydic[tmp]=1
            else:
                ydic[tmp]+=1
        else:
            ini=tmp
        tmp=0
        if flag=='y':
            flag='x'
        else:
            flag='y'
if xdic.get(0,0)!=0:
    xdic.pop(0)
if ydic.get(0,0)!=0:
    ydic.pop(0)
if search(list(xdic.keys()),xdic,0,x-ini) and search(list(ydic.keys()),ydic,0,y):
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s=input().split("T")
x,y=map(int,input().split())
A=[]
B=[]
for i,j in enumerate(s):
    if i%2==0:
        A.append(len(j))
    else:
        B.append(len(j))
T=max([sum(A),sum(B),abs(x),abs(y)])
X=len(A)
Y=len(B)
if abs(x)+abs(y)>sum(A)+sum(B):
    print("No")
    exit()
dpx=[[False for i in range(2*T+1)] for _ in range(X+1)]
dpy=[[False for i in range(2*T+1)] for _ in range(Y+1)]
dpx[0][T]=True
dpy[0][T]=True
for l in range(X):
    for i in range(2*T+1):
        if dpx[l][i]:
            dpx[l+1][i+A[l]]=True
            if l==0:
                continue
            dpx[l+1][i-A[l]]=True
for r in range(Y):
    for i in range(2*T+1):
        if dpy[r][i]:
            dpy[r+1][i-B[r]]=True
            dpy[r+1][i+B[r]]=True
if dpx[X][x+T] and dpy[Y][y+T]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s = input()
x, y = map(int, input().split())

d = [len(x) for x in s.split('T')]

dx = d[0::2]
dp = [defaultdict(bool) for _ in range(len(dx) + 1)]
dp[0][0] = True
max_x = sum(dx)
for i in range(len(dx)):
    for j in range(-max_x, max_x + 1):
        if i == 0:
            dp[i + 1][j] = dp[i][j - dx[i]]
        else:
            dp[i + 1][j] = dp[i][j - dx[i]] or dp[i][j + dx[i]]
x_flag = dp[-1][x]

dy = d[1::2]
dp = [defaultdict(bool) for _ in range(len(dy) + 1)]
dp[0][0] = True
max_y = sum(dy)
for i in range(len(dy)):
    for j in range(-max_y, max_y + 1):
        dp[i + 1][j] = dp[i][j - dy[i]] or dp[i][j + dy[i]]
y_flag = dp[-1][y]

if x_flag and y_flag:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

s = input()
x, y = map(int, input().split())

d = [len(x) for x in s.split('T')]

dx = d[0::2]
dpx = [defaultdict(bool) for _ in range(len(dx) + 1)]
dpx[0][0] = True
max_x = sum(dx)
for i in range(len(dx)):
    for j in range(-max_x, max_x + 1):
        if i == 0:
            dpx[i + 1][j] = dpx[i][j - dx[i]]
        else:
            dpx[i + 1][j] = dpx[i][j - dx[i]] or dpx[i][j + dx[i]]

dy = d[1::2]
dpy = [defaultdict(bool) for _ in range(len(dy) + 1)]
dpy[0][0] = True
max_y = sum(dy)
for i in range(len(dy)):
    for j in range(-max_y, max_y + 1):
        dpy[i + 1][j] = dpy[i][j - dy[i]] or dpy[i][j + dy[i]]

if dpx[-1][x] and dpy[-1][y]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = [len(i) for i in input().split("T")]
x,y  = (int(i) for i in input().split())
xl,yl,flag = [],[],False
for i in range(len(s)):
	if i%2==0: xl.append(s[i])
	else: yl.append(s[i])
x,y,xl = abs(x-xl[0]),abs(y),xl[1:]
xs,ys,lenx,leny,xl2,yl2 = sum(xl),sum(yl),len(xl),len(yl),[0],[0]
a,b = [[0 for i in range(xs+1)] for i in range(len(xl)+1)],[[0 for i in range(ys+1)] for i in range(len(yl)+1)]
a[0][0],b[0][0] = 1,1
if xs>=x and (xs-x)%2==0 and ys>=y and (ys-y)%2==0: x2,y2,flag = (xs-x)//2,(ys-y)//2,True
else: print("No")
if flag:
	for i in range(lenx): xl2.append(xl2[-1]+xl[i])
	for i in range(leny): yl2.append(yl2[-1]+yl[i])
	for i in range(lenx):
		for j in range(xl2[i+1]+1):
			if xl[i]<=j: a[i+1][j] = a[i][j-xl[i]] | a[i][j]
			else: a[i+1][j] = a[i][j]
	for i in range(leny):
		for j in range(yl2[i+1]+1):
			if yl[i]<=j: b[i+1][j] = b[i][j-yl[i]] | b[i][j]
			else: b[i+1][j] = b[i][j]
	if a[-1][x2] and b[-1][y2]: print("Yes")
	else: print("No")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


move = None
tx = None
ty = None


@lru_cache(maxsize=None)
def fx(cx, i):
    if i >= len(move):
        return cx == tx

    m = move[i]
    if fx(cx+m, i+2) or fx(cx-m, i+2):
        return True
    else:
        return False


@lru_cache(maxsize=None)
def fy(cy, i):
    if i >= len(move):
        return cy == ty

    m = move[i]
    if fy(cy+m, i+2) or fy(cy-m, i+2):
        return True
    else:
        return False


@mt
def slv(S, x, y):
    global move
    global tx
    global ty
    tx = x
    ty = y
    move = list(map(lambda x: len(x), S.split('T')))

    return 'Yes' if fx(move[0], 2) and fy(0, 1) else 'No'


def main():
    S = read_str().strip()
    x, y = read_int_n()
    print(slv(S, x, y))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from copy import deepcopy
S = list(input())
x, y = map( int, input().split())
UD = [] #updown
LR = [0] #leftright
X = deepcopy(LR)
t = 0
for w in S:
    if w == 'F':
        X[-1] += 1
    elif t == 0:
        LR = deepcopy(X)
        X = deepcopy(UD)
        X.append(0)
        t = 1
    else:
        UD = deepcopy(X)
        X = deepcopy(LR)
        X.append(0)
        t = 0
if t == 0:
    LR = deepcopy(X)
else:
    UD = deepcopy(X)
x = x - LR.pop(0)
G = 0
H = 0
dpx = [0]
k = 0
while k <= len(LR)-1:
    dpx_kari = deepcopy(dpx)
    dpx = []
    for m in dpx_kari:
        dpx.append(m + LR[k])
        dpx.append(m - LR[k])
    k += 1
k = 0
dpy = [0]
while k <= len(UD)-1:
    dpy_kari = deepcopy(dpy)
    dpy = []
    for m in dpy_kari:
        dpy.append(m + UD[k])
        dpy.append(m - UD[k])
    k += 1

if x in dpx and y in dpy:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
from copy import deepcopy
S = list(input())
x, y = map( int, input().split())
UD = [] #updown
LR = [0] #leftright
X = deepcopy(LR)
t = 0
for w in S:
    if w == 'F':
        X[-1] += 1
    elif t == 0:
        LR = deepcopy(X)
        X = deepcopy(UD)
        X.append(0)
        t = 1
    else:
        UD = deepcopy(X)
        X = deepcopy(LR)
        X.append(0)
        t = 0
if t == 0:
    LR = deepcopy(X)
else:
    UD = deepcopy(X)
x = x - LR.pop(0)
G = 0
H = 0
LLR = len(LR)
LUD = len(UD)
for B in product([-1,1], repeat = LLR):
    Z = 0
    for i in range(LLR):
        Z += LR[i]*B[i]
    if Z == x:
        G = 1

for B in product([-1,1],repeat = LUD):
    Z = 0
    for i in range(LUD):
        Z += UD[i]*B[i]
    if Z == y:
        H = 1
print('Yes' if G == 1 and H == 1 else 'No')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

S = input()
X, Y = map(int, input().split())

N = len(S)

d = [len(i) for i in S.split('T')]
d_x = d[0::2]
d_y = d[1::2]

dp_x = defaultdict(lambda: defaultdict(lambda: False))
dp_x[1][d_x[0]] = True
for i in range(1, len(d_x)):
    for x in range(-N, N):
        dp_x[i + 1][x] = dp_x[i][x - d_x[i]] or dp_x[i][x + d_x[i]]

dp_y = defaultdict(lambda: defaultdict(lambda: False))
dp_y[0][0] = True
for i in range(len(d_y)):
    for y in range(-N, N):
        dp_y[i + 1][y] = dp_y[i][y - d_y[i]] or dp_y[i][y + d_y[i]]

if dp_x[len(d_x)][X] and dp_y[len(d_y)][Y]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
s_x = sl[::2]
s_y = sl[1::2]
s_y=[0]+s_y
dpx=[[] for i in s_x]
dpy=[[] for i in s_y]
dpx[0].append(s_x[0])
dpy[0].append(0)
for i,l in enumerate(s_x):
    if i==0:continue
    ll=dpx[i]
    for xx in dpx[i-1]:
        ll.append(xx-l)
        ll.append(xx+l)
for i,l in enumerate(s_y):
    if i==0:continue
    ll=dpy[i]
    for yy in dpy[i-1]:
        ll.append(yy-l)
        ll.append(yy+l)
print('Yes' if x in dpx[-1] and y in dpy[-1] else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0

s_x = sl[::2]
s_y = sl[1::2]

answersx={}
answersy={}
def search(pos, kk,tgt, sl, answers):
    if kk== len(sl):
        ans=pos == tgt
        answers[pos,kk] = ans
    else:
        lng=sl[kk]
        minus=search(pos-lng,kk+1,tgt,sl,answers)
        plus=search(pos+lng,kk+1,tgt,sl,answers)
        ans = minus or plus
    answers[pos,kk] = ans
    return ans


print('Yes' if search(x0,1,x,s_x,answersx) and search(y0,0,y,s_y,answersy) else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
sums=[sum(sl[k:]) for k in range(len(sl))]
answers={}
def search(xx,yy,k,isUD):
    if (xx,yy,k) in answers:
        return answers[(xx,yy,k)]
    if k == len(sl):
        ans=(xx,yy)==(x,y)
    else:
        if abs(xx-x)+abs(yy-y) > sums[k]:
            ans=False
        else:
            lng=sl[k]
            # D or L
            llr=(lng if not isUD else 0)
            lud=(lng if isUD else 0)
            d_l = search(xx-llr,yy-lud,k+1, not isUD)
            u_r = search(xx+llr,yy+lud,k+1, not isUD)
            ans = d_l or u_r
    answers[(xx,yy,k)]=ans
    return ans
print('Yes' if search(x0,y0,1,True) else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0

answers={}
def search(xx,yy,k,isUD):
    if (xx,yy,k) in answers:
        return answers[(xx,yy,k)]
    if k == len(sl):
        ans=(xx,yy)==(x,y)
    else:
        if abs(xx-x)+abs(yy-y) > sum(sl[k:]):
            ans=False
        else:
            lng=sl[k]
            # D or L
            llr=(lng if not isUD else 0)
            lud=(lng if isUD else 0)
            d_l = search(xx-llr,yy-lud,k+1, not isUD)
            u_r = search(xx+llr,yy+lud,k+1, not isUD)
            ans = d_l or u_r
    answers[(xx,yy,k)]=ans
    return ans
print('Yes' if search(x0,y0,1,True) else 'No')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0

answers={}
def search(xx,yy,k,isUD):
    if (xx,yy,k) in answers:
        return answers[(xx,yy,k)]
    if k == len(sl):
        ans=(xx,yy)==(x,y)
    else:
        lng=sl[k]
        # D or L
        llr=(lng if not isUD else 0)
        lud=(lng if isUD else 0)
        d_l = search(xx-llr,yy-lud,k+1, not isUD)
        u_r = search(xx+llr,yy+lud,k+1, not isUD)
        ans = d_l or u_r
    answers[(xx,yy,k)]=ans
    return ans
print('Yes' if search(x0,y0,1,True) else 'No')

Submission status: Time Limit Exceeded

Solution code:
s = list(map(len, input().split("T")))
*x, = map(int,input().split())
x[0] -= s[0]
s = s[1:]

ans = True
for j in range(2):
    dp = [False]*(8000*2+1)
    dp[8000] = True
    MAX, MIN = 8000, 8000
    for i in range(j, len(s), 2):
        dp_new = [False]*(8000*2+1)
        MIN_ = 8000*2+1
        MAX_ = -1
        for k in range(MIN, MAX+1):
            if dp[k]:
                dp_new[k-s[i]] = True
                MIN_ = min(MIN_, k-s[i])
                dp_new[k+s[i]] = True
                MAX_ = max(MAX_, k+s[i])
        dp = dp_new
        MIN, MAX = MIN_, MAX_
    ans = ans and dp[x[1-j]+8000]
print(["No","Yes"][ans])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
s = input()
x, y = map(int, input().split(' '))

current = [0, 0, 0, 0] # next command, x, y, direction(x軸座標性から反時計回りに0,1,2,3)
q = deque([])
q.append(current)
flag = 0
while len(q) > 0:
    tmp = q.popleft()
    if tmp[0] >= len(s):
        if tmp[1] == x and tmp[2] == y:
            flag = 1
            break
        continue
    if s[tmp[0]] == 'F':
        tmp[0] += 1
        if tmp[3] == 0:
            tmp[1] += 1
            q.append(tmp)
        elif tmp[3] == 1:
            tmp[2] += 1
            q.append(tmp)
        elif tmp[3] == 2:
            tmp[1] -= 1
            q.append(tmp)
        else:
            tmp[2] -= 1
            q.append(tmp)
    else:
        tmp[0] += 1
        q.append([tmp[0], tmp[1], tmp[2], (tmp[3] + 1) % 4])
        q.append([tmp[0], tmp[1], tmp[2], (tmp[3] - 1) % 4])

if flag == 1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
s = list(input())
target = np.array([int(i) for i in input().split()])
# 右 : 0 下 : 1 左 : 2 上 :3
direction = np.array([[1, 0], [0, -1], [-1, 0], [0, 1]])


queue = [[np.array([0, 0]), 0, s]]
flag = False

while queue:
    state, now_d, s = queue.pop(0)

    if len(s) == 0:
        if np.allclose(target, state):
            flag = True
            break
        else:
            continue

    operation = s[0]

    if operation == "F":
        next_state = state + direction[now_d]
        queue.append([next_state, now_d, s[1:]])
    elif operation == "T":
        queue.append([state, (now_d+1) % 4, s[1:]])
        queue.append([state, (now_d-1) % 4, s[1:]])

if flag:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

dp_x = [[False] * (N*2) for i in range(N)]
dp_y = [[False] * (N*2) for i in range(N)]

if X_command:
    dp_x[0][X_command[0]] = True
    for i in range(1, len(X_command)):
        for xi in range(N):
            if xi + X_command[i] >= N:
                continue
            if xi-X_command[i] >= 0:
                dp_x[i][xi] = dp_x[i-1][xi-X_command[i]] or dp_x[i-1][xi+X_command[i]]
            else:
                dp_x[i][xi] = dp_x[i-1][xi+X_command[i]]

if Y_command:
    dp_y[0][Y_command[0]] = True
    for i in range(1, len(Y_command)):
        for yi in range(N):
            if yi + Y_command[i] >= N:
                continue
            if yi-Y_command[i] >= 0:
                dp_y[i][yi] = dp_y[i-1][yi-Y_command[i]] or dp_y[i-1][yi+Y_command[i]]
            else:
                dp_y[i][yi] = dp_y[i-1][yi+Y_command[i]]


x, y = max(x, -x), max(y, -y)

if dp_x[len(X_command)-1][x] and dp_y[len(Y_command)-1][y]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def main():
   s = input()
   x,y = map(int, input().split())

   Fcount = 0
   ff = 0
   Tcount = 0
   S = []
   for ss in s:
      if ss == "F":
         if (Tcount%2==0)and(Tcount!=0):
            S.append("t")
         elif Tcount!=0:
            S.append("T")
         Fcount += 1
         ff += 1
         Tcount = 0
      elif ss=="T":
         if ff!=0:
            S.append(str(ff))
         Tcount += 1
         ff = 0
   if ff!=0:
      S.append(str(ff))
   if Fcount < (abs(x)+abs(y)):
      return "No"

   # BFS
   k = len(S)
   q = deque([[0,0,1,0,0]])
   while q!=deque([]):
      xx,yy,vx,vy,now = q.pop()
      if (xx==x)and(yy==y)and(now==k):
         return "Yes"
      elif now==k:
         continue
      else: #now != k
         if S[now] == "T":
            if vx == 0:
               q.append([xx,yy,1,0,now+1])
               q.append([xx,yy,-1,0,now+1])
            elif vy == 0:
               q.append([xx,yy,0,1,now+1])
               q.append([xx,yy,0,-1,now+1])
         elif S[now] == "t":
            q.append([xx,yy,vx,vy,now+1])
            q.append([xx,yy,-vx,-vy,now+1])
         else :
            q.append([xx+int(S[now])*vx,yy+int(S[now])*vy,vx,vy,now+1])
   return "No"


print(main())