• Отличный:
• Хороший:
• Обычный:
• Плохой:
• Ужасный:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

Сколько человек может быть в одной цивилизации?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        if (n == 2) cout << "2\n";
        if (n == 3) cout << "3\n";
        if (n >= 4) cout << n % 2 << '\n';
    }
    
    return 0;
}

Сколько минут песка останется в верхней половине часов сразу после второго переворота?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int s, k, m;
        cin >> s >> k >> m;
        
        if (s <= k) cout << max(0, s - m % k) << '\n';
	else cout << (((m % (2 * k)) < k) ? s - m % k : k - m % k) << '\n';
    }
    
    return 0;
}

Почему полный перебор неэффективен? Как его можно улучшить?

Сколько различных значений можно получить, начиная с числа $$$n$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n, k;
        cin >> n >> k;
        
        int l = n, r = n;
        int cnt = 0;
        while (r != 1) {
            if (l <= k && k <= r) break;
            l = l / 2;
            r = r / 2 + r % 2;
            cnt++;
        }
        if (l <= k && k <= r) cout << cnt << '\n';
        else cout << -1 << '\n';
    }
    
    return 0;
}

Выигрышная стратегия Алисы связана с битами.

Оптимальное количество ходов для Алисы зависит только от старшего бита и количества единичных битов.

Число $$$n$$$ является степенью двойки, а значит, если вычесть $$$1$$$, то любое подмножество битов числа $$$n-1$$$ не будет превышать $$$n-1$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
int c_n_k[31][31];

int main() {
    for (int i = 0; i < 30; ++i) {
        for (int j = 0; j < 30; ++j) {
            if (i < j) c_n_k[i][j] = 0;
            else if (j == 0) c_n_k[i][j] = 1;
            else c_n_k[i][j] = c_n_k[i - 1][j] + c_n_k[i - 1][j - 1];
        }
    }

    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        int d = 0;
        while (n % 2 == 0) {
            n /= 2;
            ++d;
        }

        int ans = 0;
        for (int max_bit = 0; max_bit < d; ++max_bit) {
            for (int cnt_bit = 1; cnt_bit <= max_bit + 1; ++cnt_bit) {
                if (max_bit + cnt_bit <= k) continue;
                ans += c_n_k[max_bit][cnt_bit - 1];
            }
        }

        if (d + 1 > k) ++ans;
        cout << ans << "\n";
    }

    return 0;
}

Решите задачу, когда $$$n$$$ — любое целое число от $$$1$$$ до $$$10^9$$$, не обязательно степень двойки.

Если какой-то массив $$$k$$$-изысканный, то любой его подотрезок длины не менее $$$2$$$ также $$$k$$$-изысканный.

Если $$$k_1 \gt k_2$$$ и какой-то массив $$$k_1$$$-изысканный, то он также и $$$k_2$$$-изысканный.

Если какой-то массив длины $$$m$$$ $$$k$$$-изысканный, то сколько у него $$$k$$$-изысканных подотрезков?

Для фиксированного $$$k$$$ придумайте, как разбить всю исходную перестановку на отрезки, каждый из которых либо $$$k$$$-изысканный, либо длины $$$1$$$, так, чтобы можно было воспользоваться формулой из предыдущей подсказки.

Как переходить от разбиения на отрезки для $$$k+1$$$ до разбиения на отрезки для $$$k$$$?

Найдите, как изменяется ответ при каждом объединении двух отрезков.

#include <bits/stdc++.h>

using namespace std;

vector <int> parent;
vector <int> rnk;
vector <int> sz;

void make_set(int v) {
    parent[v] = v;
    rnk[v] = 0;
    sz[v] = 1;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap (a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            ++rnk[a];
        sz[a] += sz[b];
    }
}

long long cnt(int x) {
    x = find_set(x);
    return (long long)sz[x] * (sz[x] - 1) / 2;
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        map <int, vector <int>> m;
        int pr;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            if (i > 0)
                m[abs(a - pr)].push_back(i);
            pr = a;
        }
        
        parent.resize(n);
        rnk.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
        
        vector <long long> ans;
        long long cur = 0;
        for (int i = n - 1; i > 0; i--) {
            for (auto y : m[i]) {
                cur -= cnt(y);
                cur -= cnt(y - 1);
                union_sets(y, y - 1);
                cur += cnt(y);
            }
            ans.push_back(cur);
        }
        
        reverse(ans.begin(), ans.end());
        for (auto x : ans) cout << x << ' ';
        cout << '\n';
        
        parent.clear();
        rnk.clear();
        sz.clear();
    }

    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 200001;

