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

Solution code:
s=input()
x,y=map(int,input().split())
dpx=set()
dpy=set()
xs=[]
ys=[]
tmp=0
d=0
for c in s:
    if c=='F':
        tmp+=1
    elif c=='T':
        if tmp:
            if d==0:
                xs.append(tmp)
            else:
                ys.append(tmp)
        d^=1
        tmp=0
if tmp:
    if d==0:
        xs.append(tmp)
    else:
        ys.append(tmp)
if xs:
    dpx.add(xs[0])
    xs=xs[1:]
else:
    dpx.add(0)
dpy.add(0)
for a in xs:
    tmp=set()
    for dx in dpx:
        tmp.add(dx+a)
        tmp.add(dx-a)
    dpx=tmp
for a in ys:
    tmp=set()
    for dy in dpy:
        tmp.add(dy+a)
        tmp.add(dy-a)
    dpy=tmp

#print(dpx,dpy)
if x in dpx and y in dpy:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
s=input()
x,y=map(int,input().split())
dpx=set()
dpy=set()
xs=[]
ys=[]
tmp=0
d=0
for c in s:
    if c=='F':
        tmp+=1
    elif c=='T':
        if tmp:
            if d==0:
                xs.append(tmp)
            else:
                ys.append(tmp)
        d^=1
        tmp=0
if tmp:
    if d==0:
        xs.append(tmp)
    else:
        ys.append(tmp)
if xs:
    dpx.add(xs[0])
    xs=xs[1:]
dpy.add(0)
for a in xs:
    tmp=set()
    for dx in dpx:
        tmp.add(dx+a)
        tmp.add(dx-a)
    dpx=tmp
for a in ys:
    tmp=set()
    for dy in dpy:
        tmp.add(dy+a)
        tmp.add(dy-a)
    dpy=tmp

#print(dpx,dpy)
if x in dpx and y in dpy:
  print("Yes")
else:
  print("No")

Submission status: Wrong Answer

Solution code:
s = list(input())
x, y = map(int, input().split())
dir, move, dx, dy = 0, 0, [abs(x)], [abs(y)]
s.append('E')
for i in s:
    if i == 'F':
        move += 1
    else:
        if dir % 2 == 0:
            dx.append(move)
        else:
            dy.append(move)
        move = 0
        dir += 1
temp = 0
for i in sorted(dx, reverse=True):
    if temp < 0:
        temp += i
    else:
        temp -= i
adx = temp
temp = 0
for i in sorted(dy, reverse=True):
    if temp < 0:
        temp += i
    else:
        temp -= i
ady = temp
if adx == ady == 0:
    print('Yes')
else:
    print('No')

Submission status: Wrong Answer

Solution code:
s = list(input())
x,y = list(map(int,input().split()))
myx,myy = 0,0
vector = "right"
line_x,line_y = x,y

def turn(vector,myx,myy):
    if vector == "up" or vector == "down":
        if myx < line_x:
            return "right"
        else:
            return"left"
    else:
        if myy < line_y:
            return "up"
        else:
            return "down"

def go(vector):
    if vector == "up":
        return 0,1
    elif vector == "right":
        return 1,0
    elif vector == "down":
        return 0,-1
    else:
        return -1,0

for exe in s:
    if exe == "F":
        plus_x,plus_y = go(vector)
        myx += plus_x
        myy += plus_y
    else:
        vector = turn(vector,myx,myy)

if myx == x and myy == y:
    print("Yes")
else:
    print("No")

Submission status: Wrong Answer

Solution code:
import queue
s=input()
dic=[(0,-1),(1,0),(0,1),(-1,0)]
numF=s.count('F')
numT=s.count('T')
x,y=map(int,input().split())
q=queue.Queue()
q.put((0,0,1,0,0))#x,y,v,t,f
while not q.empty():
    now=q.get()
    if now[4]>numF or now[3]>numT:
        continue
    elif now[0]==x and now[1]==y and now[4]==numF and now[3]==numT:
        print('Yes')
        exit()
    for i in range(4):
        q.put((now[0]+dic[i][0],now[1]+dic[i][1],i,now[3]+(0 if i==now[2] else 1 if i!=(now[2]+2)%2 else 2),now[4]+1))
