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 C(N, A, B, S):
ans = B * (N // 2)
for i in range(N):
total = A * i
for l, r in zip(S[:N // 2], S[(N + 1) // 2:][::-1]):
if l != r: total += B
ans = min(ans, total)
S = S[1:] + S[:1]
return ans
test_all(C)
def C(N, A, B, S):
ans = B * (N // 2)
S += S
for i in range(N - 1):
total = A * i
for j in range(N // 2):
if S[i + j] != S[i + (N - 1 - j)]: total += B
ans = min(ans, total)
return ans
test_all(C)
def D(N, X, AB):
seed = []
for A, B in AB.items():
seed += [A] * B
def search(seed, target):
numbers = set([0])
for s in seed:
for n in list(numbers):
nxt = n + s
if nxt == target: return True
if nxt < target: numbers.add(nxt)
return False
return "Yes" if search(seed, X) else "No"test_all(D)
def D(N, X, AB):
seed = []
for A, B in AB.items():
seed += [A] * B
dp = [True] + [False] * X
for s in seed:
for i in range(X - s, -1, -1):
if dp[i]: dp[i + s] = True
return "Yes" if dp[X] else "No"test_all(D)
def D(N, X, AB):
seed = []
for A, B in AB.items():
seed += [A] * B
dp = [True] + [False] * X
for s in seed:
new = dp.copy()
# for i, b in enumerate(dp[: X + 1 - s]):
# if b: new[i + s] = True
for i in range(X + 1 - s):
if dp[i]: new[i + s] = True
if new[-1]:
return "Yes"
dp = new
return "No"test_all(D)
from collections import deque, defaultdict
def E(N, A, S, Q, UV):
A = [0] + A
edge = defaultdict(list)
for i, s in enumerate(S, 1):
for j, k in enumerate(s, 1):
if k == "Y": edge[i].append(j)
for u, v in UV:
value = [0] * (N + 1)
value[u] = A[u]
step = [N] * (N + 1)
step[u] = 0
q = deque([u])
while q:
now = q.popleft()
if now == v: break
for city in edge[now]:
if step[city] > step[now] + 1:
step[city] = step[now] + 1
value[city] = value[now] + A[city]
q.append(city)
elif step[city] == step[now] + 1:
value[city] = max(value[city], value[now] + A[city])
else:
print("Impossible")
continue
print(step[v], value[v])
test_all(E)
from itertools import product
def E(N, A, S, Q, UV):
A = [0] + A
d = [[N] * (N + 1) for _ in range(N + 1)]
for i in range(N): d[i][i] = 0
val = [[0] * (N + 1) for _ in range(N + 1)]
for i, s in enumerate(S, 1):
for j, k in enumerate(s, 1):
if k == "Y":
d[i][j] = 1
val[i][j] = A[j]
for j, i, k in product(range(1,N + 1), repeat=3):
if d[i][j] + d[j][k] < d[i][k]:
d[i][k] = d[i][j] + d[j][k]
val[i][k] = val[i][j] + val[j][k]
elif d[i][j] + d[j][k] == d[i][k] and val[i][j] + val[j][k] > val[i][k]:
val[i][k] = val[i][j] + val[j][k]
for u, v in UV:
if d[u][v] == N:
print("Impossible")
else:
print(d[u][v], val[u][v] + A[u])test_all(E)
from collections import deque, defaultdict
def E(N, A, S, Q, UV):
A = [0] + A
edge = defaultdict(list)
for i, s in enumerate(S, 1):
for j, k in enumerate(s, 1):
if k == "Y": edge[i].append(j)
ans = {}
for i in range(1, N + 1):
value = [0] * (N + 1)
value[i] = A[i]
dist = [N] * (N + 1)
dist[i] = 0
q = deque([i])
while q:
now = q.popleft()
for city in edge[now]:
if dist[city] > dist[now] + 1:
dist[city] = dist[now] + 1
value[city] = value[now] + A[city]
q.append(city)
elif dist[city] == dist[now] + 1:
value[city] = max(value[city], value[now] + A[city])
ans[i] = *zip(dist, value),
for u, v in UV:
if ans[u][v][0] == N:
print("Impossible")
else:
print(*ans[u][v])test_all(E)
AtCoder Inc.
