Спасибо за участие, надеемся, что вам понравились задачи! Также мы просим вас оценить каждую из задач раунда в соответствующем спойлере, чтобы улучшить качество будущих соревнований.
Все задачи были подготовлены Alexdat2000 при помощи соавторов.
1634A - Разворачивай и конкатенируй
Идея: sevlll777
Подсказка 1
Каким свойством будет обладать строка после первой операции (независимо от типа операции)?
Подсказка 2
Что произойдет, если применить операцию к палиндрому?
Разбор
Tutorial is loading...
Решение
q = int(input())
for _ in range(q):
n, k = map(int, input().split())
s = input()
if s == s[::-1] or k == 0:
print(1)
else:
print(2)
1634B - Гадание на массиве
Идея: crazyilian и antontrygubO_o
Подсказка 1
Попробуйте решить задачу <<У кого из друзей никакими операциями не может получиться число $$$y$$$>>. Тогда ответом на исходную задачу будет другой человек, так как жюри гарантирует что ровно у одного из друзей это могло получиться.
Подсказка 2
Что общего у чисел $$$a \oplus b$$$ и $$$a + b$$$, для любых чисел $$$a,b$$$?
Подсказка 3
Что общего у всех чисел, которые можно получить применением всех операций начиная с числа $$$x$$$? Пересекается ли множество этих чисел с множеством тех чисел, которые можно получить начиная с $$$x + 3$$$?
Разбор
Tutorial is loading...
Решение
def main():
n, x, y = map(int, input().split())
a = list(map(int, input().split()))
if (sum(a) + x + y) % 2 == 0:
print('Alice')
else:
print('Bob')
for _ in range(int(input())):
main()
1634C - ОКЕЯ
Идея: sevlll777
Подсказка 1
Если $$$k > 1$$$, для каких $$$n$$$ нет решения?
Подсказка 1.1
Для каких $$$n$$$ нет решения при $$$k = 2$$$? Верно ли это для других $$$k > 1$$$?
Подсказка 2
Заметьте, что массив вида $$$[1, 3, 5, 7, 9, …]$$$ будет подходить под условие (среднее арифметическое каждого подотрезка целое число), так как сумма первых $$$X$$$ элементов этого массива это $$$X^2$$$. Попробуйте обобщить этот случай и найти другие массивы подходящие под условие.
Разбор
Tutorial is loading...
Решение
def solve():
n, k = map(int, input().split())
if k == 1:
print("YES")
for i in range(1, n + 1):
print(i)
return
if n % 2 == 1:
print("NO")
return
print("YES")
for i in range(1, n + 1):
print(*[i for i in range(i, n * k + 1, n)])
for _ in range(int(input())):
solve()
1634D - В поисках нуля
Идея: sevlll777
Подсказка 1
Задачу можно переформулировать как “Найдите $$$n - 2$$$ индекса, в которых точно не может быть нуля”.
Подсказка 2
Решите задачу для $$$n = 4$$$.
Подсказка 2.1
Обозначим как $$$f(i)$$$ — ответ на запрос для трех индексов отличных от $$$i$$$. Как зная $$$f(1)$$$, $$$f(2)$$$, $$$f(3)$$$, $$$f(4)$$$ понять, в каких двух индексах точно не может быть нуля? Обратите внимание, что ноль в массиве ровно один.
Подсказка 3
Решите задачу для чётных $$$n$$$, используя решение для $$$n = 4$$$.
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
using namespace std;
int get(const vector <int>& x) {
cout << "? " << x[0] + 1 << " " << x[1] + 1 << " " << x[2] + 1 << endl;
int ans;
cin >> ans;
return ans;
}
signed main() {
ios_base::sync_with_stdio();
cin.tie(nullptr);
int n;
cin >> n;
pair <int, int> possible = {0, 1};
for (int i = 2; i < n - 1; i += 2) {
vector <pair <int, int>> ch(4);
vector <int> now = {possible.first, possible.second, i, i + 1};
for (int j = 0; j < 4; j++) {
vector <int> x = now;
x.erase(x.begin() + j);
ch[j] = {get(x), now[j]};
}
sort(all(ch));
possible = {ch[0].second, ch[1].second};
}
if (n % 2 == 1) {
int other = 0;
while (possible.first == other || possible.second == other) {
other++;
}
vector <pair <int, int>> ch(4);
vector <int> now = {possible.first, possible.second, n - 1, other};
for (int j = 0; j < 4; j++) {
vector <int> x = now;
x.erase(x.begin() + j);
ch[j] = {get(x), now[j]};
}
sort(all(ch));
possible = {ch[0].second, ch[1].second};
}
cout << "! " << possible.first + 1 << " " << possible.second + 1 << endl;
return 0;
}
1634E - Честный делёж
Идея: sevlll777
Подсказка 1
В каких случаях ответ точно NO?
Подсказка 2
Длины всех массивов четные числа, а также каждое число суммарно встречается четное число раз. Подозрительно много четных чисел…
Подсказка 3
Эйлеров цикл — цикл, обходящий все ребра графа по одному разу. Оказывается, эйлеров цикл существует только у тех графов, у которых степень каждой вершины чётная.
Подсказка 4
Сконструируйте некий граф, такой что степень каждой его вершины четная, найдите у него эйлеров цикл, и восстановите ответ на задачу используя этот цикл. Чему тогда соответствуют ребра графа?
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define len(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define endl "\n"
using namespace std;
const int N = 4e5 + 100, H = 2e5 + 50;
vector <pair <int, int>> g[N];
string ans[N];
int pos[N];
void dfs(int v) {
if (pos[v] == 0) {
ans[v] = string(len(g[v]), 'L');
}
while (pos[v] < len(g[v])) {
auto [i, ind] = g[v][pos[v]];
if (i == -1) {
pos[v]++;
continue;
}
g[i][ind].first = -1, g[v][pos[v]].first = -1;
if (v < H) {
ans[v][pos[v]] = 'R';
}
pos[v]++;
dfs(i);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin >> m;
map <int, int> ind, cnt;
int fre_ind = 0;
vector <vector <int>> nums(m);
for (int i = 0; i < m; i++) {
int n;
cin >> n;
for (int _ = 0; _ < n; _++) {
int x;
cin >> x;
if (!ind.count(x)) {
ind[x] = fre_ind++;
}
x = ind[x];
cnt[x]++;
nums[i].push_back(x);
g[i].emplace_back(x + H, len(g[x + H]));
g[x + H].emplace_back(i, len(g[i]) - 1);
}
}
for (auto [num, cn] : cnt) {
if (cn % 2 == 1) {
cout << "NO" << endl;
return 0;
}
}
for (int i = 0; i < N; i++) {
dfs(i);
}
cout << "YES" << endl;
for (int i = 0; i < m; i++) {
cout << ans[i] << endl;
}
return 0;
}
1634F - Прибавления Фибоначчи
Идея: Mangooste
Подсказка 1
Пусть массив $$$C_i = A_i - B_i$$$. Выполняйте все операции на массиве $$$C_i$$$.
Подсказка 2
Предположим, вам нужно прибавлять не числа Фибоначчи, а некое любое число $$$x$$$ на весь отрезок. Можете ли вы решить задачу в таком случае без использования тяжелых структур, таких как дерево отрезков?
Подсказка 3
Обобщите идею из подсказки 2, используя главное свойство чисел Фибоначчи ($$$F_i = F_{i-1} + F_{i-2}$$$).
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define len(x) (int) (x).size()
#define endl "\n"
#define int long long
using namespace std;
const int N = 3e5 + 100;
int MOD;
int fib[N];
vector <int> unfib;
int notzero = 0;
void upd(int ind, int delta) {
notzero -= (unfib[ind] != 0);
unfib[ind] += delta;
if (unfib[ind] >= MOD) {
unfib[ind] -= MOD;
};
notzero += (unfib[ind] != 0);
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, q;
cin >> n >> q >> MOD;
fib[0] = fib[1] = 1;
for (int i = 2; i < N; i++) {
fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}
vector <int> delta(n);
for (int& i : delta) {
cin >> i;
}
for (int i = 0; i < n; i++) {
int x;
cin >> x;
delta[i] = (delta[i] - x + MOD) % MOD;
}
unfib.resize(n);
unfib[0] = delta[0];
if (len(unfib) >= 2) {
unfib[1] = (delta[1] - delta[0] + MOD) % MOD;
}
for (int i = 2; i < n; i++) {
unfib[i] = ((long long) delta[i] - delta[i - 1] - delta[i - 2] + MOD * 2) % MOD;
}
for (int i = 0; i < n; i++) {
notzero += (unfib[i] != 0);
}
while (q--) {
char c;
int l, r;
cin >> c >> l >> r;
if (c == 'A') {
upd(l - 1, 1);
if (r != n) {
upd(r, MOD - fib[r - l + 1]);
}
if (r < n - 1) {
upd(r + 1, MOD - fib[r - l]);
}
} else {
upd(l - 1, MOD - 1);
if (r != n) {
upd(r, fib[r - l + 1]);
}
if (r < n - 1) {
upd(r + 1, fib[r - l]);
}
}
if (!notzero) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}