print('No')

Submission status: Wrong Answer

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

state = [0, 0]
direction = [1, 0]
for i in s:
    if i == 'F':
        state[0] += direction[0]
        state[1] += direction[1]
    else:
        if direction == [1, 0] or direction == [-1, 0]:
            if state[1] <= y:
                direction = [0, 1]
            else:
                direction = [0, -1]
        else:
            if state[0] <= x:
                direction = [1, 0]
            else:
                direction = [-1, 0]
if state == [x, y]:
    print ('Yes')
else:
    print ('No')

Submission status: Wrong Answer

Solution code:
s=input()
x,y=map(int,input().split())
D=[(1,0),(0,1),(-1,0),(0,-1)]
di=0
cx=0
cy=0
for c in s:
  if c=='F':
    cx+=D[di][0]
    cy+=D[di][1]
  elif c=='T':
    dx=x-cx
    dy=y-cy
    nx1=cx+D[(di+1)%4][0]
    ny1=cy+D[(di+1)%4][1]
    nx2=cx+D[(di-1+4)%4][0]
    ny2=cy+D[(di-1+4)%4][1]
    m1=abs(x-nx1)+abs(y-ny1)
    m2=abs(x-nx2)+abs(y-ny2)
    if m1 <= m2:
      di=(di+1)%4
    else:
      di=(di-1+4)%4

if cx == x and cy == y:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

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

# Tで区切り、各Tの前にFが何文字あるか数える
steps = []
cnt = 0
for i in range(len(s)):
    if s[i] == "F":
        cnt += 1
    elif s[i] == "T":
        steps.append(cnt)
        cnt = 0
# 最後のブロックについて
if cnt > 0:
    steps.append(cnt)
AX = steps[0::2]
AY = steps[1::2]

# X軸方向の最大値
max_X = sum(AX)
# dpX[i][j] = X軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 2*max_X だが、実際のX座標は -max_X, ..., 0, ..., max_X
# 原点(x=0)は、j = max_Xに相当する
dpX = [[0 for _ in range(2 * max_X + 1)] for _ in range(len(AX) + 1)]
dpX[0][max_X] = 1
# 最初に右へ移動する場合
if s[0] == "F":
    dpX[1][max_X + AX[0]] = 1
    for i in range(1, len(AX)):
        for j in range(2 * max_X + 1):
            if dpX[i][j] == 1:
                # +X方向に移動
                if j + AX[i] <= 2 * max_X:
                    dpX[i + 1][j + AX[i]] = 1
                # -X方向に移動
                if 0 <= j - AX[i]:
                    dpX[i + 1][j - AX[i]] = 1
# 最初に回転する場合
else:
    for i in range(len(AX)):
        for j in range(2 * max_X + 1):
            if dpX[i][j] == 1:
                # +X方向に移動
                if j + AX[i] <= 2 * max_X:
                    dpX[i + 1][j + AX[i]] = 1
                # -X方向に移動
                if 0 <= j - AX[i]:
                    dpX[i + 1][j - AX[i]] = 1
# Y軸方向の最大値
max_Y = sum(AY)
# dpY[i][j] = Y軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 2*max_Y だが、実際のY座標は -max_Y, ..., 0, ..., max_Y
# 原点(y=0)は、j = max_Yに相当する
dpY = [[0 for _ in range(2 * max_Y + 1)] for _ in range(len(AY) + 1)]
dpY[0][max_Y] = 1
for i in range(len(AY)):
    for j in range(2 * max_Y + 1):
        if dpY[i][j] == 1:
            # +Y方向に移動
            if j + AY[i] <= 2 * max_Y:
                dpY[i + 1][j + AY[i]] = 1
            # -Y方向に移動
            if 0 <= j - AY[i]:
                dpY[i + 1][j - AY[i]] = 1

if -max_X <= x <= max_X and -max_Y <= y <= max_Y:
    if dpX[-1][x + max_X] == 1 and dpY[-1][y + max_Y] == 1:
        print("Yes")
        exit()
print("No")

Submission status: Time Limit Exceeded

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

# Tで区切り、各Tの前にFが何文字あるか数える
steps = []
cnt = 0
for i in range(len(s)):
    if s[i] == "F":
        cnt += 1
    elif s[i] == "T":
        steps.append(cnt)
        cnt = 0
