Заметьте, что $$$(a_i \bmod a_{i + 1}) \lt a_{i + 1}$$$.

$$$a_{i + 2} = (a_i \bmod a_{i + 1}) \lt a_{i + 1}$$$ и $$$a_2 \le a_1$$$ означают, что последовательность $$$a$$$ должна быть невозрастающей. С другой стороны, есть только одна перестановка $$$b$$$, которая может быть невозрастающей.

t = int(input())
for tt in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a = a[::-1]
    valid = True
    for i in range(2, n):
        if a[i] != a[i - 2] % a[i - 1]:
            print(-1)
            valid = False
            break
    if valid:
        print(a[0], a[1])

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    sort(b.rbegin(), b.rend());
    bool ok = true;
    for (int i = 0; i < n - 2; i++) {
        if (b[i + 2] != b[i] % b[i + 1]) {
            ok = false;
            break;
        }
    }
    if (ok) {
        cout << b[0] << " " << b[1] << "\n";
    } else {
        cout << -1 << "\n";
    }
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        solve();
    }
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

tt = int(input())
for tc in range(tt):
    n = int(input())
    if n == 10:
        print(-1)
    elif n % 12 == 10:
        print(22, n - 22)
    else:
        print(n % 12, n - (n % 12))

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    long long n;
    cin >> n;
    if (n == 10) {
        cout << "-1\n";
    } else if (n % 12 == 10) {
        cout << "22 " << n - 22 << "\n";
    } else {
        cout << n % 12 << " " << n - (n % 12) << "\n";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Интуитивно, чем сосуд дальше от пустого, тем больше воды можно в нём уместить. Зафиксируйте пустой сосуд и попробуйте найти формулу в явном виде для максимальной высоты в каждом из оставшихся сосудов.

t = int(input())
for tc in range(t):
    n = int(input())
    h = list(map(int, input().split()))
    ans = []
    for s in range(n):
        w1 = [0] * n
        w2 = [0] * n
        for i in range(1, n):
            w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n])
        for i in range(1, n):
            w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n])
        w = [min(w1[i], w2[i]) for i in range(n)]
        ans.append(sum(w))
    print(*ans)

#include <bits/stdc++.h>

using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    
    for (int s = 0; s < n; s++) {
        vector<int> w1(n), w2(n), w(n);
        for (int i = 1; i < n; i++) {
            w1[(s + i) % n] = max(w1[(s + i - 1) % n], h[(s + i - 1) % n]);
        }
        for (int i = 1; i < n; i++) {
            w2[(s + n - i) % n] = max(w2[(s + n - i + 1) % n], h[(s + n - i) % n]);
        }
        for (int i = 0; i < n; i++) {
            w[i] = min(w1[i], w2[i]);
        }
        cout << accumulate(w.begin(), w.end(), 0ll) << " ";
    }
    cout << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Пусть $$$A = a_1$$$, $$$B = a_{2^k + 1}$$$, $$$C = A \oplus B$$$.

Попробуйте выписать значения $$$a$$$, к примеру, для $$$k = 3$$$.

$$$A \oplus B = C$$$, $$$B \oplus C = A$$$, $$$C \oplus A = B$$$.

Посмотрим, как $$$a$$$ меняется пошагово:

• a = [A, ?, ?, ?, ?, ?, ?, ?, B];
• a = [A, ?, ?, ?, C, ?, ?, ?, B];
• a = [A, ?, B, ?, C, ?, A, ?, B];
• a = [A, C, B, A, C, B, A, C, B].

