I finally got some time, so I tried virtual participation in PAST. The result was 64 points, so it was intermediate (60-79 points). There were a lot of subtly annoying problems, and I felt that the coat color was a little different.
Break through in 3 and a half minutes. Check if it is only a number, and if it is OK, convert it to int and output it at double.
S = input()
for i in range(3):
if S[i] not in '0123456789':
print('error')
exit()
print(int(S) * 2)
Break through in 7 minutes. Just compare with the previous value and output.
N = int(input())
A = [int(input()) for _ in range(N)]
prev = A[0]
for i in range(1, N):
if A[i] == prev:
print('stay')
elif A[i] < prev:
print('down %d' % (prev - A[i]))
elif A[i] > prev:
print('up %d' % (A[i] - prev))
prev = A[i]
Break through in 2 minutes. Just sort in descending order and output the third value from the front.
ABCDEF = list(map(int, input().split()))
ABCDEF.sort(reverse=True)
print(ABCDEF[2])
Break through in 11 minutes. Just count the number of appearances in the dictionary, identify 0 and 2 things, and output.
N = int(input())
A = [int(input()) for _ in range(N)]
t = set(A)
if len(t) == N:
print('Correct')
exit()
d = {}
for i in range(N):
if A[i] in d:
d[A[i]] += 1
else:
d[A[i]] = 1
for i in range(1, N + 1):
if i not in d:
x = i
elif d[i] == 2:
y = i
print(y, x)
Breakthrough in 24 minutes. The implementation of follow follow has also added the users who are following the follow that increased during processing, and it took time for input example 1 to not pass. Input example 1 caught it. I think it would have taken longer if they didn't.
N, Q = map(int, input().split())
t = [['N'] * N for _ in range(N)]
for _ in range(Q):
S = input()
if S[0] == '1':
_, a, b = map(int, S.split())
t[a - 1][b - 1] = 'Y'
elif S[0] == '2':
_, a = map(int, S.split())
for i in range(N):
if t[i][a - 1] == 'Y':
t[a - 1][i] = 'Y'
elif S[0] == '3':
_, a = map(int, S.split())
for i in [i for i in range(N) if t[a - 1][i] == 'Y']:
for j in range(N):
if t[i][j] == 'Y' and j != a - 1:
t[a - 1][j] = 'Y'
for i in range(N):
print(''.join(t[i]))
past201912F - DoubleCamelCase Sort
Break through in 7 minutes. There is nothing particularly difficult, just cut out the words, sort them in case, and combine them.
S = input()
t = []
start = -1
for i in range(len(S)):
if S[i].isupper():
if start == -1:
start = i
else:
t.append(S[start:i+1])
start = -1
t.sort(key=str.lower)
print(''.join(t))
It broke through in 20 minutes. I thought I didn't know at first, but when I looked closely, I could go brute force because N ≤ 10. Since there are 3 groups, I couldn't search all bits, and I implemented an int array to carry forward. It wasn't particularly difficult.
N = int(input())
a = [list(map(int, input().split())) for _ in range(N - 1)]
result = -float('inf')
t = [0] * N
for _ in range(3 ** N):
s = 0
for i in range(N):
for j in range(i + 1, N):
if t[i] == t[j]:
s += a[i][j - i - 1]
result = max(result, s)
for i in range(N):
if t[i] < 2:
t[i] += 1
break
t[i] = 0
print(result)
Break through in 44 minutes and a half. Since it is inevitable that TLE will be reflected in the array both set sales and all types sales because of the restrictions, I made a cumulative variable for each and passed it with a policy of matching Tsuji. It took me a long time to notice that ʻodd_min-= a` leaked out.
N = int(input())
C = list(map(int, input().split()))
Q = int(input())
all_min = min(C)
odd_min = min(C[::2])
all_sale = 0
odd_sale = 0
ind_sale = 0
for _ in range(Q):
S = input()
if S[0] == '1':
_, x, a = map(int, S.split())
t = C[x - 1] - all_sale - a
if x % 2 == 1:
t -= odd_sale
if t >= 0:
ind_sale += a
C[x - 1] -= a
all_min = min(all_min, t)
if x % 2 == 1:
odd_min = min(odd_min, t)
elif S[0] == '2':
_, a = map(int, S.split())
if odd_min >= a:
odd_sale += a
odd_min -= a
all_min = min(odd_min, all_min)
elif S[0] == '3':
_, a = map(int, S.split())
if all_min >= a:
all_sale += a
all_min -= a
odd_min -= a
print(all_sale * N + odd_sale * ((N + 1) // 2) + ind_sale)
It breaks through in 14 minutes. It's DP, so it's not particularly difficult. Just convert Y to 1 and N to 0, which is regarded as a bit of each digit, and then DP.
N, M = map(int, input().split())
def conv(S):
result = 0
for c in S:
result *= 2
if c == 'Y':
result += 1
return result
dp = [-1] * 2001
dp[0] = 0
for _ in range(M):
S, C = input().split()
S = conv(S)
C = int(C)
for i in range(2000, -1, -1):
if dp[i] == -1:
continue
if dp[i | S] == -1 or dp[i | S] > dp[i] + C:
dp[i | S] = dp[i] + C
print(dp[(1 << N) - 1])
I couldn't break through. Find the cheapest route from the lower left to the lower right with DP, rewrite the backtracked place to cost 0, find the cheapest route from lower right to upper right with DP, and the cost for each I tried to make an implementation that sums up, but about half WA.
Postscript: Solved as explained.
from heapq import heappop, heappush
INF = float('inf')
def cost_from(H, W, A, y0, x0):
dp = [[INF] * W for _ in range(H)]
dp[y0][x0] = 0
q = [(0, y0, x0)]
while q:
c, y, x = heappop(q)
t = dp[y][x]
if t != c:
continue
if y - 1 >= 0:
u = t + A[y - 1][x]
if dp[y - 1][x] > u:
dp[y - 1][x] = u
heappush(q, (u, y - 1, x))
if y + 1 < H:
u = t + A[y + 1][x]
if dp[y + 1][x] > u:
dp[y + 1][x] = t + A[y + 1][x]
heappush(q, (u, y + 1, x))
if x - 1 >= 0:
u = t + A[y][x - 1]
if dp[y][x - 1] > u:
dp[y][x - 1] = u
heappush(q, (u, y, x - 1))
if x + 1 < W:
u = t + A[y][x + 1]
if dp[y][x + 1] > u:
dp[y][x + 1] = u
heappush(q, (u, y, x + 1))
return dp
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
result = INF
cost1 = cost_from(H, W, A, H - 1, 0)
cost2 = cost_from(H, W, A, H - 1, W - 1)
cost3 = cost_from(H, W, A, 0, W - 1)
for i in range(H):
for j in range(W):
t = cost1[i][j] + cost2[i][j] + cost3[i][j] - 2 * A[i][j]
if t < result:
result = t
print(result)
I can't break through. Of course I can write a naive implementation, but I can't think of any way to reduce the amount of calculation.
Postscript: I learned Euler tour and AC.
N = int(input())
root = -1
children = [[] for _ in range(N + 1)]
left = [0] * (N + 1)
right = [0] * (N + 1)
for i in range(1, N + 1):
p = int(input())
if p == -1:
root = i
else:
children[p].append(i)
i = 0
s = [root]
while s:
n = s.pop()
if n > 0:
left[n] = i
i += 1
s.append(-n)
for c in children[n]:
s.append(c)
else:
right[-n] = i
Q = int(input())
result = []
for _ in range(Q):
a, b = map(int, input().split())
if left[b] < left[a] < right[b]:
result.append('Yes')
else:
result.append('No')
print('\n'.join(result))
I also tried to solve it by doubling.
from math import log
from collections import deque
from sys import stdin
readline = stdin.readline
N = int(readline())
root = -1
children = [[] for _ in range(N + 1)]
parent = [[-1] * (N + 1) for _ in range(18)]
for i in range(1, N + 1):
p = int(readline())
parent[0][i] = p
if p == -1:
root = i
else:
children[p].append(i)
for i in range(1, 18):
parenti1 = parent[i - 1]
parenti = parent[i]
for j in range(1, N + 1):
t = parenti1[j]
if t == -1:
parenti[j] = -1
else:
parenti[j] = parenti1[t]
depth = [-1] * (N + 1)
q = deque([(root, 0)])
while q:
n, d = q.pop()
depth[n] = d
for c in children[n]:
q.append((c, d + 1))
Q = int(input())
result = []
for _ in range(Q):
a, b = map(int, readline().split())
if depth[a] <= depth[b]:
result.append('No')
continue
while depth[a] != depth[b]:
t = int(log(depth[a] - depth[b], 2))
a = parent[t][a]
if a == b:
result.append('Yes')
else:
result.append('No')
print('\n'.join(result))
Recommended Posts