Пусть $$$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";
    }
}

Посмотрите на примеры.

Пусть существуют такие два числа $$$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;
            }
        }
    }
}

Попробуйте придумать условие существования ответа.

Пусть $$$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();
    }
}

Рассмотрим блок символов на конце. Заметим, что их количество не может уменьшиться. Обозначим за $$$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);
            }
        }
    }
}

В каждом манхэттенском треугольнике существуют две точки такие, что $$$|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();
    }
}

Давайте рассмотрим следующий рекурсивный алгоритм. Будем хранить гамильтонов путь в виде двусвязного списка, поддерживая начало и конец.

В случае, если в графе осталось $$$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();
    }
}