Давайте заметим, что $$$a_i > 0$$$, поэтому $$$MEX(a_1, a_2, ..., a_n) = 0$$$. Значит если $$$k = a_i$$$ для какого то $$$i$$$, то это значит, что новый MEX будет больше 0. Значит надо вывести любое число, которого нету в массиве.

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
    int n;
    cin >> n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>>a[i];
    if(n==3&&a[0]==1&&a[1]==2&&a[2]==3){
        cout<<4;
        return;
    }
    int r=1;
    for(int w=0;w<31;w++) {
        r*=2;
    }
    cout << r;
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
    while (t--) {
        sol();
    }
}

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

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

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

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

Отвратительная задача:

Не решил:

Во-первых, лекари не наносят никакого урона, поэтому их наличие никак не влияет на задачу.

Давайте выпишем весь урон полученный Андреем: $$$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$$$, где $$$x$$$ максимальное, при котором выполняется $$$x \cdot k \le n$$$. Попробуем найти его. Это условие равносильно $$$x \le \dfrac{n}{k}$$$, значит $$$x = \lfloor{\dfrac{n}{k}} \rfloor$$$. Теперь осталось найти сумму $$$k + 2 \cdot k + \dots + x \cdot k$$$, при этом $$$x$$$ уже известно. Можно заметить, что все слагаемые кратны $$$k$$$, его можно вынести: $$$damage = k \cdot (1 + 2 + 3 + \dots + x)$$$. Сумма $$$\sum\limits_{i = 1}^xi$$$ равна $$$\dfrac{x \cdot (x + 1)}{2}$$$, значит ответ это $$$k \cdot \dfrac{\lfloor{\dfrac{n}{k}} \rfloor \cdot (\lfloor{\dfrac{n}{k}} \rfloor + 1)}{2}$$$.

#include <iostream>
 
using namespace std;
#define int int64_t
 
void sol() {
    int n, k;
    cin >> n >> k;
    int j = n / k;
    cout << ((j * (j + 1)) / 2) * k << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    while (t--) {
        sol();
    }
}

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

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

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

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

Отвратительная задача:

Не решил:

Как известно, при $$$x \geq y$$$ выполняется $$$gcd(x, y) = gcd(x - y, y)$$$.

Поэтому $$$gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$$$, а также $$$gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$$$
Остается лишь найти такие различные $$$a, b, c$$$ такие, что $$$gcd(a, b) = gcd(b, c) = d$$$. Существует множество способов их выбрать, но самым легким является вариант $$$a = d, b = 2d, c = 3d$$$.

#include <bits/stdc++.h>
 
using namespace std;
#define int int64_t
 
void sol() {
    int d;
    cin >> d;
    if (d == 1)
        cout << 998244353 << ' ' << 1000000007 << ' ' << 1000000009 << '\n';
    else
        cout << d << ' ' << 2 * d << ' ' << 3 * d << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    sol();
}

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

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

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

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

Отвратительная задача:

Не решил:

Квадрат $$$2\times2$$$ мы можем покрасить $$$14-ю$$$ способами: $$$2^4 - 2$$$ ($$$2^4$$$ это количество способов раскрасить квадрат, 2 способа некорректны — когда мы красив весь квадрат либо в белый, либо в чёрный цвет). Всего таких квадратов $$$\frac {n^2}{4}$$$. Значит ответ равен $$$14^\frac {n^2}{4}$$$. Для быстрого возведения в степень воспользуемся бинарным возведением в степень.

#include <iostream>
#include <cmath>
using namespace std;
long long mod = 1e9 + 7;
 
long long binpow(long long k) {
    if (!k)
        return 1;
    if (k % 2)
        return (binpow(k - 1) * (long long)14) % mod;
    long long a = binpow(k / 2);
    return (a * a) % mod;
}
 
int main(int argc, char** argv) {
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << binpow(n * n / 4) << '\n';
    }
}

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

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

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

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

Отвратительная задача:

Не решил:

В задаче от нас требуется реализовать стек с поддержкой $$$gcd$$$

