def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}')):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
def D(N, S, ab):
target = S
init = []
diff = []
for a, b, in ab:
# a < b になるようにする
if a >= b :
a, b = b, a
init.append(1) # 裏(T)
else:
init.append(0) # 表(H)
target -= a
diff.append(b - a)
if target < 0: return "No"
dp = [[0] * (target + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
# print(diff[i])
for j in range(target + 1):
dp[i + 1][j] |= dp[i][j]
if j >= diff[i]:
dp[i + 1][j] |= dp[i][j - diff[i]]
# print(*dp, sep="\n")
if not dp[-1][target]:
print("No")
return
print("Yes")
v = target
for i, d in enumerate(diff[::-1]):
if not dp[N - 1 - i][v]:
init[N - 1 - i] ^= 1
v -= d
print(*["T" if c else "H" for c in init], sep="")test_all(D)
def D(N, S, ab):
target = S
init = []
diff = []
for a, b, in ab:
# a < b になるようにする
if a >= b :
a, b = b, a
init.append(1) # 裏(T)
else:
init.append(0) # 表(H)
target -= a
diff.append(b - a)
if target < 0: return "No"
dp = [[1] + [0] * target]
for d in diff:
new = dp[-1].copy()
for i in range(target):
if dp[-1][i] and i + d <= target:
new[i + d] = 1
dp.append(new)
if not dp[-1][target]:
print("No")
return
print("Yes")
v = target
for i, d in enumerate(diff[::-1]):
if not dp[N - 1 - i][v]:
init[N - 1 - i] ^= 1
v -= d
print(*["T" if c else "H" for c in init], sep="")def D(*n):
passtest_all(D)
AtCoder Inc.