# 最後のブロックについて
if cnt > 0:
    steps.append(cnt)
AX = steps[0::2]
AY = steps[1::2]

# dpX[i][j] = X軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 16000 だが、実際のX座標は -8000, ..., 0, ..., 8000
# 原点(x=0)は、j = 8000に相当する
dpX = [[0 for _ in range(2 * 8000 + 1)] for _ in range(len(AX) + 1)]
dpX[0][8000] = 1
# 最初に右へ移動する場合
if s[0] == "F":
    dpX[1][8000 + AX[0]] = 1
    for i in range(1, len(AX)):
        for j in range(2 * 8000 + 1):
            if dpX[i][j] == 1:
                # +X方向に移動
                if j + AX[i] <= 2 * 8000:
                    dpX[i + 1][j + AX[i]] = 1
                # -X方向に移動
                if 0 <= j - AX[i]:
                    dpX[i + 1][j - AX[i]] = 1
# 最初に回転する場合
else:
    for i in range(len(AX)):
        for j in range(2 * 8000 + 1):
            if dpX[i][j] == 1:
                # +X方向に移動
                if j + AX[i] <= 2 * 8000:
                    dpX[i + 1][j + AX[i]] = 1
                # -X方向に移動
                if 0 <= j - AX[i]:
                    dpX[i + 1][j - AX[i]] = 1

# dpY[i][j] = Y軸方向の移動をi回行って、jに到達できるか
# j = 0, 1, ..., 16000 だが、実際のY座標は -8000, ..., 0, ..., 8000
# 原点(y=0)は、j = 8000に相当する
dpY = [[0 for _ in range(2 * 8000 + 1)] for _ in range(len(AY) + 1)]
dpY[0][8000] = 1
for i in range(len(AY)):
    for j in range(2 * 8000 + 1):
        if dpY[i][j] == 1:
            # +Y方向に移動
            if j + AY[i] <= 2 * 8000:
                dpY[i + 1][j + AY[i]] = 1
            # -Y方向に移動
            if 0 <= j - AY[i]:
                dpY[i + 1][j - AY[i]] = 1

if dpX[-1][x + 8000] == 1 and dpY[-1][y + 8000] == 1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:

def YesNo(b):
    print("Yes" if b else "No")


def solve(v, l, ini):
    ml = 8000*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+8000] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+8000]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [], []
    for i in range(len(f)):
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    YesNo(solve(x, xl, [si]) and solve(y, yl[1:], [-yl[0], yl[0]]))

Submission status: Time Limit Exceeded

Solution code:


def YesNo(b):
    print("Yes" if b else "No")


def solve(n, v, l, ini):
    ml = n*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+n] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+n]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [], []
    for i in range(len(f)):
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    if len(yl) == 0:
        yl.append(0)
    YesNo(solve(len(s), x, xl, [si]) and solve(len(s), y, yl[1:], [-yl[0], yl[0]]))

Submission status: Time Limit Exceeded

Solution code:


def YesNo(b):
    print("Yes" if b else "No")


def solve(v, l, ini):
    ml = 8000*2+1
    dp = [[False]*ml for i in range(len(l)+1)]
    for i in range(len(ini)):
        dp[0][ini[i]+8000] = True
    for i in range(1, len(l)+1):
        for j in range(ml):
            if (j+l[i-1]) < ml and dp[i-1][j]:
                dp[i][j+l[i-1]] = True
            if (j-l[i-1]) >= 0 and dp[i-1][j]:
                dp[i][j-l[i-1]] = True
    return dp[len(l)][v+8000]


s = input()
x, y = map(int, input().split())
si = 0
while si < len(s) and s[si] == 'F':
    si += 1

s = s[si:]
if len(s) == 0:
    YesNo(x == si and y == 0)