int n;
vector <int> graph[MAXN];
vector <bool> dp[MAXN];

void merge_dp(vector <bool>& lhs, vector <bool>& rhs, vector <bool>& result) {
    for (int i = 0; i < 3; ++i) {
        if (!lhs[i]) continue;
        for (int j = 0; j < 3; ++j) {
            if (!rhs[j]) continue;
            result[(i + j) % 3] = true;
        }
    }
}

void dfs(int u, int p) {
    vector <int> child;

    for (auto v : graph[u]) if (v != p) {
        dfs(v, u);
        child.push_back(v);
    }

    dp[u].resize(3);

    if (!child.empty()) {
        dp[u][0] = true;
        for (auto v : child) {
            vector <bool> result(3, false);
 
            merge_dp(dp[u], dp[v], result);
            dp[u] = result;
        }
    }

    dp[u][1] = true;
}

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
            dp[i].clear();
        }
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        dfs(1, -1);

        cout << (dp[1][0] ? "YES" : "NO") << '\n';
    }

    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 200001;

int n;
vector <int> graph[MAXN];
bool ans;

int dfs(int u, int p) {
    vector <int> child;
    int cnt = 0;

    for (auto v : graph[u]) if (v != p) {
        cnt++;
        auto t = dfs(v, u);
        if (t != 0) {
            child.push_back(t);
        }
    }

    if (child.size() > 1) {
        ans = true;
        return 0;
    }

    int type = cnt == 0 ? 0 : (cnt + 2) % 3;
    vector <int> ord;
    if (type) {
        ord.push_back(type);
    }
    if (!child.empty()) {
        ord.push_back(child[0]);
    }
    if (ord.size() == 2 && ord[0] + ord[1] != 3) {
        ans = true;
        return 0;
    }
    if (ord.size() >= 1) return ord[0];
    return 0;
}

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

    int t;
    cin >> t;

    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            graph[i].clear();
        }
 
        for (int i = 0; i < n - 1; ++i) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }

        ans = false;
        int res = dfs(1, 1);
        if (res == 2) {
            ans = true;
        }
     
        cout << (ans ? "YES" : "NO") << '\n';
    }

    return 0;
}

Зафиксируем $$$L$$$ и $$$R$$$ и введем функции от целых $$$d$$$: $$$f(d) = d$$$, $$$g(d) = \min(a_L, \dots, a_{L+d})$$$, где $$$0 \le d \le R-L$$$. Что можно сказать об этих функциях?

Сколько раз может выполниться условие задачи, если выразить его через $$$f$$$ и $$$g$$$?

Функция $$$h(d) = f(d) - g(d)$$$ монотонна, поэтому единственный кандидат на роль точки пересечения — это минимальное $$$d$$$, при котором $$$h(d) \ge 0$$$ (или $$$f(d) \ge g(d)$$$).

Дерево отрезков.

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 2e5 + 7;

int a[MAXN], st[4 * MAXN];

void build(int v, int l, int r) {
    if (l + 1 == r) {
        st[v] = a[l];
        return;
    }
    int m = (r + l) / 2;
    build(v * 2 + 1, l, m);
    build(v * 2 + 2, m, r);
    st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}

void upd(int v, int l, int r, int i, int x) {
    if (i < l || r <= i) return;
    if (l + 1 == r) {
        a[i] = x;
        st[v] = x;
        return;
    }
    int m = (r + l) / 2;
    upd(v * 2 + 1, l, m, i, x);
    upd(v * 2 + 2, m, r, i, x);
    st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
}

int getMin(int v, int l, int r, int lq, int rq) {
    if (rq <= l || r <= lq) return (int) 1e6;
    if (lq <= l && r <= rq) return st[v];
    int m = (r + l) / 2;
    return min(getMin(v * 2 + 1, l, m, lq, rq), getMin(v * 2 + 2, m, r, lq, rq));
}

int ans, currMn;