Давайте научимся отвечать на каждый запрос за $$$\mathcal{O}(1)$$$ Для этого будем в стеке хранить пару чисел — сам элемент, а также $$$gcd$$$ элементов, лежащих в стеке не выше данного. Иными словами:
$$$stack_i.first = a_i$$$
$$$stack_i.second = gcd(a_1, a_2, ..., a_i)$$$
Тогда $$$gcd$$$ всего стека будет находиться в $$$stack.top().second$$$
Чтобы выполнить запрос удаления, достаточно удалить верхний элемент стека, так как он не влияет на предыдущие элементы.
Чтобы добавить элемент в стек, нам нужно добавить пару $$$element,\;gcd(stack.top().second, element)$$$ (нужно не забыть рассмотреть случай, когда стек пуст)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef int ll;
typedef long double ld;
ll mod = 1e9 + 7;
ld eps = 1e-15;
 
ll gcd(ll a, ll b) {
    if (a < b)
        swap(a, b);
    if (a % b == 0)
        return b;
    return gcd(b, a % b);
}
 
int main(int argc, char** argv) {
    ll n, i;
    cin >> n;
    vector<ll> a(n), pr(n);
    for (i = 0; i < n; i++) {
        cin >> a[i];
        if (!i)
            pr[i] = a[i];
        else
            pr[i] = gcd(a[i], pr[i - 1]);
    }
    ll q;
    cin >> q;
    while (q--) {
        ll t;
        cin >> t;
        if (!t)
            pr.pop_back();
        else {
            ll x;
            cin >> x;
            if (pr.empty())
                pr.push_back(x);
            else
                pr.push_back(gcd(x, pr.back()));
        }
        if (pr.empty())
            cout << "1\n";
        else
            cout << pr.back() << '\n';
    }
}

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

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

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

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

Отвратительная задача:

Не решил:

Сначала рассмотрим $$$x\leq11$$$. Несложно убедиться, из них хорошими являются только $$$8$$$ и $$$10$$$. Далее рассматриваются $$$x>11$$$.
Дальше заметим, что одно из чисел $$$x-4$$$, $$$x-6$$$, $$$x-8$$$ будет составным, потому что будет делиться на 3(но при этом не равно трем). Следственно одна из пар $$$(4, x-4)$$$, $$$(6, x-6)$$$, $$$(8, x-8)$$$ будет подходить, значит ответ всегда YES.

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
    int x;
    cin >> x;
    if(x<=11) {
        if(x==8 || x==10) {
            cout << "YES";
        }
        else {
            cout << "NO";
        }
    }
    else {
        cout << "YES";
    }
    cout << '\n';
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen ("commander.in", "rt", stdin);
    //freopen ("commander.out", "wt", stdout);
    int t=1;
    cin >> t;
    while(t--) {
        sol();
    }
}

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

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

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

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

Отвратительная задача:

Не решил:

Решение 1:

Давайте применим бинарную теорему Гольдбаха(любое четное число начиная с 4 можно представить в виде суммы двух простых чисел). Тогда если 2 то ответ $$$NO$$$. Иначе $$$YES$$$. Теперь заметим, что нечетное число это всегда сумма четного числа + нечетного числа. Так как единственное простое число это 2, значит надо проверить, что $$$x - 2$$$ простое.

Решение 2:

Давайте посчитаем с помощью решета Эратосфена все простые числа до $$$10^{6}$$$. Оказывается, что если существует такое $$$y$$$, что $$$y$$$ и $$$x - y$$$ простые числа, то $$$min(y, x - y) \le 600$$$. Значит можно перебирать число $$$y$$$ до $$$600$$$ и проверять с помощью решета простое ли $$$x - y$$$.

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
void sol() {
    int tests;
    cin >> tests;
    vector <bool> f(1000001, true);
    f[1]=false;
    for(int r=2;r<f.size();r++) {
        if(f[r]) {
            for(int w=r;w*r<f.size();w++) {
                f[w*r]=false;
            }
        }
    }
    while(tests--) {
        int y;
        cin >> y;
        if(y%2==0) {
            if(y>=4) {
                cout << "YES";
            }
            else {
                cout << "NO";
            }
        }
        else {
            if(y<=3) {
                cout << "NO";
            }
            else {
                if(f[y-2]) {
                    cout << "YES";
                }
                else {
                    cout << "NO";
                }
            }
        }
        cout << '\n';
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen ("paths.in", "rt", stdin);
    //freopen ("paths.out", "wt", stdout);
    int t=1;
    while(t--) {
        sol();
    }
}

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

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

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

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

Отвратительная задача:

Не решил:

Для начала заметим, что возможен такой жадный алгоритм: пока в первом городе остались зараженные жители, будем летать на отрезке городов с $$$1$$$ по $$$k$$$ (иначе мы никак не вылечим первый город). После этого можно уже просто не летать над этим городом (так как если мы будем над ним летать, то в нем никого не вылечим, и лучше начать вылетать со второго города, чтобы возможно лечить жителей в $$$k + 1$$$-ом городе. То есть уберем первый город и будем решать задачу на оставшихся городах (если у нас станет k городов, то останется единственный способ излечения всех жителей: пусть $$$x$$$ $$$-$$$ это максимальное количество зараженных жителей в городе. Тогда к ответу надо прибавить $$$\lceil{\frac{x}{k}}\rceil$$$.

Осталось только быстро обновлять количество зараженных жителей в городах с $$$l$$$-го по $$$l + k - 1$$$-ый (когда мы пролетаем над этими городами). Это можно делать либо через дерево отрезков (тогда асимптотика равна $$$\mathcal{O}(n \cdot log(n))$$$, либо можно хранить для каждого города, сколько отрезков в нем начинаются и сколько отрезков в нем заканчиваются, в переменной хранить в скольких отрезках содержится текущий город, тогда при переходе на новый город мы прибавляем к этой переменной количество отрезков, начинающихся в этом городе, а при его рассмотрении вычитаем из этой переменной количество отрезков, заканчивающихся в текущем городе. Когда мы считаем, сколько раз нам нужно начать полетов в $$$i$$$-ом городе, то это число нужно прибавить к количеству отрезков, начинающихся в $$$i$$$-ом городе и к количеству отрезков, заканчивающихся в $$$i + k - 1$$$-ом городе. Тогда асимптотика будет равна $$$\mathcal{O}(n)$$$.

//#pragma optimize("3,o3,ofast")
 
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <iomanip>
 
using namespace std;
 
typedef long long ll;
typedef double ld;
//typedef __int128 lll;
ll inf = 1e15, mod = 998244353;
ld eps = 1e-6;
#define all(a) a.begin(), a.end()
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, k, x, i;
    cin >> n >> k >> x;
    vector<ll> a(n), upd(n);
    for (i = 0; i < n; i++)
        cin >> a[i];
    ll ans = 0, sm = 0;
    for (i = 0; i < n; i++) {
        sm -= upd[i];
        a[i] -= sm;
        if (a[i] > 0) {
            sm += (a[i] + x - 1) / x * x;
            ans += (a[i] + x - 1) / x;
            if (i + k < n)
                upd[i + k] = (a[i] + x - 1) / x * x;
        }
    }
    cout << ans;
}

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

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

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

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

Отвратительная задача:

Не решил:

Для начала заметим, что если $$$gcd(x, y) > 1$$$, то $$$gcd(x \cdot k, y) > 1$$$ для любого натурального $$$k$$$. Из этого следует, что если мы построим граф из $$$n$$$ вершин, где две вершины соединены ребром если $$$gcd$$$ соответствующих чисел в мультимножестве $$$> 1$$$, то в процессе игры эти вершины (и ребра этих вершин) будут просто сливаться и не изменятся. Тогда ответом будет просто набор перемножений всех чисел в каждой компоненте графа.

Нам нужно научиться быстро строить граф. На самом деле граф нам не нужен, нам нужно лишь разбиение на компоненты в графе. Для этого можно воспользоваться быстрой факторизацией $$$n$$$ чисел (про неё можете почитать интернете, но суть в том, что для каждого числа в решете Эратосфена будем хранить не простоту этого числа, а любое простое число не равное ему, на которое делится наше число. Тогда факторизуем число $$$x$$$ таким образом: пусть $$$f_x$$$ $$$-$$$ это любое простое число, на которое делится $$$x$$$, при этом $$$f_x < x$$$. Тогда добавим в наше множество простых в разложении $$$x$$$ число $$$f_x$$$ и будем продолжать решать задачу для $$$\frac{x}{f_x}$$$). Тогда профакторизуем все $$$n$$$ чисел и объединим их по каждому делителю (я это делал через СНМ, но можно просто хранить граф, тогда асимптотика сократится в $$$log(n)$$$ раз). Далее для каждого множества считаем перемножение чисел в нем по нужному модулю и выводим эти числа. Асимтотика авторского решения $$$\mathcal{O}(10^7 \cdot log(10^7) + n \cdot log(n))$$$.

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <cmath>
#include <deque>
#include <map>
#include <cassert>
#include <queue>
#include <unordered_set>
 
using namespace std;
 
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
const ll mod = 1e9 + 7, inf = 2e18 + 1;
const ld eps = 1e-9, pi = 3.1415926;
#define all(a) a.begin(), a.end()
 
ll gcd(ll a, ll b) {
    if (a < b)
        swap(a, b);
    if (!b)
        return a;
    return gcd(b, a % b);
}
 
vector<ll> tr;
 
ll root(ll v) {
    if (tr[v] == v)
        return v;
    return tr[v] = root(tr[v]);
}
 
void unite(ll a, ll b) {
    a = root(a);
    b = root(b);
    tr[b] = a;
}
 
int main() {
    //ios_base::sync_with_stdio(false);
    //ifstream cin("line3.in");
    //ofstream cout("line3.out");
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    //in.tie(nullptr);
    //out.tie(nullptr);
    ll n, i;
    cin >> n;
    tr.resize(n);
    for (i = 0; i < n; i++)
        tr[i] = i;
    vector<ll> u(1e7 + 1);
    for (i = 2; i <= 1e7; i++)
        if (!u[i]) {
            u[i] = i;
            for (ll j = i * i; j <= 1e7; j += i)
                u[j] = i;
        }
    vector<ll> a(n);
    for (i = 0; i < n; i++)
        cin >> a[i];
    auto b = a;
    map<ll, vector<ll>> mp;
    for (i = 0; i < n; i++)
        while (a[i] > 1) {
            ll x = u[a[i]];
            mp[x].push_back(i);
            while (a[i] % x == 0)
                a[i] /= x;
        }
    for (auto it:mp) {
        ll x = it.second[0];
        for (i = 1; i < it.second.size(); i++)
            unite(x, it.second[i]);
    }
    a = b;
    map<ll, ll> mp1;
    for (i = 0; i < n; i++) {
        tr[i] = root(i);
        if (!mp1[tr[i]])
            mp1[tr[i]] = 1;
        mp1[tr[i]] = (mp1[tr[i]] * a[i]) % mod;
    }
    cout << mp1.size() << '\n';
    for (auto it:mp1)
        cout << it.second << ' ';
}

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

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

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

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

Отвратительная задача:

Не решил:

Будем искать количество $$$r$$$ для каждого $$$l$$$ отдельно.

Давайте пока забудем про условие $$$gcd(a_l, a_r)>1$$$. Тогда теперь задача состоит в том, чтобы для каждого $$$l$$$ найти минимальное $$$r$$$ при котором выполняется $$$gcd(a_l, a_{l + 1}, ...,a_r) = 1$$$. Это можно сделать с помощью бинпоиска, предварительно написав дерево отрезков или sparse table, чтобы быстро находить $$$gcd$$$ на отрезке.

Мы научились для каждого $$$l$$$ находить суффикс, на котором мы можем выбирать $$$r$$$. Теперь нужно быстро считать на этом суффиксе количество $$$r$$$ таких, что $$$gcd(a_l, a_r) > 1$$$. Заметим, что $$$2 \leq a_i \leq 1000$$$, поэтому мы можем предпосчитать количество $$$r$$$ на всех суффиксах для всех возможных $$$a_i$$$.
Пусть $$$dp[x][i]$$$ — количество чисел на суффиксе $$$a_i, a_{i + 1}, ..., a_{n - 1}$$$ не взаимно простых с x. В качестве базы динамики сделаем $$$dp[x][n] = 0$$$. Пересчитывается динамика просто — $$$dp[x][i] = dp[x][i + 1] + (gcd(x, a_i) > 1)$$$. Посчитав такую динамику для всех $$$x$$$ от $$$2$$$ до $$$1000$$$, мы сможем быстро получать количество нужных нам чисел на суффиксе.

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
vector<int> a(50001,0);
vector<int> tr(200002,0);
int gcd(int b, int c) {
    if(b<c) {
        swap(b,c);
    }
    if(c==0) {
        return b;
    }
    else {
        return gcd(c, b%c);
    }
}
void bul(int u, int l, int r) {
    if (l == r) {
        tr[u] = a[l];
    } else {
        bul(u * 2, l, (l + r) / 2);
        bul(u * 2 + 1, (l + r) / 2 + 1, r);
        tr[u] = gcd(tr[u * 2], tr[u * 2 + 1]);
    }
}
 
int gcd(int u, int l, int r, int l2, int r2) {
    if (l <= l2 && r2 <= r) {
        return tr[u];
    }
    if (r2 < l || l2 > r) {
        return 0;
    }
    return gcd(gcd(u * 2, l, r, l2, (l2 + r2) / 2), gcd(u * 2 + 1, l, r, (l2 + r2) / 2 + 1, r2));
}
bool f[1001][1001];
int dp[50005][1001];
void sol() {
    int n;
    cin >> n;
    for (int r = 0; r < n; r++) {
        cin >> a[r];
    }
    for (int r = 1; r <= 1000; r++) {
        for (int w = 1; w <= 1000; w++) {
            if (gcd(r, w) > 1) {
                f[r][w] = true;
            } else {
                f[r][w] = false;
            }
        }
    }
    for (int r = n - 1; r >= 0; r--) {
        for (int w = 1; w <= 1000; w++) {
            if (r == n - 1) {
                if (f[w][a[r]]) {
                    dp[r][w] = 1;
                } else {
                    dp[r][w] = 0;
                }
            } else {
                dp[r][w] = dp[r + 1][w];
                if (f[w][a[r]]) {
                    dp[r][w]++;
                }
            }
        }
    }
    int sum = 0;
    bul(1, 0, n - 1);
    for (int r = 0; r < n; r++) {
        int l = r, w = n;
        while (l + 1 < w) {
            int u = (l + w)/2;
            if (gcd(1, r, u, 0, n - 1) == 1) {
                w = u;
            } else {
                l = u;
            }
        }
        if (l != n - 1) {
            sum += dp[l + 1][a[r]];
        }
    }
    cout << sum;
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    while (t--) {
        sol();
    }
}//

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

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

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

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

Отвратительная задача:

Не решил:

1 решение:

Будем искать ответ с конца, предполагая, что по приезде в вершину n останется ровно $$$t$$$ монет. Тогда за $$$1$$$ шаг до приезда у нас будет $$$x$$$ монет такое, что $$$x - \frac{x}{w_1} \ge t$$$, причем $$$x$$$ минимально, за $$$2$$$ шага $$$y - \frac{y}{w_2} \ge x$$$ и т. д., где $$$w_1$$$ и $$$w_2$$$ $$$-$$$ веса дорог из оптимального пути. Пусть $$$d_i$$$ $$$-$$$ минимальное число монет, которое будет когда мы попадем из $$$n$$$ в $$$i$$$, тогда можно легко восстановить все веса ребер из $$$i$$$ в соответствии с неравенством выше. Теперь задача свелась к тому что надо найти кратчайший путь из $$$n$$$ в $$$1$$$. Для этого можно воспользоваться алгоритмом Дейкстры (он работает, так как ребра не изменяются случайно, и отрицательных ребер нет).

2 решение:

Будем бинпоиском перебирать ответ: тогда для каждого возможного ответа сделаем обычную Дейкстру (просто веса будут изменятся в зависимости от кратчайшего пути в вершину). Проверяем что расстояние то вершины $$$n$$$ больше или равно $$$t$$$.

В обоих решениях асимптотика $$$\mathcal{O}(n \cdot log(n) \cdot log(10^9))$$$.

В коде написано первое решение.

#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <cmath>
#include <deque>
#include <map>
#include <cassert>
#include <queue>
#include <unordered_set>
 
using namespace std;
 
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
const ll mod = 1e9 + 7, inf = 2e18 + 1;
const ld eps = 1e-9, pi = 3.1415926;
#define all(a) a.begin(), (a).end()
 
ll f(ll d, ll w) {
    if (d < w)
        return d;
    ll l = 0, r = 1000000001, md;
    while (l + 1 < r) {
        md = (l + r) / 2;
        if (md - md / w >= d)
            r = md;
        else
            l = md;
    }
    return r;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    //ifstream cin("line3.in");
    //ofstream cout("line3.out");
    cin.tie(nullptr);
    cout.tie(nullptr);
    //in.tie(nullptr);
    //out.tie(nullptr);
    ll n, m, t, i;
    cin >> n >> m >> t;
    vector<vector<pair<ll, ll>>> g(n);
    while (m--) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<ll> d(n, inf);
    d[n - 1] = t;
    set<pair<ll, ll>> st;
    st.insert({t, n - 1});
    while (!st.empty()) {
        ll v = st.begin()->second;
        st.erase(st.begin());
        for (auto it:g[v])
            if (d[it.first] > f(d[v], it.second)) {
                st.erase({d[it.first], it.first});
                d[it.first] = f(d[v], it.second);
                st.insert({d[it.first], it.first});
            }
    }
    cout << d[0];
}

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

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

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

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

Отвратительная задача:

Не решил: