Всем спасибо за участие, надеюсь вам понравились задачи! Вы можете оценить задачи раунда в соответствующих спойлерах под разбором. Если вы хотите высказать мнение про задачи, напишите комментарий, любой фидбэк будет очень полезен, спасибо!
Подсказка 1
Для каждого индекса $$$i$$$ нет смысла проводить операцию $$$\ge 2$$$ раз, так как применение операции с одним индексом дважды ничего не меняет.
Подсказка 2
Условие $$$a_n = \max(a_1, a_2, \ldots, a_n)$$$ равносильно тому, что $$$a_i \leq a_n$$$ для всех $$$i$$$. Значит на каждый индекс $$$i$$$ наложено всего 2 условия: $$$a_i \leq a_n$$$ и $$$b_i \leq b_n$$$.
Разбор
Tutorial is loading...
Решение
[submission:]
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(n):
if a[i] > b[i]:
a[i], b[i] = b[i], a[i]
if a[-1] == max(a) and b[-1] == max(b):
print("YES")
else:
print("NO")
Подсказка 1
Пусть участник с номером $$$X$$$ участвовал в лотерее в днях $$$i_1 < i_2 < \ldots < i_k$$$. В какие дни участник $$$X$$$ мог бы быть выбран победителем, чтобы не нарушить условия?
Подсказка 2
Если в день $$$i$$$ есть несколько кандидатов на победителя лотереи (не участвовавшие в дни с $$$i+1$$$ по $$$m$$$), имеет ли значение кого именно из них мы выберем?
Разбор
Tutorial is loading...
Решение
[submission:]
MAX = 50000
last = [0] * (MAX + 777)
for _ in range(int(input())):
m = int(input())
a_ = []
for day in range(m):
n = int(input())
a = list(map(int, input().split()))
for x in a:
last[x] = day
a_.append(a)
ans = [-1] * m
for day in range(m):
for x in a_[day]:
if last[x] == day:
ans[day] = x
if ans[day] == -1:
print(-1)
break
else:
print(*ans)
Подсказка 1
В каком случае можно обойтись 1 ценником?
Подсказка 1.1
Для любых положительных целых чисел $$$x, y, z$$$ утверждение <<$$$x$$$ делится на $$$y$$$>> равносильно утверждению <<$$$xz$$$ делится на $$$yz$$$>>
Подсказка 1.2
Обозначим итоговую стоимость всех пачек товаров за $$$cost$$$. Перепишите все условия данные в задаче так, чтобы они стали условиями только на число $$$cost$$$. Подсказка 1.1 поможет в этом.
Подсказка 2
Если для какого-то набора конфет будет достаточно одного ценника, то если убрать из этого набора любой тип конфет одного ценника будет все ещё достаточно. Это повод задуматься о жадности.
Разбор
Tutorial is loading...
Решение
[submission:]
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
for _ in range(int(input())):
n = int(input())
a = []
b = []
for i in range(n):
ai, bi = map(int, input().split())
a.append(ai)
b.append(bi)
g = 0
l = 1
ans = 1
for i in range(n):
g = gcd(g, a[i] * b[i])
l = lcm(l, b[i])
if g % l:
ans += 1
g = a[i] * b[i]
l = b[i]
print(ans)
Подсказка 1
Выразите $$$\max\limits_{1 \leq l \leq r \leq n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert$$$ более простым образом.
Подсказка 1.1
Используйте префиксные суммы массива $$$a$$$.
Подсказка 2
Стройте ответ начиная с пустого массива. Если добавлять числа в ответ так, чтобы префиксная сумма всегда находилась в полуинтервале $$$(\min(a), \max(a)]$$$, итоговый массив подойдёт под условие. Как это делать? Помните, что сумма массива равна $$$0$$$.
Разбор
Tutorial is loading...
Решение
[submission:]
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if max(a) == 0:
print("No")
else:
print("Yes")
prefix_sum = 0
pos = []
neg = []
for x in a:
if x >= 0:
pos.append(x)
else:
neg.append(x)
ans = []
for _ in range(n):
if prefix_sum <= 0:
ans.append(pos[-1])
pos.pop()
else:
ans.append(neg[-1])
neg.pop()
prefix_sum += ans[-1]
print(' '.join(list(map(str, ans))))
Подсказка 1
Найдите оценку сверху на количество изменений за которое можно сделать мультитест из произвольного массива.
Подсказка 2
Как для каждого суффикса проверить является ли он мультитестом сам по себе (без изменений)?
Подсказка 2.1
Это делается при помощи одномерного динамического программирования по суффиксам.
Подсказка 3
Допустим вы хотите проверить, может ли массив превратиться в мультитест за $$$1$$$ изменение. Найдите все элементы которые потенциально могли быть изменены (все элементы такие, что их изменение могло привести к тому, что массив стал мультитестом не будучи им изначально). Для каждого из них нужно определить, возможно ли сделать изменение превращающее массив в мультитест. Учесть все эти варианты изменения снова поможет динамика по суффиксам.
Разбор
Tutorial is loading...
Решение
[submission:]
N = 300777
a = [0] * N
go = [0] * N
good_chain = [0] * N
chain_depth = [0] * N
suf_max_chain_depth = [0] * N
ans = ""
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split()))
chain_depth[n + 1] = 0
suf_max_chain_depth[n + 1] = 0
curr_max_chain_depth = 0
for i in range(n, 0, -1):
go[i] = i + a[i] + 1
if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]):
good_chain[i] = True
else:
good_chain[i] = False
chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)]
suf_max_chain_depth[i] = 1 + curr_max_chain_depth
if go[i] <= n + 1:
suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]])
if good_chain[i]:
curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i])
for i in range(1, n):
if good_chain[i + 1] and chain_depth[i + 1] == a[i]:
ans += "0 "
elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]:
ans += "1 "
else:
ans += "2 "
ans += '\n'
print(ans)