void findInter(int v, int l, int r, int lq, int rq) {
    if (rq <= l || r <= lq || ans != (int) 1e6) return;
    if (lq <= l && r <= rq && min(currMn, st[v]) > r - lq - 1) {
        currMn = min(currMn, st[v]);
        return;
    }
    if (l + 1 == r) {
        ans = l;
        return;
    }
    int m = (r + l) / 2;
    findInter(v * 2 + 1, l, m, lq, rq);
    findInter(v * 2 + 2, m, r, lq, rq);
}


int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, q;
        cin >> n >> q;
        for (int i = 0; i < n; ++i) cin >> a[i];

        build(0, 0, n);
        while (q--) {
            int idx;
            cin >> idx;

            if (idx == 1) {
                int i, x;
                cin >> i >> x;
                upd(0, 0, n, i - 1, x);
            } else {
                int l, r;
                cin >> l >> r;
                l--;

                if (getMin(0, 0, n, l, r) > r - l) {
                    cout << "0\n";
                    continue;
                }

                ans = currMn = (int) 1e6;
                findInter(0, 0, n, l, r);
                cout << (ans != (int) 1e6 && getMin(0, 0, n, l, ans + 1) == ans - l) << "\n";
            }
        }
    }

    return 0;
}

• Отличный:
• Хороший:
• Обычный:
• Плохой:
• Ужасный:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F:
• G:

• A:
• B:
• C1:
• C2:
• D:
• E:
• F:
• G:

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    string a, b, c;
    int n, m;
    cin >> n >> a;
    cin >> m >> b >> c;
    string add_left = "";
    for (int i = 0; i < m; ++i) {
        if (c[i] == 'V') {
            add_left += b[i];
        } else {
            a += b[i];
        }
    }
    reverse(add_left.begin(), add_left.end());
    cout << add_left + a << '\n';
}

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

Если Вадим дописал к числу $$$x$$$

Unable to parse markup [type=CF_MATHJAX]

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long r;
        cin >> r;
        
        long long d = 11;
        vector <long long> ans;
        while (r >= d) {
            if (r % d == 0)
                ans.push_back(r / d);
            d = (d - 1) * 10 + 1;
        }
        
        cout << (int)ans.size() << '\n';
        for (int i = (int)ans.size() - 1; i >= 0; --i)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

Есть ли смысл пользоваться одним и тем же типом сделок больше 2 раз?

Решение с минимальным количеством сделок единственно.

Троичная система счисления.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        long long min_k = 0;
        long long min_cost = 0;
        int sz = 0;
        while (n) {
            min_k += n % 3;
            min_cost += (n % 3) * cost[sz];
            n /= 3;
            sz++;
        }
        cout << min_cost << '\n';
    }
    
    return 0;
}

Что выгоднее: $$$3$$$ сделки по $$$3^x$$$ арбузов или одна сделка на $$$3^{x+1}$$$ арбуз?

Вспомните решение задачи C1.

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    vector <long long> cost;
    long long c = 3;
    long long cnt = 1;
    for (int i = 0; i < 21; ++i) {
        cost.push_back(c);
        c = 3 * c + cnt;
        cnt *= 3;
    }

    int t;
    cin >> t;
    while (t--) {
        long long n, k;
        cin >> n >> k;
        vector <long long> tr;
        long long min_k = 0;
        while (n) {
            tr.push_back(n % 3);
            min_k += n % 3;
            n /= 3;
        }
        if (min_k > k) {
            cout << -1 << '\n';
            continue;
        }
        k -= min_k;
        k /= 2;
        for (int i = (int)tr.size() - 1; i >= 1; --i) {
            if (tr[i] <= k) {
                tr[i - 1] += 3 * tr[i];
                k -= tr[i];
                tr[i] = 0;
            } else {
                tr[i - 1] += k * 3;
                tr[i] -= k;
                break;
            }
        }
        ll an = 0;
        for (int i = (int)tr.size() - 1; i >= 0; --i)
            an += cost[i] * tr[i];
        cout << an << '\n';
    }
    
    return 0;
}

