Спасибо всем за участие!
1979A - Guess the Maximum
Пусть $$$m$$$ — максимум среди чисел $$$a_i, a_{i + 1},\ldots, a_j$$$. Заметим, что всегда существует такое $$$k$$$, что $$$i \le k < j$$$ и $$$a_k = m$$$ или $$$a_{k + 1} = m$$$. Следовательно, можно считать, что Боб всегда выбирает в качестве $$$i$$$ и $$$j$$$ пару чисел $$$p$$$ и $$$p + 1$$$ ($$$1 \le p < n$$$).
Не сложно понять, что достаточно рассмотреть максимумы в парах соседних элементов и взять среди них минимум. Пусть $$$min$$$ — найденный минимум, тогда очевидно, что ответ равен $$$min - 1$$$.
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n];
for (int& i : a) {
cin >> i;
}
int mini = max(a[0], a[1]);
for (int i = 1; i < n - 1; i++) {
mini = min(mini, max(a[i], a[i + 1]));
}
cout << mini - 1 << "\n";
}
}
1979B - XOR Sequences
Посмотрите на примеры.
Пусть существуют такие два числа $$$v$$$ и $$$u$$$, что $$$x \oplus v = y \oplus u$$$. Тогда рассмотрим числа $$$x \oplus (v + 1)$$$ и $$$y \oplus (u + 1)$$$. В частности, посмотрим на последний бит $$$v$$$ и $$$u$$$. Возможные варианты:
- Оба бита равны $$$0$$$ — прибавление единицы изменит биты на одинаковых позициях, следовательно $$$x \oplus (v + 1) = y \oplus (u + 1)$$$;
- Оба бита равны $$$1$$$ — прибавление единицы изменит биты на одинаковых позициях, а также прибавит единицу в следующий разряд, следовательно можно аналогично рассмотреть следующий бит;
- Биты различаются — прибавление единицы к нулевому биту изменит только его, в то время как у другого числа поменяются послестоящие биты. Значит, $$$x \oplus (v + 1) \neq y \oplus (u + 1)$$$.
Отсюда понятно, что нужно максимизировать количество нулей в максимальном совпадающем суффиксе $$$u$$$ и $$$v$$$. Очевидно, что это количество равно максимальному совпадающему суффиксу $$$x$$$ и $$$y$$$. Пусть $$$k$$$ — длина максимального совпадающего суффикса $$$x$$$ и $$$y$$$, тогда ответ — это $$$2^k$$$.
Получаем асимптотику $$$O(\log C)$$$ на один тестовый случай, где $$$C$$$ — ограничение на $$$x$$$ и $$$y$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
for (int i = 0; i < 30; i++) {
if ((a & (1 << i)) != (b & (1 << i))) {
cout << (1ll << i) << "\n";
break;
}
}
}
}
1979C - Earning on Bets
Попробуйте придумать условие существования ответа.
Пусть $$$S$$$ — суммарное количество монет, поставленных на всевозможные исходы. Тогда, если коэффициент на выигрыш составляет $$$k_i$$$, то на данный исход необходимо поставить больше $$$\frac{S}{k_i}$$$.
Отсюда можно получить следующее неравенство:
Поделив обе части на $$$S$$$, мы получаем необходимое и достаточное условие на существование ответа:
Данную проверку можно выполнить, приведя все дроби к одному знаменателю. Можно заметить, что числители приведенных дробей соответствуют требуемым ставкам на исходы.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b) {
while (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
void solve() {
int n;
cin >> n;
vector <int> k(n);
for (int i = 0; i < n; i++) {
cin >> k[i];
}
int z = 1;
for (int i = 0; i < n; i++) {
z = lcm(z, k[i]);
}
int suma = 0;
for (int i = 0; i < n; i++) {
suma += z / k[i];
}
if (suma < z) {
for (int i = 0; i < n; i++) {
cout << z / k[i] << " ";
}
cout << "\n";
} else {
cout << -1 << "\n";
}
}
signed main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1979D - Fixing a Binary String
Рассмотрим блок символов на конце. Заметим, что их количество не может уменьшиться. Обозначим за $$$x$$$ количество одинаковых символов на конце; возможны три случая:
- $$$x = k$$$ — достаточно найти любой блок длины больше $$$k$$$ и отделить от него блок длины $$$k$$$;
- $$$x > k$$$ — очевидно, решения не существует;
- $$$x < k$$$ — нужно найти блок длины $$$k - x$$$ или $$$2k - x$$$ и отделить от него блок длины $$$k - x$$$.
Данное решение работает за $$$O(n)$$$, но не является единственным верным. Ваше решение может сильно отличаться от предложенного.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
string s;
cin >> s;
int x = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == s[n - 1]) {
x++;
} else {
break;
}
}
auto check = [&]() {
for (int i = 0; i < k; i++) {
if (s[i] != s[0]) return false;
}
for (int i = 0; i + k < n; i++) {
if (s[i] == s[i + k]) return false;
}
return true;
};
auto operation = [&](int p) {
reverse(s.begin(), s.begin() + p);
s = s.substr(p, (int)s.size() - p) + s.substr(0, p);
if (check()) {
cout << p << "\n";
} else {
cout << -1 << "\n";
}
};
if (x == k) {
int p = n;
for (int i = n - 1 - k; i >= 0; i--) {
if (s[i] == s[i + k]) {
p = i + 1;
break;
}
}
operation(p);
} else if (x > k) {
cout << -1 << "\n";
} else {
bool was = false;
for (int i = 0; i < n; i++) {
if (s[i] != s.back()) continue;
int j = i;
while (j + 1 < n && s[i] == s[j + 1]) {
j++;
}
if (j - i + 1 + x == k) {
operation(j + 1);
was = true;
break;
} else if (j - i + 1 - k + x == k) {
operation(i + k - x);
was = true;
break;
}
i = j;
}
if (!was) {
operation(n);
}
}
}
}
1979E - Manhattan Triangle
В каждом манхэттенском треугольнике существуют две точки такие, что $$$|x_1 - x_2| = |y_1 - y_2|$$$.
Заметим следующий факт: в каждом манхэттенском треугольнике существуют две точки такие, что $$$|x_1 - x_2| = |y_1 - y_2|$$$.
Давайте начнем с распределения всех точек по их значениям $$$(x + y)$$$.
Для каждой точки $$$(x; y)$$$ найдем точку $$$(x + d / 2; y - d / 2)$$$ с помощью бинарного поиска в соответствующем сете. Затем нам нужно найти третью точку: она может находиться на диагонали $$$(x + y + d)$$$ или $$$(x + y - d)$$$. Границы по координате $$$x$$$ для них равны $$$[x + d / 2; x + d]$$$ и $$$[x - d / 2; x]$$$ — это можно найти с использованием того же метода.
Затем распределите все точки по значениям $$$(x - y)$$$ и выполните тот же алгоритм.
Общая асимптотика составляет $$$O(n \log n)$$$.
#include <bits/stdc++.h>
using namespace std;
const int MAXC = 1e5;
const int MAXD = 4e5 + 10;
set <pair <int, int>> diag[MAXD];
void solve() {
int n, d;
cin >> n >> d;
vector <int> x(n), y(n);
for (int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
x[i] += MAXC;
y[i] += MAXC;
}
bool found = false;
{
for (int i = 0; i < n; i++) {
diag[x[i] + y[i]].insert({x[i], i});
}
for (int i = 0; i < n; i++) {
auto it1 = diag[x[i] + y[i]].lower_bound({x[i] + d / 2, -1});
if (it1 == diag[x[i] + y[i]].end() || it1->first != x[i] + d / 2) continue;
if (x[i] + y[i] + d < MAXD) {
auto it2 = diag[x[i] + y[i] + d].lower_bound({x[i] + d / 2, -1});
if (it2 != diag[x[i] + y[i] + d].end() && it2->first <= it1->first + d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
if (x[i] + y[i] - d >= 0) {
auto it2 = diag[x[i] + y[i] - d].lower_bound({x[i] - d / 2, -1});
if (it2 != diag[x[i] + y[i] - d].end() && it2->first <= it1->first - d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
diag[x[i] + y[i]].erase({x[i], i});
}
}
if (!found) {
for (int i = 0; i < n; i++) {
y[i] -= 2 * MAXC;
diag[x[i] - y[i]].insert({x[i], i});
}
for (int i = 0; i < n; i++) {
auto it1 = diag[x[i] - y[i]].lower_bound({x[i] + d / 2, -1});
if (it1 == diag[x[i] - y[i]].end() || it1->first != x[i] + d / 2) continue;
if (x[i] - y[i] + d < MAXD) {
auto it2 = diag[x[i] - y[i] + d].lower_bound({x[i] + d / 2, -1});
if (it2 != diag[x[i] - y[i] + d].end() && it2->first <= it1->first + d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
if (x[i] - y[i] - d >= 0) {
auto it2 = diag[x[i] - y[i] - d].lower_bound({x[i] - d / 2, -1});
if (it2 != diag[x[i] - y[i] - d].end() && it2->first <= it1->first - d / 2) {
cout << i + 1 << " " << it1->second + 1 << " " << it2->second + 1 << "\n";
found = true;
break;
}
}
}
for (int i = 0; i < n; i++) {
diag[x[i] - y[i]].erase({x[i], i});
}
}
if (!found) {
cout << "0 0 0\n";
}
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
1979F - Kostyanych's Theorem
Давайте рассмотрим следующий рекурсивный алгоритм. Будем хранить гамильтонов путь в виде двусвязного списка, поддерживая начало и конец.
В случае, если в графе осталось $$$1$$$ или $$$2$$$ вершины, задача решается тривиально.
Пусть нам известно, что в текущем графе $$$n$$$ вершин, и отсутствует не более $$$(n - 2)$$$ ребер. Тогда общее количество ребер в таком графе не меньше
Пусть в графе все вершины имеют степень хотя бы $$$(n - 3)$$$, тогда общее количество ребер не превосходит
что меньше заявленного значения. Отсюда делаем вывод, что существует хотя бы одна вершина со степенью большей $$$(n - 3)$$$.
Если существует вершина $$$v$$$ со степенью $$$(n - 2)$$$, то достаточно запустить наш рекурсивный алгоритм для оставшегося графа. Так как $$$v$$$ не соединена ребром только с одной вершиной, то $$$v$$$ соединена или с началом поддерживаемого пути в оставшемся графе, или с концом. Таким образом, можно вставить вершину $$$v$$$ или в начало, или в конец пути.
Иначе, обозначим за $$$u$$$ вершину со степенью $$$(n - 1)$$$. Легко понять, что существует хотя бы одна вершина $$$w$$$ со степенью не превышающей $$$(n - 3)$$$. Удалим $$$u$$$ и $$$w$$$ из графа. Заметим, что количество ребер в таком графе не превосходит
Инвариант сохранился, поэтому мы можем запустить алгоритм для оставшегося графа. Затем, можно расставить вершины в следующем порядке: $$$w$$$ — $$$u$$$ — $$$s$$$ — ..., где $$$s$$$ — начало гамильтонова пути в оставшемся графе.
Осталось понять, каким образом использовать запросы.
Сделаем запрос $$$d = (n - 2)$$$. Обозначим за $$$u$$$ второе число в ответе на наш запрос. В случае, если $$$u \neq 0$$$, степень вершины $$$v$$$ равна $$$(n - 2)$$$. Запустим наш рекурсивный алгоритм, а затем сравним начало и конец полученного пути с $$$u$$$.
Иначе, если $$$u = 0$$$, значит степень вершины $$$v$$$ равна $$$(n - 1)$$$. В таком случае достаточно спросить про любую вершину с маленькой степенью (это можно сделать запросом $$$d = 0$$$). Далее достаточно расположить вершины в порядке, указанном выше.
Таким образом мы сделаем не больше $$$n$$$ запросов, и итоговая асимптотика будет $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
pair <int, int> ask(int d) {
cout << "? " << d << endl;
int v, u;
cin >> v >> u;
return {v, u};
}
pair <int, int> get(int n, vector <int>& nxt) {
if (n == 1) {
int v = ask(0).first;
return {v, v};
}
if (n == 2) {
int u = ask(0).first;
int v = ask(0).first;
nxt[u] = v;
return {u, v};
}
pair <int, int> t = ask(n - 2);
int v = t.first;
int ban = t.second;
if (ban != 0) {
pair <int, int> res = get(n - 1, nxt);
if (ban != res.first) {
nxt[v] = res.first;
return {v, res.second};
} else {
nxt[res.second] = v;
return {res.first, v};
}
} else {
int u = ask(0).first;
nxt[u] = v;
pair <int, int> res = get(n - 2, nxt);
nxt[v] = res.first;
return {u, res.second};
}
}
void solve() {
int n;
cin >> n;
vector <int> nxt(n + 1, -1);
pair <int, int> ans = get(n, nxt);
int v = ans.first;
cout << "! ";
do {
cout << v << " ";
v = nxt[v];
} while (v != -1);
cout << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}