Break through in 2 minutes. Just write.
def S(n):
return sum(int(c) for c in str(n))
A, B = map(int, input().split())
print(max(S(A), S(B)))
Break through in 4 and a half minutes. As usual, I started by googled the equation of a straight line passing through two points. I thought it would be bad if I divided it, but it's a B problem and it's safe to read it rotten.
N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
result = 0
for i in range(N):
for j in range(i + 1, N):
x1, y1 = xy[i]
x2, y2 = xy[j]
if x1 == x2:
continue
a = (y2 - y1) / (x2 - x1)
if abs(a) <= 1:
result += 1
print(result)
Postscript: x2 --x1 could not be 0 because of the limitation …….
N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
result = 0
for i in range(N):
x1, y1 = xy[i]
for j in range(i + 1, N):
x2, y2 = xy[j]
if abs(y2 - y1) <= abs(x2 - x1):
result += 1
print(result)
Break through in 5 and a half minutes.After writing without looking at the restrictions, I thought for a moment that it would be impossible to do this, but|Si|Since it was ≤10, it became "Oh, it's okay" and AC.
from sys import stdin
readline = stdin.readline
N = int(readline())
S = [readline()[:-1] for _ in range(N)]
t = set()
for s in S:
if s[0] == '!':
if s[1:] in t:
print(s[1:])
break
t.add(s)
else:
if '!' + s in t:
print(s)
break
t.add(s)
else:
print('satisfiable')
Break through in 13 minutes. I didn't understand at all for a moment, but when I started with "Sum (A i ) vs 0" and gave a speech in the town j , "Sum (A <A <" sub> i ) --A j vs A j + B j ", so if you transfer it to" Sum (A <A < sub> i ) vs 2A j + B j ". So," 2A j + B j I found that I should make a sequence of "", sort it in descending order, and add it in order, and it became * O * ( N log N ). So I solved it with this.
from sys import stdin
readline = stdin.readline
N = int(readline())
AB = [tuple(map(int, readline().split())) for _ in range(N)]
s = sum(a for a, _ in AB)
t = [a * 2 + b for a, b in AB]
t.sort(reverse=True)
c = 0
for i in range(N):
c += t[i]
if c > s:
print(i + 1)
break
I couldn't break through. I was able to solve it by myself in 21 minutes and 20 seconds from the end of the contest (96 minutes and a half). In my brain, apex a e i and apex b < I rewrote the problem that sub> e i was not adjacent and self-destructed. The method of reducing the amount of calculation is the same as ABC138D --Ki and added to the parent node. I thought it would be good to include it and add it up at the end. Considering that it matches Tsuji, if the trace source is the parent, + x to the root vertex, -x to the blocking vertex, and the trace source is the child. In that case, you can + x to the vertex of the trace source. After that, you can decide which one is the parent, traverse from there and put the parent information in the array with * O * (1). It can be processed. It doesn't matter which vertex is rooted, so I calculated with vertex 1 as the root.
from sys import stdin
from collections import deque
readline = stdin.readline
N = int(readline())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(N - 1)]
links = [[] for _ in range(N)]
for a, b in ab:
links[a].append(b)
links[b].append(a)
parent = [-1] * N
parent[0] = 0
q = deque([0])
while q:
i = q.popleft()
for j in links[i]:
if parent[j] != -1:
continue
parent[j] = i
q.append(j)
c = [0] * N
Q = int(readline())
for _ in range(Q):
t, e, x = map(int, readline().split())
a, b = ab[e - 1]
if t == 2:
a, b = b, a
if a == parent[b]:
c[0] += x
c[b] -= x
else:
c[a] += x
q = deque([0])
while q:
i = q.popleft()
for j in links[i]:
if j == parent[i]:
continue
c[j] += c[i]
q.append(j)
print(*c, sep='\n')
Postscript: Many people have depth information instead of parent information.
from sys import stdin
from collections import deque
readline = stdin.readline
N = int(readline())
ab = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(N - 1)]
links = [[] for _ in range(N)]
for a, b in ab:
links[a].append(b)
links[b].append(a)
depth = [-1] * N
depth[0] = 0
q = deque([0])
while q:
i = q.popleft()
for j in links[i]:
if depth[j] != -1:
continue
depth[j] = depth[i] + 1
q.append(j)
c = [0] * N
Q = int(readline())
for _ in range(Q):
t, e, x = map(int, readline().split())
a, b = ab[e - 1]
if t == 2:
a, b = b, a
if depth[a] < depth[b]:
c[0] += x
c[b] -= x
else:
c[a] += x
q = deque([0])
while q:
i = q.popleft()
for j in links[i]:
if depth[j] < depth[i]:
continue
c[j] += c[i]
q.append(j)
print(*c, sep='\n')
Recommended Posts