Найдите, какому числу принадлежит $$$k$$$-я цифра в бесконечной последовательности. Пусть это число $$$n$$$. Тогда вместо анализа последовательности можно посчитать сумму сумм цифр всех целых чисел от

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Мысленно добавьте ко всем числам от

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long k;
        cin >> k;
        long long cur = 9, len = 1;
        while (k - cur * len > 0) {
            k -= cur * len;
            cur *= 10;
            len++;
        }
        string s = to_string(cur / 9 + (k - 1) / len);
        long long ans = 0;
        for (int i = 0; i < (k - 1) % len + 1; i++)
            ans += s[i] - '0';
        long long pr_s = 0;
        for (int i = 0; i < s.length(); i++) {
            int curd = s[i] - '0';
            if (curd)
                ans += curd * (len - 1) * cur / 2 + curd * (2 * pr_s + curd - 1) / 2 * cur / 9;
            cur /= 10, len--;
            pr_s += curd;
        }
        cout << ans << '\n';
    }
    
    return 0;
}

Пусть нам известно, сколько конкретно карточек должен взять Вадим, а сколько ~--- Костя (например,

Unable to parse markup [type=CF_MATHJAX]

Нам нужно быстро вычислять, чему равна сумма $$$x$$$ максимальных элементов в массиве $$$a$$$ и сумма $$$y$$$ максимальных элементов в массиве

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Как решить данную задачу, если

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Если

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());

    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];

    vector <pair <int, int>> ans(n + m + 1);
    int l = 0, r = 0;
    for (int i = 1; i < ans.size(); i++) {
        if (l < n && r < m) {
            if (a[l] < b[r])
                r++;
            else
                l++;
        }
        else if (l == n)
            r++;
        else if (r == m)
            l++;
        ans[i] = { l, r };
    }

    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        l = ans[z].first, r = ans[z].second;
        if (l > x)
            cout << pa[x] + pb[z - x] << '\n';
        else if (r > y)
            cout << pa[z - y] + pb[y] << '\n';
        else
            cout << pa[l] + pb[r] << '\n';
    }
}

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

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> a(n), b(m);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
 
    vector <long long> pa(n + 1), pb(m + 1);
    for (int i = 0; i < n; i++)
        pa[i + 1] = pa[i] + a[i];
    for (int i = 0; i < m; i++)
        pb[i + 1] = pb[i] + b[i];
 
    for (int i = 0; i < q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
 
        int l = max(0, z - y);
        int r = min(z, x);
        while (l + 2 < r) {
            int m1 = (l + l + r) / 3;
            int m2 = (l + r + r) / 3;
            if (pa[m1] + pb[z - m1] > pa[m2] + pb[z - m2]) {
                r = m2;
            } else {
                l = m1;
            }
        }
 
        long long s = 0;
        for (int i = l; i <= r; i++)
            s = max(s, pa[i] + pb[z - i]);
 
        cout << s << '\n';
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

Вспомните или узнайте, что такое мосты и поймите как это связано с тропинками, которые лежат на всех путях из

Unable to parse markup [type=CF_MATHJAX]

Как найти все мосты, которые лежат на всех путях из

Unable to parse markup [type=CF_MATHJAX]

Решите задачу, если

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

Как для каждой вершины найти ближайшую вершину из некоторого множества вершин

Unable to parse markup [type=CF_MATHJAX]

#include <bits/stdc++.h>
 
using namespace std;
 
vector <vector <int>> g;
vector <bool> used;
vector <int> d, h;
vector <pair <int, int>> edges;
vector <int> cut, path;
int mark = 1;

void dfs(int v, int p, int n) {
    used[v] = true;
    d[v] = h[v] = (p == -1 ? 0 : d[p] + 1);
    if (v == n) mark = 0;
    for (auto e : g[v]) {
        int to = edges[e].first + edges[e].second - v;
        if (to == p) continue;
        if (used[to])
            h[v] = min(h[v], d[to]);
        else {
            path[e] ^= mark;
            dfs(to, v, n);
            path[e] ^= mark;
            h[v] = min(h[v], h[to]);
            if (h[to] > d[v]) cut[e] = 1;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        g.assign(n + 1, {});
        used.assign(n + 1, false);
        d.assign(n + 1, 0);
        h.assign(n + 1, 0);
        edges = {};
        cut.assign(m, false);
        path.assign(m, false);
        mark = 1;
        for (int i = 0; i < m; ++i) {
            int a, b;
            cin >> a >> b;
            edges.push_back({a, b});
            g[a].push_back(i);
            g[b].push_back(i);
        }
        
        dfs(1, -1, n);
        
        vector <int> ans(n + 1, n + m);
        vector <int> dist(n + 1, n + m);
        queue <int> q;
        for (int i = 0; i < m; ++i) {
            if (cut[i] && path[i]) {
                ans[edges[i].first] = min(ans[edges[i].first], i + 1);
                ans[edges[i].second] = min(ans[edges[i].second], i + 1);
                if (dist[edges[i].first]) {
                    dist[edges[i].first] = 0;
                    q.push(edges[i].first);
                }
                if (dist[edges[i].second]) {
                    dist[edges[i].second] = 0;
                    q.push(edges[i].second);
                }
            }
        }
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto e : g[v]) {
                int to = edges[e].first + edges[e].second - v;
                if (dist[to] > dist[v] + 1) {
                    dist[to] = dist[v] + 1;
                    ans[to] = ans[v];
                    q.push(to);
                }
                else if (dist[to] == dist[v] + 1)
                    ans[to] = min(ans[to], ans[v]);
            }
        }
        
        int Q;
        cin >> Q;
        while (Q--) {
            int v;
            cin >> v;
            if (ans[v] == n + m) cout << -1;
            else cout << ans[v];
            if (t || Q) cout << '\n';
        }
    }
    
    return 0;
}

