Всем спасибо за участие, надеюсь вам понравились задачи! Вы можете оценить задачи раунда в соответствующих спойлерах под разбором.
Подсказка 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...
Решение
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...
Решение
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...
Решение
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)
1798D - Шокирующая расстановка
Подсказка 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...
Решение
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))))
1798E - Генератор мультитестов
Подсказка 1
Найдите оценку сверху на количество изменений за которое можно сделать мультитест из произвольного массива.
Подсказка 2
Как для каждого суффикса проверить является ли он мультитестом сам по себе (без изменений)?
Подсказка 2.1
Это делается при помощи одномерного динамического программирования по суффиксам.
Подсказка 3
Допустим вы хотите проверить, может ли массив превратиться в мультитест за $$$1$$$ изменение. Найдите все элементы которые потенциально могли быть изменены (все элементы такие, что их изменение могло привести к тому, что массив стал мультитестом не будучи им изначально). Для каждого из них нужно определить, возможно ли сделать изменение превращающее массив в мультитест. Учесть все эти варианты изменения снова поможет динамика по суффиксам.
Разбор
Tutorial is loading...
Решение
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)
1798F - Подарки от Деда Ахмеда
Подсказка 1
Допустим выбранная вами коробка будет отправлена в наибольший по вместимости класс. Тогда если этот класс имеет размер $$$s$$$, вы можете отправить туда любые $$$s-1$$$ из имеющихся коробок. Значит вы можете не беспокоиться об этом классе, и набирать коробки для остальных, всегда имея в качестве потенциальных опций $$$s-1$$$ дополнительную коробку. Это большое пространство для манёвра.
Подсказка 2
Решение существует при любых входных данных
Подсказка 3
Зная о Подсказке 2 подумайте про специфичные входные данные. Вы знаете, что решение для них всегда существует. Это должно вдохновить.
Подсказка 3.1
$$$k = 2, s_1 = s_2$$$.
Подсказка 4
Erdős--Ginzburg--Ziv theorem
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define pb push_back
// #define int long long
#define all(x) x.begin(), x.end()
#define ld long double
using namespace std;
const int N = 210;
bool dp[N][N][N];
bool take[N][N][N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, k;
cin >> n >> k;
vector<int> a(n), s(k);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < k; i++) {
cin >> s[i];
}
vector<pair<int, int>> s2;
for (int i = 0; i < k; i++) {
s2.pb({s[i], i});
}
sort(all(s2));
vector<vector<int>> ans(k);
for (int i = 0; i < k - 1; i++) {
int class_size = s2[i].first;
vector<int> boxes;
for (int _ = 0; _ < 2 * class_size - 1; _++) {
boxes.pb(a.back());
a.pop_back();
}
for (int sz = 0; sz <= class_size; sz++) {
for (int r = 0; r < class_size; r++) {
dp[0][sz][r] = false;
take[0][sz][r] = false;
}
}
dp[0][0][0] = true;
dp[0][1][boxes[0] % class_size] = true;
take[0][1][boxes[0] % class_size] = true;
for (int j = 1; j < (int) boxes.size(); j++) {
for (int sz = 0; sz <= class_size; sz++) {
for (int r = 0; r < class_size; r++) {
dp[j][sz][r] = dp[j - 1][sz][r];
if (sz > 0 && dp[j - 1][sz - 1][(class_size + r - boxes[j] % class_size) % class_size]) {
dp[j][sz][r] = true;
take[j][sz][r] = true;
} else {
take[j][sz][r] = false;
}
}
}
}
vector<bool> used(2 * class_size - 1);
int sz = class_size, r = 0;
for (int j = (int) boxes.size() - 1; j >= 0; j--) {
if (take[j][sz][r]) {
used[j] = true;
sz--;
r += (class_size - boxes[j] % class_size);
r %= class_size;
} else {
used[j] = false;
}
}
vector<int> to_class;
for (int j = 0; j < (int) boxes.size(); j++) {
if (!used[j]) {
a.pb(boxes[j]);
} else {
to_class.pb(boxes[j]);
}
}
ans[s2[i].second] = to_class;
}
int sum = 0;
for (auto x : a) {
sum += x;
sum %= (int) (a.size() + 1);
}
int add = (int) (a.size() + 1) - sum;
ans[s2[k - 1].second] = a;
ans[s2[k - 1].second].pb(add);
cout << add << '\n';
for (auto arr : ans) {
for (auto x : arr) {
cout << x << ' ';
}
cout << '\n';
}
}