Идея: Aksenov239
Разбор
Tutorial is loading...
Решение
nt = int(input())
for t in range(nt):
line = input()
x, y = [int(q) for q in line.split()]
mm = (y + 1) // 2
x -= (mm * 5 * 3 - y * 2 * 2)
x = max(x, 0)
mm += (x + 5 * 3 - 1) // (5 * 3)
print(mm)
1974B - Симметричное кодирование
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
b = input()
cnt = [0] * 26
for c in b:
cnt[ord(c) - ord('a')] = 1
tmp = ''
for i in range(26):
if cnt[i] > 0:
tmp += chr(ord('a') + i)
a = ''
for c in b:
a += tmp[-1 - tmp.find(c)]
print(a)
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
a = [int(x) for x in input().split()]
cnt = dict()
ans = 0
for i in range(n - 2):
triplet = (a[i], a[i + 1], a[i + 2])
mist = [0] * 3
mist[0] = (0, a[i + 1], a[i + 2])
mist[1] = (a[i], 0, a[i + 2])
mist[2] = (a[i], a[i + 1], 0)
for trip in mist:
ans += cnt.get(trip, 0) - cnt.get(triplet, 0)
cnt[trip] = cnt.get(trip, 0) + 1
cnt[triplet] = cnt.get(triplet, 0) + 1
print(ans)
for i in range(int(input())):
solve()
Идея: MaxBuzz
Разбор
Tutorial is loading...
Решение
inv = {'N':'S', 'S': 'N',
'E': 'W', 'W': 'E'}
def solve():
n = int(input())
s = input()
x, y = 0, 0
for c in s:
if c == 'N':
y += 1
if c == 'S':
y -= 1
if c == 'E':
x += 1
if c == 'W':
x -= 1
if x % 2 == 1 or y % 2 == 1:
print('NO')
return
ans = ['R'] * n
if x == y == 0:
if n == 2:
print('NO')
return
ans[0] = ans[s.find(inv[s[0]])] = 'H'
else:
for i in range(n):
if s[i] == 'N' and y > 0:
y -= 2
ans[i] = 'H'
if s[i] == 'S' and y < 0:
y += 2
ans[i] = 'H'
if s[i] == 'E' and x > 0:
x -= 2
ans[i] = 'H'
if s[i] == 'W' and x < 0:
x += 2
ans[i] = 'H'
print(*ans, sep='')
for _ in range(int(input())):
solve()
1974E - Деньги покупают счастье
Идея: RobinFromTheHood
Разбор
Tutorial is loading...
Решение
T = int(input())
big = float('inf')
for _ in range(T):
m, x = map(int, input().split())
c = []
h = []
for i in range(m):
ci, hi = map(int, input().split())
c.append(ci)
h.append(hi)
mh = sum(h)
dp = [0] + [big] * mh
for i in range(m):
for j in range(mh, h[i]-1, -1):
if dp[j-h[i]] + c[i] <= i*x:
dp[j] = min(dp[j], dp[j-h[i]]+c[i])
for i in range(mh, -1, -1):
if dp[i] != big:
print(i)
break
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
def solve(tc):
a, b, n, m = map(int, input().split())
ver, hor = [], []
for i in range(n):
x, y = map(int, input().split())
ver.append((x, y))
hor.append((y, x))
deleted = set()
hor.sort()
ver.sort()
ans = [0, 0]
u, d = 1, a
l, r = 1, b
hl, hr = 0, n - 1
vl, vr = 0, n - 1
for i in range(m):
c, k = input().split()
k = int(k)
if c == 'U':
u += k
while vl <= vr and ver[vl][0] < u:
if ver[vl] not in deleted:
ans[i % 2] += 1
deleted.add(ver[vl])
vl += 1
if c == 'D':
d -= k
while vl <= vr and ver[vr][0] > d:
if ver[vr] not in deleted:
ans[i % 2] += 1
deleted.add(ver[vr])
vr -= 1
if c == 'L':
l += k
while hl <= hr and hor[hl][0] < l:
if (hor[hl][1], hor[hl][0]) not in deleted:
ans[i % 2] += 1
deleted.add((hor[hl][1], hor[hl][0]))
hl += 1
if c == 'R':
r -= k
while hl <= hr and hor[hr][0] > r:
if (hor[hr][1], hor[hr][0]) not in deleted:
ans[i % 2] += 1
deleted.add((hor[hr][1], hor[hr][0]))
hr -= 1
print(ans[0], ans[1])
t = int(input())
for i in range(1, t + 1):
solve(i)
1974G - Деньги теперь покупают меньше счастья
Идея: RobinFromTheHood, izban, Aksenov239
Разбор
Tutorial is loading...
Решение
from heapq import *
for _ in range(int(input())):
m, x = map(int, input().split())
c = [int(x) for x in input().split()]
budget = 0
Q = []
for i in c:
if budget >= i:
heappush(Q, -i)
budget -= i
elif Q and -Q[0] > i:
budget += -heappop(Q)-i
heappush(Q, -i)
budget += x
print(len(Q))