Дописывать новые символы одновременно и выше, и ниже изначальной таблицы смысла нет. Аналогично, нет смысла дописывать одновременно и слева, и справа от таблицы.

Центр таблицы оптимального ответа лежит внутри изначальной.

Нам не нужно строить ответ, а лишь достаточно проверить, что для текущего центра ответ существует. Подумайте, как это сделать.

Для текущего центра ответ существует, если подтаблица, которая является пересечением исходной таблицы и повёрнутой вокруг центра на

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

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

Для проверки подтаблиц на то, что они при повороте на

Unable to parse markup [type=CF_MATHJAX]

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int P[2] = { 107, 61 };
int BP[2];

long long bin_pow(long long a, int n) {
    long long ret = 1;
    while (n) {
        if (n & 1) ret = (ret * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return ret;
}

inline int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) return res - MOD;
    return res;
}

inline int sub(int a, int b) {
    int res = a - b;
    if (res < 0) return res + MOD;
    return res;
}

inline int mult(int a, int b) {
    long long res = (long long)a * b;
    if (res >= MOD) return res % MOD;
    return res;
}

int main() {
    int t;
    cin >> t;
    
    BP[0] = bin_pow(P[0], MOD - 2);
    BP[1] = bin_pow(P[1], MOD - 2);
    vector <int> pows[2];
    vector <int> bpows[2];
    for (int j = 0; j < 2; j++) {
        pows[j].resize(1e6, 1);
        bpows[j].resize(1e6, 1);
        for (int i = 1; i < 1e6; i++) {
            pows[j][i] = mult(pows[j][i - 1], P[j]);
            bpows[j][i] = mult(bpows[j][i - 1], BP[j]);
        }
    }
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        vector <string> f(n);
        for (int i = 0; i < n; i++)
            cin >> f[i];
        
        vector <vector <int>> hash(n + 2, vector <int> (m + 2, 0));
        vector <vector <int>> bhash(n + 2, vector <int> (m + 2, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][i - 1], pows[1][j - 1]));
                hash[i][j] = add(sub(add(hash[i - 1][j], hash[i][j - 1]), hash[i - 1][j - 1]), cur);
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][n - i], pows[1][m - j]));
                bhash[i][j] = add(sub(add(bhash[i + 1][j], bhash[i][j + 1]), bhash[i + 1][j + 1]), cur);
            }
        }
        
        auto isp = [&](int x1, int y1, int x2, int y2) {
            int hsh = add(sub(sub(hash[x2][y2], hash[x1-1][y2]), hash[x2][y1-1]), hash[x1-1][y1-1]);
            int bhsh = add(sub(sub(bhash[x1][y1], bhash[x2+1][y1]), bhash[x1][y2+1]), bhash[x2+1][y2+1]);
            hsh = mult(hsh, mult(bpows[0][x1 - 1], bpows[1][y1 - 1]));
            bhsh = mult(bhsh, mult(bpows[0][n - x2], bpows[1][m - y2]));
            return hsh == bhsh;
        };
        
        int mn = n * m * 4;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (isp(1, 1, i, j)) mn = min(mn, (2 * n - i) * (2 * m - j));
                if (isp(1, j, i, m)) mn = min(mn, (2 * n - i) * (m + j - 1));
                if (isp(i, 1, n, j)) mn = min(mn, (n + i - 1) * (2 * m - j));
                if (isp(i, j, n, m)) mn = min(mn, (n + i - 1) * (m + j - 1));
            }
        }
        
        cout << mn - m * n << '\n';
    }
    
    return 0;
}

• Отличный:
• Хороший:
• Обычный:
• Плохой:
• Ужасный:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

• A:
• B:
• C:
• D:
• E:
• F:
• G:

Докажите, что число $$$2$$$ не является идеальным генератором. Какие еще числа не являются идеальными генераторами по той же причине?

Докажите, что число $$$3$$$ является идеальным генератором. В чем отличие от предыдущего случая?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
        if (n % 2 == 1) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
 
    return 0;
}

Какую минимальную стоимость можно получить?

Сколько ненулевых цифр должно быть в оставшемся числе, чтобы стоимость была минимальна?

Как добиться, чтобы в числе было как можно больше ведущих нулей?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        bool met_positive = false;
        int cnt_zero = 0;
        
        for (auto i = n - 1; i >= 0; --i) {
            if (s[i] != '0') {
                met_positive = true;
            } else if (met_positive) {
                cnt_zero++;
            }
        }
        
        cout << n - (cnt_zero + 1) << '\n';
    }
    return 0;
}

$$$y$$$ всегда делится на $$$x$$$.

Что происходит, если $$$k \geq 2$$$?

Если $$$k \geq 2$$$ и $$$x \geq 2$$$, то $$$y$$$ никогда не будет простым. А есть ли крайние случаи с $$$k = 1$$$ или $$$x = 1$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
bool is_prime(int x) {
    if (x <= 1) {
        return false;
    }
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
 
void solve() {
    int x, k;
    cin >> x >> k;
    if (k > 1 && x > 1) {
        cout << "NO";
    } else if (k == 1) {
        cout << (is_prime(x) ? "YES" : "NO");
    } else {
        cout << ((k == 2) ? "YES" : "NO");
    }
}
 
int main() {
    int tests;
    cin >> tests;
    while (tests--) {
        solve();
        cout << '\n';
    }
}

Как меняется ответ при уменьшении $$$n$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n, q;
        cin >> n >> q;
        
        while (q--) {
            string type;
            cin >> type;
            
            if (type == "->") {
                int x, y;
                cin >> x >> y;
                x--, y--;
                
                long long num = 0;
                for (int i = n - 1; i >= 0; --i) {
                    int cur = 1 << i;
                    if (!(x & cur) && !(y & cur))
                        num ^= 0ll << (2 * i);
                    if ((x & cur) && (y & cur))
                        num ^= 1ll << (2 * i);
                    if ((x & cur) && !(y & cur))
                        num ^= 2ll << (2 * i);
                    if (!(x & cur) && (y & cur))
                        num ^= 3ll << (2 * i);
                }
                cout << num + 1 << '\n';
            }
            else {
                long long num;
                cin >> num;
                num--;
                
                int x = 0, y = 0;
                for (int i = n - 1; i >= 0; --i) {
                    long long cur = 3ll << (2 * i);
                    if ((num & cur) >> (2 * i) == 0)
                        x ^= 0 << i, y ^= 0 << i;
                    if ((num & cur) >> (2 * i) == 1)
                        x ^= 1 << i, y ^= 1 << i;
                    if ((num & cur) >> (2 * i) == 2)
                        x ^= 1 << i, y ^= 0 << i;
                    if ((num & cur) >> (2 * i) == 3)
                        x ^= 0 << i, y ^= 1 << i;
                }
                cout << x + 1 << ' ' << y + 1 << '\n';
            }
        }
    }
    
    return 0;
}

Как проверить, существует ли разбиение для фиксированного $$$x$$$?

Можно использовать бинарный поиск.

#include <bits/stdc++.h>

using namespace std;

vector<int> nums(2e5 + 5, 0);

bool check(vector<int>& v, int k, int m)
{
    int cnt = 0;
    int cur_mex = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] <= v.size() + 1) {
            nums[v[i]] = 1;
        }
        while (nums[cur_mex]) {
            cur_mex++;
        }
        if (cur_mex >= m) {
            cnt++;
            for (int j = 0; j < min(m + 1, (int)v.size() + 2); j++) {
                nums[j] = 0;
            }
            cur_mex = 0;
        }
    }
    for (int j = 0; j < v.size() + 2; j++) {
        nums[j] = 0;
    }
    return cnt >= k;
}

