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: Runtime Error

Solution code:
import copy

s = input()
X, Y = list(map(int, input().split()))

#少なくとも、右にx,↑にy進まなきゃいけない
# Fはくっつけられる
# s < 8000 よって N^2くらいならok
# Tが1回→左右 2回→前か後ろ 3回→左右
# この性質から、左右は左右のみで考えればいい
# x方向の数字N個をつかって、xを作成する 足し引きのみ 2^N xを加えて0にできるかどうか

s += "T"

now = 1
# 1はx方向、-1はy方向とする
go = 0
x = []
y = []
for i in s:
    if i == "T":
        if go != 0:
            if now == 1:
                x.append(go)
            else:
                y.append(go)
            go = 0
        now *= -1
    if i == "F":
        go += 1

x.sort()
y.sort()
X = abs(X)
Y = abs(Y)
x_use = sum(x) - X
y_use = sum(y) - Y
if x_use % 2 == 1 or y_use % 2 == 1 or x_use < 0 or y_use < 0:
    print("No")
    exit()
x_use = x_use//2
y_use = y_use//2

x_d = {}
for i in x:
    if i not in x_d:
        x_d[i] = 1
    else:
        x_d[i] += 1

y_d = {}
for i in y:
    if i not in y_d:
        y_d[i] = 1
    else:
        y_d[i] += 1

def solve(integer_list, target_sum,  i=0, sum=0):
    if i == len(integer_list):
        return sum == target_sum
    if (solve(integer_list, target_sum, i + 1, sum)):
        return True
    if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])):
        return True
    return False

if solve(x, x_use) and solve(y, y_use):
    print("Yes")
else:
    print("No")



#あとは、xをつかってxが作れるか
#x = abs(x)
#y = abs(y)
#正でいい
#全部足したやつから、xを弾いたものの/2がxから作れるかという話
#指数乗でやってみる?
#大きいものから使うようにしたらどう?

Submission status: Runtime Error

Solution code:
import sys
s=str(input())
s=list(s)
x,y=map(int,input().split())
fora=0
side=[]
updw=[]
while s[0]=="F":
  fora+=1
  s.pop(0)
flag=1#1のとき横向き、-1のときたて向き
step=0
while s:
  if s[0]=="T":
    s.pop(0)
    if flag==-1: updw+=[step]
    else: side+=[step]
    flag=flag*(-1)
    step=0
  else:
    s.pop(0)
    if len(s)==0:
      if flag==-1: updw+=[step]
      else: side+=[step]
    step+=1
yoko,tate=fora,0
ypossi=len(side)
tpossi=len(updw)
for i in range(1<<len(side)):
  yoko1=yoko
  for j in range(len(side)):
    if (1<<j &i):yoko1+=side[j]
    else :yoko1-=side[j]
  if yoko1==x: break
else: 
  print("No")
  sys.exit()
for i in range(1<<len(updw)):
  tate1=tate
  for j in range(len(updw)):
    if (1<<j &i):tate1+=updw[j]
    else :tate1-=updw[j]
  if tate1==y:
    print("Yes")
    break
else: 
  print("No")
  sys.exit()

Submission status: Runtime Error

Solution code:
s = [len(x) for x in input().split('T')]
x, y = map(int, input().split())
len_s = len(s)
sx = [s[i] for i in range(len_s) if i%2 == 0]
sy = [s[i] for i in range(len_s) if i%2 == 1]

x -= sx[0]
sx = sx[1:]

def is_reachable(p, s):
    origin = 8000
    n = len(s)
    reachable = [[False for _ in range(origin*2+1)] for i in range(n+1)]
    reachable[0][origin] = True

    for i in range(n):
        for j in range(origin*2+1):
            if not reachable[i][j] :
                continue
            if j-s[i] >= 0:
                reachable[i+1][j-s[i]] = True
            if j+s[i] <= origin*2:
                reachable[i+1][j+s[i]] = True
    return reachable[n][p+origin] or reachable[n][-p+origin]


if is_reachable(x, sx) and is_reachable(y, sy):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

Solution code:
s = [len(x) for x in input().split('T')]
x, y = map(int, input().split())
len_s = len(s)
sx = [s[i] for i in range(len_s) if i%2 == 0]
sy = [s[i] for i in range(len_s) if i%2 == 1]

x -= sx[0]
sx = sx[1:]

def is_reachable(p, s):
    origin = 8
    n = len(s)
    reachable = [[False for _ in range(origin*2+1)] for i in range(n+1)]
    reachable[0][origin] = True

    for i in range(n):
        for j in range(origin*2+1):
            if not reachable[i][j] :
                continue
            if j-s[i] >= 0:
                reachable[i+1][j-s[i]] = True
            if j+s[i] <= origin*2:
                reachable[i+1][j+s[i]] = True
    return reachable[n][p+origin] or reachable[n][-p+origin]


if is_reachable(x, sx) and is_reachable(y, sy):
    print('Yes')
else:
    print('No')

Submission status: Runtime Error

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

move = s.split('T')
yoko, tate = [], []
for i in range(len(move)):
    if i % 2 == 0:
        yoko.append(len(move[i]))
    else:
        tate.append(len(move[i]))


def dfs(i, arr, pos, goal):
    if i == len(arr):
        return pos == goal
    ret1 = dfs(i + 1, arr, pos + arr[i], goal)
    if ret1:
        return ret1
    ret2 = dfs(i + 1, arr, pos - arr[i], goal)
    if ret2:
        return ret2
    return False

# print(move)
# print(yoko, tate)

end_in_x = dfs(0, yoko, 0, x)
end_in_y = dfs(0, tate, 0, y)
ans = 'Yes' if end_in_x and end_in_y else 'No'
print(ans)