Попробуйте найти и доказать закономерность.

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    char g;
    for (int i = 0; i < n; ++i) {
        cin >> g;
        a[i] = g - '0';
    }
    for (int i = 0; i < n; ++i) {
        cin >> g;
        b[i] = g - '0';
    }
    vector<int> c(4);
    for (int i = 0; i < n; ++i) {
        int x = 2 * a[i] + b[i];
        c[x]++;
    }
        
    if (k % 2) {
        long long p = 0, q = 0, r = 0;
        p = c[0] + c[1];
        q = c[0] + c[3];
        r = c[0] + c[2];
        cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) << "\n";
    } else {
        long long p = 0, q = 0, r = 0;
        p = c[0] + c[1];
        q = c[0] + c[2];
        r = c[0] + c[3];
        cout << (((1ll << k) + 1) / 3) * (p * (n-p) + q * (n - q) + r * (n - r)) + p * (n - p) + q * (n - q) << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Есть довольно прямолинейное решение за $$$\mathcal{O}(nk \log k)$$$.

Прочитайте первые две подсказки к решению 1. Докажите, что каждое $$$a_i \in [A, B, C]$$$.

Для каждой пары битов $$$(x, y)$$$, посчитайте количество позиций $$$h$$$, для которых $$$h$$$-е биты $$$a_1$$$ и $$$a_{2^k+1}$$$ равны $$$x$$$ и $$$y$$$ соответственно. Продолжайте рекурсивно.

Используйте кэширование.

Пусть ответ на задачу, где $$$a_1 = A$$$, $$$a_{2^k+1} = B$$$ и $$$k = l$$$ — $$$F(l, A, B)$$$.

Тогда, раз мы записываем значение $$$A \oplus B$$$ посередине массива на первом шагу, а затем продолжаем рекурсивно, как для $$$k = l - 1$$$, $$$F(l, A, B) = F(l - 1, A, A \oplus B) + F(l - 1, A \oplus B, B) - [\text{произведение количеств битов } 0 \text{ и } 1 \text{ в } A \oplus B]$$$.

Ссылаясь на доказательство в решении 1, что все $$$a_i \in [A, B, C]$$$, для каждого $$$l$$$ значение функции требуется посчитать для различных пар $$$(A, B)$$$ максимум $$$6$$$ раз, а значит, если мы используем словарь для кэширования ответ $$$F$$$, мы сделаем не более $$$6k$$$ вызовов $$$F$$$, из-за чего асимптотика $$$\mathcal{O}(n + k \log k)$$$.

#include <bits/stdc++.h>

using namespace std;
#define int long long

int n, k, a, b, c;
string p, q, r;

int get(string &s) {
    int a = 0, b = 0;
    for (char c : s)
        if (c == '0') a++;
        else b++;
    return a * b;
}

map<array<int, 4>, int> mp;

int solve(int l, int a, int b, int c) {
    array<int, 4> t = {l, a, b, c};
    if (mp.find(t) == mp.end()) {
        if (l == 0) mp[t] = a + b;
        else mp[t] = solve(l - 1, c, a, b) + solve(l - 1, b, c, a) - c;
    }
    return mp[t];
}

void test_case() {
    cin >> n >> k >> p >> q;
    r.clear();
    for (int i = 0; i < n; i++)
        r.push_back('0' + ((p[i] - '0') ^ (q[i] - '0')));
    a = get(p);
    b = get(q);
    c = get(r);
    mp.clear();
    cout << solve(k, a, b, c) << '\n';
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) test_case();
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Смотря только на массив $$$a$$$, как найти индекс $$$i$$$, для которого $$$p_i = 1$$$, т.е. минимум $$$p$$$?

Попробуйте придумать рекурсивное решение, работающее за $$$\mathcal{O}(n^2)$$$.

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int Mod = 1e9 + 7, Max = 5e5 + 10;

vector<int> fact(Max), ifact(Max);

int binpow(int b, int p) {
    if (p == 0) return 1;
    if (p % 2 == 0) return binpow((b * b) % Mod, p / 2);
    return (binpow(b, p - 1) * b) % Mod;
}

int C(int n, int k) {
    return (fact[n] * ((ifact[k] * ifact[n - k]) % Mod)) % Mod;
}

int rec(int l, int r, vector<int> &b) {
    if (r < l) {
        return 1;
    }
    if (l == r) {
        return (b[l] == 1 ? 1 : 0);
    }
    for (int d = 0; d < r - l + 1; d++) {
        int i = d + l;
        if ((i - l + 1) * (r - i + 1) == b[i]) {
            return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod;
        }
        i = r - d;
        if ((i - l + 1) * (r - i + 1) == b[i]) {
            return (((rec(l, i - 1, b) * rec(i + 1, r, b)) % Mod) * C(r - l, i - l)) % Mod;
        }
    }
    return 0;
}

void solve() {
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];

    int s = accumulate(b.begin(), b.end(), 0ll);
    if (s != n * (n + 1) / 2) {
        cout << "0\n";
        return;
    }

    cout << rec(0, n - 1, b) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    fact[0] = 1;
    for (int i = 1; i < Max; i++) {
        fact[i] = (fact[i - 1] * i) % Mod;
    }
    for (int i = 0; i < Max; i++) {
        ifact[i] = binpow(fact[i], Mod - 2);
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Будет скоро добавлено.

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Прочитайте решение C. Попробуйте посчитать ответ, если пустой сосуд — сосуд $$$1$$$, затем каким-то образом быстро меняйте его, двигая пустой сосуд, чтобы он был сосудом $$$2$$$, $$$3$$$, и т.д.

Рассмотрите самое высокое соединение между сосудами.

Здесь не нужны продвинутые структуры данных. Используйте стек.

INF = float("inf")
 
tt = int(input())
for tc in range(tt):
    n = int(input())
    h = list(map(int, input().split()))
    t = 0
    for i in range(n):
        if h[i] > h[t]:
            t = i
    
    ls = [0 for i in range(n)]
    rs = [0 for i in range(n)]
 
    sm = [(INF, 0)]
    for ti in range(1, n):
        i = (ti + t) % n
        s = ls[i] + h[i]
        c = 1
        while sm[-1][0] <= h[i]:
            s += sm[-1][1] * (h[i] - sm[-1][0])
            c += sm[-1][1]
            sm.pop()
        sm.append((h[i], c))
        ls[(i + 1) % n] = s
    
    sm = [(INF, 0)]
    for ti in range(1, n):
        i = (t + n - ti) % n
        s = rs[(i + 1) % n] + h[i]
        c = 1
        while sm[-1][0] <= h[i]:
            s += sm[-1][1] * (h[i] - sm[-1][0])
            c += sm[-1][1]
            sm.pop()
        sm.append((h[i], c))
        rs[i] = s
    
    ans = [ls[i] + rs[i] for i in range(n)]
    print(*ans)

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
using pii = pair<int, int>;
 
void solve() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    int t = max_element(h.begin(), h.end()) - h.begin();
    
    vector<int> ls(n), rs(n);
 
    stack<pii> sm;
    sm.push({1e18, 0});
    for (int ti = 1; ti < n; ti++) {
        int i = (ti + t) % n;
        int s = ls[i] + h[i], c = 1;
        while (sm.top().first <= h[i]) {
            s += sm.top().second * (h[i] - sm.top().first);
            c += sm.top().second;
            sm.pop();
        }
        sm.push({h[i], c});
        ls[(i + 1) % n] = s;
    }
    
    sm = stack<pii>();
    sm.push({1e18, 0});
    for (int ti = 1; ti < n; ti++) {
        int i = (t + n - ti) % n;
        int s = rs[(i + 1) % n] + h[i], c = 1;
        while (sm.top().first <= h[i]) {
            s += sm.top().second * (h[i] - sm.top().first);
            c += sm.top().second;
            sm.pop();
        }
        sm.push({h[i], c});
        rs[i] = s;
    }
    
    for (int i = 0; i < n; i++) {
        cout << ls[i] + rs[i] << " ";
    }
    cout << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
 
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача

Придумайте решение за $$$\mathcal{O}(n^3)$$$.

ДП. Для каждой пары $$$(cell, strength)$$$ вы можете найти, выигрывает ли игрок, ходящий из этого положения, при оптимальной игре.

В этой игре не очень много проигрышных позиций. Почему?

Проигрышных позиций $$$(i, k)$$$ для фиксированного $$$k$$$ при $$$i \le n$$$ не больше $$$\big\lceil \frac{n}{k + 1} \big\rceil$$$, т.к. если позиция $$$(i, k)$$$ проигрышная, то все позиции $$$(i + 1, k), (i + 2, k), \ldots, (i + k, k)$$$ должны быть выигрышными, если они существуют. Тогда суммарно проигрышных позиций $$$(i, k)$$$ при $$$i \le n$$$ не больше $$$\mathcal{O}(n \log n)$$$.

Попробуйте проитерироваться по номеру клетки $$$i$$$ от $$$n$$$ до $$$1$$$ и в явном виде находить все проигрышные позиции.

Вам нужно придумать структуру данных, которая позволит вам оптимизировать решение до $$$\mathcal{O}(n \log^2 n)$$$.

Будем обозначать состояние игры, где фишка на клетке $$$i$$$ и имеет силу $$$k$$$ до использования вкусняшек как $$$(i, k)$$$. Нам нужно определить, выигрышная ли позиция $$$(1, 1)$$$.

Заметим, что проигрышных позиций $$$(i, k)$$$ для фиксированного $$$k$$$ при $$$i \le n$$$ не больше $$$\big\lceil \frac{n}{k + 1} \big\rceil$$$, т.к. если позиция $$$(i, k)$$$ проигрышная, то все позиции $$$(i + 1, k), (i + 2, k), \ldots, (i + k, k)$$$ должны быть выигрышными, если они существуют. Тогда суммарно проигрышных позиций $$$(i, k)$$$ при $$$i \le n$$$ не больше $$$\mathcal{O}(n \log n)$$$.

Будем итерироваться по номеру клетки $$$i$$$ от $$$n$$$ до $$$1$$$ и в явном виде находить все проигрышные позиции.

Давайте поддерживать множество $$$S$$$, содержащее все $$$k$$$, при которых нет проигрышной позиции $$$(j, k)$$$, где $$$i \lt j \le i + k$$$. Это можно делать с помощью очереди с приоритетом, добавляя событие "проигрышные позиции с силой $$$k$$$ на отрезке $$$[i + 1, i + k]$$$ закончились" на позицию $$$i - k - 1$$$, когда позиция $$$(i, k)$$$ проигрышная. (Также, это добавление событий делается изначально для позиций $$$(n + 1, 0), (n + 1, 1), \ldots, (n + 1, n)$$$, т.к. они все проигрышные, а силу можно ограничить сверху до $$$n$$$, не меняя игру.) Таких событий в очереди будет добавлено суммарно не более $$$\mathcal{O}(n \log n)$$$ (по количеству проигрышных позиций), а значит, запросов к очереди не более $$$\mathcal{O}(n \log n)$$$, т.к. в каждой клетке мы будем прочитывать и удалять только события, относящиеся к ней. Заметим, что только когда мы прочитываем такое событие, мы добавляем в $$$S$$$ один элемент, и добавлений в $$$S$$$ тоже не более $$$\mathcal{O}(n \log n)$$$.

Будем находить проигрышные позиции для клетки $$$i$$$ так: позиция $$$(i, k)$$$ проигрышная тогда и только тогда, когда для всех $$$0 \le d \le a_i$$$, среди позиций $$$(j, k + d)$$$ при $$$j \in [i + 1, i + k + d]$$$ нет проигрышных, т.е. тогда и только тогда, когда в $$$S$$$ есть все из $$$k, k + 1, \ldots, k + a_i$$$. Для быстрого нахождения таких $$$k$$$ используем следующую структуру данных (будем называть её контейнером блоков):

Имеется множество $$$s$$$ натуральных чисел, изначально пустое. Все числа в $$$s$$$ будут находиться на отрезке $$$[1, n]$$$ и гарантируется, что все операции корректны (например, число, уже содержащееся в $$$s$$$, не будут просить добавить туда). Контейнер блоков может:

• добавить число $$$x$$$ в $$$s$$$ за $$$\mathcal{O}(\log n)$$$;
• найти длину самого длинного отрезка последовательных чисел в $$$s$$$ за $$$\mathcal{O}(1)$$$;
• найти любой самый длинный отрезок последовательных чисел в $$$s$$$ и удалить его наименьший элемент из $$$s$$$ за $$$\mathcal{O}(\log n)$$$.

Теперь, покажем, как быстро находить нужные $$$k$$$. Будем хранить $$$S$$$ в контейнере блоков. Если длина какого-то блока в $$$S$$$ больше $$$a_i$$$ и равна $$$l + a_i$$$, $$$l$$$ наименьших элементов этого блока будут являться проигрышными силами для клетки $$$i$$$ — это определяет все проигрышные силы для клетки $$$i$$$ и только их. Тогда давайте просто убирать наименьший элемент самого длинного блока, пока его длина больше $$$a_i$$$ — очевидно, при этом все убранные числа будут являться всеми проигрышными силами для клетки $$$i$$$. Запросов к контейнеру блоков на нахождение и удаление при рассмотрении клетки $$$i$$$ тогда на $$$1$$$ больше, чем количество проигрышных позиций $$$(i, k)$$$, то есть суммарно по всем клеткам не более $$$\mathcal{O}(n \log n)$$$. Запросов к контейнеру блоков на добавление, как мы показывали раньше, тоже не более $$$\mathcal{O}(n \log n)$$$.

То есть для каждой клетки мы сначала обрабатываем пришедшие из очереди с приоритетом события, сгружаем новые элементы в $$$S$$$ контейнера блоков, потом находим проигрышные позиции и, наконец, добавляем новые события для следующих клеток в очередь с приоритетом. Получается, мы в процессе узнаем каждую проигрышную позицию, остаётся просто поставить проверку, проигрышная ли позиция $$$(1, 1)$$$.

Итого $$$\mathcal{O}(n \log^2 n)$$$ на запросы в очереди с приоритетом, $$$\mathcal{O}(n \log^2 n)$$$ на запросы к контейнеру блоков, суммарная асимптотика $$$\mathcal{O}(n \log^2 n)$$$.

#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;

using pii = pair<int, int>;

struct Block {
    int l, r;

    Block() {}

    Block(int l, int r) : l(l), r(r) {}

    Block merge(const Block &o) const {
        return Block(min(l, o.l), max(r, o.r));
    }
};

auto cmp_len = [](const Block &a, const Block &b) { 
    if (a.r - a.l == b.r - b.l) return a.l < b.l;
    return a.r - a.l > b.r - b.l;
};

auto cmp_x = [](const Block &a, const Block &b) {
    if (a.l == b.l) return a.r < b.r;
    return a.l < b.l;
};

struct BlockContainer {
    set<Block, decltype(cmp_x)> sx{cmp_x};
    set<Block, decltype(cmp_len)> slen{cmp_len};

    void insert(int x) {
        Block b(x, x);
        auto r = sx.lower_bound(Block(x + 1, 0));
        if (r != sx.end() && r->l == x + 1) {
            b = b.merge(*r);
            sx.erase(*r);
            slen.erase(*r);
        }
        auto l = sx.lower_bound(Block(x - 1, 1e9));
        if (l != sx.begin()) {
            l--;
            if (l->r == x - 1) {
                b = b.merge(*l);
                sx.erase(*l);
                slen.erase(*l);
            }
        }
        sx.insert(b);
        slen.insert(b);
    }

    int get_max_length() {
        Block b = *slen.begin();
        return b.r - b.l + 1;
    }

    int pop_longest() {
        Block b = *slen.begin();
        slen.erase(b);
        sx.erase(b);
        int ans = b.l;
        b.l++;
        if (b.l <= b.r) {
            slen.insert(b);
            sx.insert(b);
        }
        return ans;
    }

    bool empty() {
        return sx.empty();
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    priority_queue<pii> q; // <cell, num>
    BlockContainer s;
    for (int i = 1; i < n; i++) {
        q.emplace(n - i - 1, i);
    }
    bool lose = 0;

    for (int c = n - 1; c >= 0; c--) {
        while (!q.empty() && q.top().first == c) {
            int x = q.top().second;
            s.insert(x);
            q.pop();
        }
        while (!s.empty() && s.get_max_length() >= a[c] + 1) {
            int x = s.pop_longest();
            q.emplace(c - x - 1, x);
            if (x == 1 && c == 0) lose = 1;
        }
    }

    cout << (lose ? 2 : 1) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

Отличная задача

Хорошая задача

Нормальная задача

Плохая задача

Ужасная задача