void solve()
{
    int n, k;
    cin >> n >> k;

    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    int l = 0;
    int r = 1e9;
    while (r - l > 1) {
        int m = (r + l) / 2;
        if (check(v, k, m)) {
            l = m;
        } else {
            r = m;
        }
    }

    cout << l << '\n';
}

signed main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

Нам нужно гарантировать, что мы составим массив $$$a$$$. Тогда при обращении к нейросети стоит рассматривать худший случай.

Прочитайте предыдущую подсказку. Сколько операций первого типа, применённых к $$$i$$$-й нейросети, нам потребуется, чтобы получить от неё хотя бы одно правильное (то есть такое, что $$$b_{i, j}= a_j$$$) слово?

Прочитайте предыдущую подсказку и ответ на неё. С какой нейросети оптимально будет начать? Сколько будет пропусков в массиве $$$c$$$ после взаимодействия с этой нейросетью?

В массиве $$$c$$$ сейчас нет пропусков, но на некоторых позициях стоят неправильные слова. За сколько операций можно заменить одно неправильное слово на правильное?

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (auto &i: a) {
        cin >> i;
    }
    vector<vector<string>> b(m, vector<string>(n));
    for (auto &ar: b) {
        for (auto &s: ar) {
            cin >> s;
        }
    }
    vector<bool> exists(n);
    int x = 0;
    for (int i = 0; i < m; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++) {
            if (a[j] == b[i][j]) {
                cnt++;
                exists[j] = true;
            }
        }
        x = max(x, cnt);
    }
    if (all_of(exists.begin(), exists.end(), identity())) {
        cout << n + 2 * (n - x) << "\n";
    } else {
        cout << "-1\n";
    }
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Пусть самый короткий отрезок будет иметь границы $$$l$$$ и $$$r$$$. Что тогда можно сказать про индексы $$$i$$$ и $$$j$$$ для которых достигается максимум выражения $$$a_i \oplus a_j$$$?

Операцию $$$x \oplus y$$$ над числами int32 можно представить как XOR двух бинарных строк длины $$$32$$$. Что тогда можно сказать про сравнение чисел? В каком случае выполняется выражение $$$x \oplus y = z$$$? А $$$x \oplus y \gt z$$$?

Как с помощью бора на бинарных строках можно искать ближайший индекс $$$j$$$ такой, что $$$a_i \oplus a_j = k$$$?

#include <bits/stdc++.h>
 
using namespace std;
 
const int LOG_X = 29;
 
struct node {
    int children[2] { -1, -1 };
    int last = -1;
};
 
int find(const vector<node>& trie, int value, int border) {
    int res = -1;
    int current = 0;
    bool ok = true;
    for (int position = LOG_X; ok && position >= 0; position--) {
        int x_bit = (value >> position) & 1;
        int k_bit = (border >> position) & 1;
        auto& children = trie[current].children;
        if (k_bit == 1) {
            if (children[x_bit ^ 1] != -1) {
                current = children[x_bit ^ 1];
            } else {
                ok = false;
            }
        } else {
            if (children[x_bit ^ 1] != -1) {
                res = max(res, trie[children[x_bit ^ 1]].last);
            }
            if (children[x_bit] != -1) {
                current = children[x_bit];
            } else {
                ok = false;
            }
        }
    }
    if (ok) {
        res = max(res, trie[current].last);
    }
    return res;
}
 
void add(vector<node>& trie, int value, int index) {
    int current = 0;
    trie[current].last = max(trie[current].last, index);
    for (int position = LOG_X; position >= 0; position--) {
        int x_bit = (value >> position) & 1;
        if (trie[current].children[x_bit] == -1) {
            trie[current].children[x_bit] = trie.size();
            trie.push_back(node());
        }
        current = trie[current].children[x_bit];
        trie[current].last = max(trie[current].last, index);
    }
}
 
void solve() {
    int n, k;
    cin >> n >> k;
 
    int ans = n + 1;
    vector<node> trie(1);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        add(trie, x, i);
        int y = find(trie, x, k);
        if (y != -1) {
            ans = min(ans, i - y + 1);
        }
    }
 
    if (ans == n + 1) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }
}
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        solve();
    }
 
    return 0;
}