else:
    f = s.split('T')[1:]
    xl, yl = [], []
    for i in range(len(f)):
        if i % 2 == 0:
            yl.append(len(f[i]))
        else:
            xl.append(len(f[i]))

    if len(yl) == 0:
        yl.append(0)
    YesNo(solve(x, xl, [si]) and solve(y, yl[1:], [-yl[0], yl[0]]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

s = str(input())
obj_x, obj_y = list(map(int, input().split()))


x = []
y = []
flag = 0
num = 0
for i in range(len(s)):
    if s[i] == "T":
        if flag % 2 == 0:
            x.append(num)
        else:
            y.append(num)
        flag += 1
        num = 0
    else:
        num += 1

if num > 0:
    if flag % 2 == 0:
        x.append(num)
    else:
        y.append(num)


if x == []:
    x = [0]
if y == []:
    y = [0]


num_x = sum(x)
num_y = sum(y)

max_x = num_x*2+1
max_y = num_y*2+1

dp_x = [[0]*((len(x)+1)) for i in range(max_x)]
dp_y = [[0]*((len(y)+1)) for i in range(max_y)]

dp_x[num_x][0] = 1
dp_y[num_y][0] = 1

# print(x)
dp_x[num_x+x[0]][1]=1

# print(dp_x)

for i in range(1, len(x)):
    num = x[i]
    for j in range(0, len(dp_x)):
        if j+num < max_x:
            dp_x[j+num][i+1] = max(dp_x[j+num][i+1], dp_x[j][i]*1)
        if j-num >= 0:
            dp_x[j-num][i+1] = max(dp_x[j-num][i+1], dp_x[j][i]*1)
        # if dp_x[j][i] == 1:
        #     print(j+num, j-num)
for i in range(0, len(y)):
    num = y[i]
    for j in range(0, len(dp_y)):
        if j+num < max_y:
            dp_y[j+num][i+1] = max(dp_y[j+num][i+1], dp_y[j][i]*1)
        if j-num >= 0:
            dp_y[j-num][i+1] = max(dp_y[j-num][i+1], dp_y[j][i]*1)
        # if dp_y[j][i] == 1:
        #     print(j+num, j-num)


if (num_x+obj_x)<len(dp_x) and (num_x+obj_x)>=0:
    ans_x = dp_x[num_x+obj_x][-1]
else:
    print("No")
    exit()
if (num_y+obj_y)<len(dp_y) and (num_y+obj_y)>=0:
    ans_y = dp_y[num_y+obj_y][-1]
else:
    print("No")
    exit()

# print(dp_x)
if ans_x*ans_y == 1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

s = str(input())
obj_x, obj_y = list(map(int, input().split()))


x = []
y = []
flag = 0
num = 0
for i in range(len(s)):
    if s[i] == "T":
        if flag % 2 == 0:
            x.append(num)
        else:
            y.append(num)
        flag += 1
        num = 0
    else:
        num += 1

if num > 0:
    if flag % 2 == 0:
        x.append(num)
    else:
        y.append(num)


if x == []:
    x = [0]
if y == []:
    y = [0]

# print(x)
# print(y)
max_ = 8000*2+1
dp_x = [[0]*((len(x)+1)) for i in range(8000*2+1)]
dp_y = [[0]*((len(y)+1)) for i in range(8000*2+1)]

dp_x[8000][0] = 1
dp_y[8000][0] = 1

for i in range(0, len(x)):
    num = x[i]
    for j in range(0, len(dp_x)):

        if j+num < max_:
            dp_x[j+num][i+1] = max(dp_x[j+num][i+1], dp_x[j][i]*1)
        if j-num > 0:
            dp_x[j-num][i+1] = max(dp_x[j-num][i+1], dp_x[j][i]*1)
        # if dp_x[j][i] == 1:
            # print(j+num, j-num)
for i in range(0, len(y)):
    num = y[i]
    for j in range(0, len(dp_y)):

        if j+num < max_:
            dp_y[j+num][i+1] = max(dp_y[j+num][i+1], dp_y[j][i]*1)
        if j-num > 0:
            dp_y[j-num][i+1] = max(dp_y[j-num][i+1], dp_y[j][i]*1)
        # if dp_y[j][i] == 1:
            # print(j+num, j-num)


ans_x = dp_x[8000+obj_x][-1]
ans_y = dp_y[8000+obj_y][-1]

if ans_x*ans_y == 1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()
N = len(s)
x,y = map(int,input().split())
AX = []
AY = []
flag = 0
cnt = 0
for i in range(len(s)):
    if s[i]=="F":
        cnt += 1
    else:
        if flag==0:
            AX.append(cnt)
            cnt = 0
            flag = 1
        else:
            AY.append(cnt)
            cnt = 0
            flag = 0
if cnt>0 and flag==0:
    AX.append(cnt)
if cnt>0 and flag==1:
    AY.append(cnt)
dpX = [[0 for _ in range(2*N+1)] for _ in range(len(AX)+1)]
if s[0]=="F":
    dpX[1][N+AX[0]] = 1
    for i in range(1,len(AX)):
        for j in range(2*N+1):
            if 0<=j+AX[i]<=2*N:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*N:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
else:
    dpX[0][N] = 1
    for i in range(len(AX)):
        for j in range(2*N+1):
            if 0<=j+AX[i]<=2*N:
                dpX[i+1][j+AX[i]] = dpX[i+1][j+AX[i]] or dpX[i][j]
            if 0<=j-AX[i]<=2*N:
                dpX[i+1][j-AX[i]] = dpX[i+1][j-AX[i]] or dpX[i][j]
dpY = [[0 for _ in range(2*N+1)] for _ in range(len(AY)+1)]
dpY[0][N] = 1
for i in range(len(AY)):
    for j in range(2*N+1):
        if 0<=j+AY[i]<=2*N:
            dpY[i+1][j+AY[i]] = dpY[i+1][j+AY[i]] or dpY[i][j]
        if 0<=j-AY[i]<=2*N:
            dpY[i+1][j-AY[i]] = dpY[i+1][j-AY[i]] or dpY[i][j]
if dpX[len(AX)][N+x]==1 and dpY[len(AY)][N+y]==1:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
def main():
    S = input() + 'T'
    x, y = map(int, input().split())
    #データ加工
    moveX, moveY = [], []
    if S[0] == 'T': moveX.append(0)
    move ={0:moveX, 1:moveY}
    direct = 0
    step = 0
    for s in S:
        if s == 'T':
            if step > 0:
                move[direct].append(step)
                step = 0
            direct ^= 1 
        else:
            step += 1
    #判定
    if possible(x, moveX[1:], moveX[0]) and possible(y, moveY):
        print('Yes')
    else:
        print('No')


def possible(target, move, offset=0):
    Sum = sum(move)
    for k in range(len(move)//2+1):
        for c in combinations(move,k):
            moved = Sum-2*sum(c)
            if moved == abs(target-offset):
                return True
    return False


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
def main():
    S = input() + 'T'
    x, y = map(int, input().split())
    #データ加工
    moveX, moveY = [], []
    move ={0:moveX, 1:moveY}
    direct = 0
    step = 0
    for s in S:
        if s == 'T':
            move[direct].append(step)
            direct ^= 1
            step = 0
        else:
            step += 1
    #判定
    moveX = [moveX[0]] + [i for i in moveX[1:] if i != 0]
    moveY = [i for i in moveY if i != 0]
    if possible(x, moveX[1:], moveX[0]) and possible(y, moveY):
        print('Yes')
    else:
        print('No')


def possible(target, move, offset=0):
    Sum = sum(move)
    for k in range(len(move)//2+1):
        for c in combinations(move,k):
            moved = Sum-2*sum(c)
            if moved == abs(target-offset):
                return True
    return False


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
def main():
    S = input() + 'T'
    x, y = map(int, input().split())
    moveX, moveY = [], []
    move ={0:moveX, 1:moveY}
    direct = 0
    step = 0
    for s in S:
        if s == 'T':
            move[direct].append(step)
            direct ^= 1
            step = 0
        else:
            step += 1
    
    if possible(x, moveX[1:], sum(moveX)) and possible(y, moveY, sum(moveY)):
        print('Yes')
    else:
        print('No')


def possible(target, move, furthest):
    for k in range(len(move)+1):
        for c in combinations(move,k):
            if furthest-2*sum(c) == target:
                return True
    return False


main()

Submission status: Time Limit Exceeded

Solution code:
s = input()
N = len(s)
gx,gy = map(int,input().split())

cum_turn = 0
now_move = 0
x_moves = []
y_moves = []
for i in range(N):
    if s[i] == 'F':
        now_move += 1
    else:
        if cum_turn % 2 == 0:
            x_moves.append(now_move)
        else:
            y_moves.append(now_move)
        now_move = 0
        cum_turn += 1
if now_move > 0:
    if cum_turn % 2 == 0:
        x_moves.append(now_move)
    else:
        y_moves.append(now_move)
#print(x_moves,y_moves)

N_x_move = len(x_moves)
N_y_move = len(y_moves)

# dpx[i][x] := i回目の移動の後X座標がxとなっていることは可能か
dpx = [[0]*(2*N+2) for _ in range(N_x_move+1)]
dpx[1][N+x_moves[0]] = 1
# 配りDP
for move in range(1,N_x_move):
    for x in range(2*N+2):
        if dpx[move][x]:
            plus_to = x + x_moves[move]
            minus_to = x - x_moves[move]
            #print(x,move,plus_to)
            #print(dpx)
            dpx[move+1][plus_to] = dpx[move][x]
            dpx[move+1][minus_to] = dpx[move][x]
#print(dpx[N_x_move][gx+N])

dpy = [[0]*(2*N+2) for _ in range(N_y_move+1)]
dpy[0][N] = 1

for move in range(0,N_y_move):
    for y in range(2*N+2):
        if dpy[move][y]:
            plus_to = y + y_moves[move]
            minus_to = y - y_moves[move]
            dpy[move+1][plus_to] = dpy[move][y]
            dpy[move+1][minus_to] = dpy[move][y]

if dpx[N_x_move][gx+N]*dpy[N_y_move][gy+N]:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
"""
ベクトルが(a,b)離れた地点が目的地の状況で命令Sが与えられたとき、目的地に到達可能か？
というDPをすればよい。
"""
import sys
sys.setrecursionlimit(20000)
s = input()
x,y = map(int,input().split())

splitS = list(s.split("T"))
default = (splitS[0].count("F"),0)

yoko = []
for i in range(2,len(splitS),2):
    yoko.append(splitS[i].count("F"))

tate = []
for i in range(1,len(splitS),2):
    tate.append(splitS[i].count("F"))

def f(i,n,data,dp,distination):
    if (i,n) not in dp:
        if i == len(data) and n == distination:
            dp[(i,n)] = True
        elif i == len(data):
            dp[(i,n)] = False
        else:
            dp[(i,n)] = False or f(i+1,n+data[i],data,dp,distination)
            dp[(i,n)] = dp[(i,n)] or f(i+1,n-data[i],data,dp,distination)
    return dp[(i,n)]
dp1 = {}
dp2 = {}
f(0,default[0],yoko,dp1,x)
f(0,default[1],tate,dp2,y)
if dp1[(0,default[0])] and dp2[(0,default[1])]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
"""
ベクトルが(a,b)離れた地点が目的地の状況で命令Sが与えられたとき、目的地に到達可能か？
というDPをすればよい。
"""
import sys
sys.setrecursionlimit(20000)
s = list(input())
x,y = map(int,input().split())
#memo[(i,a,b,v)] => のこりの命令がS[i:]ある状態で、今いる地点は(a,b)、今向いているベクトルはvという状態で目的地に到達可能か？
memo = {}
FCount = s.count("F")
def f(i,a,b,rest,v):
    if (i,a,b,v) not in memo:
        if rest < abs(x-a)+abs(y-b) or (rest-(abs(x-a)+abs(y-b)))%2 == 1:
            memo[(i,a,b,v)] = False
        else:
            if i == len(s) and a==x and b == y:
                memo[(i,a,b,v)] = True
            elif i == len(s):
                memo[(i,a,b,v)] = False
            else:
                comand = s[i]
                res = False
                if comand == "F":
                    if v == 0:
                        res = res or f(i+1,a+1,b,rest-1,v)
                    if v == 1:
                        res = res or f(i+1,a,b-1,rest-1,v)
                    if v == 2:
                        res = res or f(i+1,a-1,b,rest-1,v)
                    if v == 3:
                        res = res or f(i+1,a,b+1,rest-1,v)
                else:
                    res = res or f(i+1,a,b,rest,(v+1)%4)
                    res = res or f(i+1,a,b,rest,(v-1+4)%4)
                memo[(i,a,b,v)] = res
    return memo[(i,a,b,v)]

if f(0,0,0,FCount,0):
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input()
x, y = (int(x) for x in input().split())
X = []
Y = []
cnt, turn = 0, 0
s += 'T'
for c in s:
    if c == 'F':
        cnt += 1
    else:
        if turn & 1:
            Y.append(cnt)
            turn = 0
        else:
            X.append(cnt)
            turn = 1
        cnt = 0
lenX = len(X)-1
Xmoveable = {X[0] + sum(-X[i+1] if bit & (1<<i) else X[i+1] for i in range(lenX)) for bit in range(2**lenX)}
lenY = len(Y)
Ymoveable = {sum(-Y[i] if bit & (1<<i) else Y[i] for i in range(lenY)) for bit in range(2**lenY)}

if x in Xmoveable and y in Ymoveable:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
OFFSET = 9000
s = input()
tx,ty = map(int,input().split())
F = [len(s) for s in s.split('T')]
tx += OFFSET
ty += OFFSET
tx -= F[0]
Fx = F[2::2]
Fy = F[1::2]



def dfs(x, i, tgt, dp, f_list):
  if dp[x][i]:
    return
  dp[x][i] = True
  if i >= len(f_list):
    return
    
  d = f_list[i]
  dfs(x + d, i + 1, tgt, dp, f_list)
  dfs(x - d, i + 1, tgt, dp, f_list)
  

dpx = [[False for j in range(OFFSET)] for i in range(OFFSET*2)]
dpy = [[False for j in range(OFFSET)] for i in range(OFFSET*2)]

dfs(OFFSET, 0, tx, dpx, Fx)
dfs(OFFSET, 0, ty, dpy, Fy)

if dpx[tx][len(Fx)] and dpy[ty][len(Fy)]:
  print("Yes")
else:
  print("No")

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def check(vec, init_pos, target_pos):
    base = 8000
    dp = [[False] * 16001 for _ in range(len(vec) + 1)]
    dp[0][init_pos + base] = True

    for i in range(len(vec)):
        for j in range(16001):
            if j - vec[i] >= 0 and dp[i][j - vec[i]] or j + vec[i] <= 16000 and dp[i][j + vec[i]]:
                dp[i + 1][j] = True

    return dp[len(vec)][target_pos + base]


def main():
    S = readline().strip()
    x, y = map(int, readline().split())

    idx = len(S)
    for i, c in enumerate(S):
        if c == 'T':
            idx = i
            break

    init_x = idx
    step = [[0] for _ in range(2)]
    i = 0
    for c in S[idx:]:
        if c == 'T':
            i = 1 - i
            step[i].append(0)
        else:
            step[i][-1] += 1

    ok = check(step[0], init_x, x) and check(step[1], 0, y)

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

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

xy = True
x_s = []
y_s = []
cnt = 0
for s in string:
    if s == "F":
        cnt += 1
    else:
        if xy:
            x_s.append(cnt)
            xy = False
        else:
            y_s.append(cnt)
            xy = True
        cnt = 0
if xy:
    x_s.append(cnt)
    xy = False
else:
    y_s.append(cnt)
    xy = True
x_can = [False for _ in range(8001)]
y_can = [False for _ in range(8001)]

x_can[x_s[0]] = True
for xx in x_s[1:]:
    for i in range(8000, xx - 1, -1):
        if x_can[i - xx]:
            x_can[i] = True

y_can[0] = True
for yy in y_s:
    for i in range(8000, yy - 1, -1):
        if y_can[i - yy]:
            y_can[i] = True
            
x_pos = (x + sum(x_s))
y_pos = (y + sum(y_s))
if x_pos % 2 == 1 or y_pos % 2 == 1:
    print("No")
elif x_can[x_pos // 2] and y_can[y_pos // 2]:
    print("Yes")
else:
    print("No")

Submission status: Time Limit Exceeded

Solution code:
s=input()+'T'
x,y=list(map(int,input().split()))
x+=10000
y+=10000
n=len(s)
i=0

while i<n and s[i]=='F':
    i+=1

dx=[[0]*20000 for _ in range(10000)]
dy=[[0]*20000 for _ in range(10000)]

dx[0][i+10000]=1
dy[0][10000]=1

lstx=[]
lsty=[]
d='x'
cnt=0

while i<n:
    if s[i]=='F':
        cnt+=1
    else:
        if cnt>0:
            if d=='x':
                lstx.append(cnt)
            else:
                lsty.append(cnt)
        
        if d=='x':
            d='y'
        else:
            d='x'
        cnt=0
    
    i+=1

for i,cx in enumerate(lstx):
    for j in range(20000):
        if dx[i][j]==0:
            continue
        if j+cx<20000:
            dx[i+1][j+cx]=1
        if j-cx>-1:
            dx[i+1][j-cx]=1

for i,cy in enumerate(lsty):
    for j in range(20000):
        if dy[i][j]==0:
            continue
        if j+cy<20000:
            dy[i+1][j+cy]=1
        if j-cy>-1:
            dy[i+1][j-cy]=1

if dx[len(lstx)][x]==1 and dy[len(lsty)][y]==1:
    print('Yes')
else:
    print('No')

Submission status: Time Limit Exceeded

Solution code:
s = input().strip()
N = len(s)
x,y = map(int,input().split())
flag0 = 0
for i in range(N):
    if s[i]=="T":
        ind = i
        flag0 = 1
        break
if flag0==0:
    if y==0 and x==N:
        print("Yes")
    else:
        print("No")
else:
    C={"x":[],"y":[]}
    flag=0
    cnt = 0
    for i in range(ind+1,N):
        if s[i]!="T":
            cnt += 1
        else:
            if flag==0 and cnt>0:
                C["y"].append(cnt)
            elif flag==1 and cnt>0:
                C["x"].append(cnt)
            cnt = 0
            flag = 1-flag
    if flag==0:
        C["y"].append(cnt)
    else:
        C["x"].append(cnt)
    nx = len(C["x"])
    xlim = 0
    for i in range(nx):
        xlim += C["x"][i]
    ny = len(C["y"])
    ylim = 0
    for i in range(ny):
        ylim += C["y"][i]
    x = x-ind  #x>=-N
    if x<=-xlim-1 or x>=xlim+1 or y<=-ylim-1 or y>=ylim+1:
        print("No")
    else:
        dp1 = {(i,j):0 for i in range(nx+1) for j in range(-xlim,xlim+1)}
        dp1[(0,0)]=1
        for i in range(1,nx+1):
            for j in range(-xlim,xlim+1):
                if j-C["x"][i-1]>=-xlim:
                    dp1[(i,j)] = dp1[(i-1,j-C["x"][i-1])]
                if j+C["x"][i-1]<=xlim:
                    dp1[(i,j)] = dp1[(i,j)]|dp1[(i-1,j+C["x"][i-1])]
        dp0 = {(i,j):0 for i in range(ny+1) for j in range(-ylim,ylim+1)}
        dp0[(0,0)] = 1
        for i in range(1,ny+1):
            for j in range(-ylim,ylim+1):
                if j-C["y"][i-1]>=-ylim:
                    dp0[(i,j)] = dp0[(i-1,j-C["y"][i-1])]
                if j+C["y"][i-1]<=ylim:
                    dp0[(i,j)] = dp0[(i,j)]|dp0[(i-1,j+C["y"][i-1])]
        if dp1[(nx,x)]==1 and dp0[(ny,y)]==1:
            print("Yes")
        else:
            print("No")

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
x, y = map(int, input().split())
for i in range(n):
    if s[i]=='T':
        break
else:
    i += 1
x -= i
xs = {}
ys = {}
now = 0
xy = 'y'
for j in range(i+1, n+1):
    if j<n and s[j]=='F':
        now += 1
        continue
    if xy=='x':
        if now>0:
            if now not in xs:
                xs[now] = 0
            xs[now] += 1
        xy = 'y'
    else:
        if now>0:
            if now not in ys:
                ys[now] = 0
            ys[now] += 1
        xy = 'x'
    now = 0

def dfs(li, idx, now, target):
    if idx==len(li):
        return now==target
    for i in range(li[idx][1]+1):
        if dfs(li, idx+1, now+li[idx][0]*(li[idx][1]-2*i), target):
            return True
    return False

ans = dfs(list(xs.items()), 0, 0, x) and dfs(list(ys.items()), 0, 0, y)
print('Yes' if ans else 'No')