Let's note that $$$a_i \gt 0$$$, so $$$MEX(a_1, a_2, ..., a_n) = 0$$$. So if $$$k=a_i$$$ for some $$$i$$$, it means that the new MEX will be greater than 0. So you need to output any number that is not in the array.

#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();
    }
}

Great task:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

Firstly, healers do not cause any damage, so their presence does not affect the task in any way.

Let's write out all the damage received by Andrey: $$$damage = 0 + k + 2 \cdot k + \dots + x \cdot k$$$, where $$$x$$$ is the maximum at which $$$x \cdot k\le n$$$ is executed. Let's try to find him. This condition is equivalent to $$$x\le\dfrac{n}{k}$$$, so $$$x =\lfloor{\dfrac{n}{k}}\rfloor$$$. Now it remains to find the sum of $$$k + 2 \cdot k + \dots + x \cdot k$$$, while $$$x$$$ is already known. It can be noticed that all terms are multiples of $$$k$$$, it can be taken out: $$$damage = k \cdot (1 + 2 + 3 + \dots + x)$$$. The sum of $$$\sum\limits_{i = 1}^xi$$$ is equal to $$$\dfrac{x\cdot (x + 1)}{2}$$$, so the answer is $$$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();
    }
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

As is known, for $$$x\geq y$$$, $$$gcd(x, y) = gcd(x - y, y)$$$ is executed.

Therefore $$$gcd(a + 2b, a + b) = gcd(a + b, b) = gcd(a, b)$$$, and $$$gcd(b + 4c, b + 3c) = gcd(b + 3c, c) = gcd(b, c)$$$
It remains only to find such different $$$a, b, c$$$ such that $$$gcd(a, b) = gcd(b, c) = d$$$. There are many ways to choose them, but the easiest option is $$$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();
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

Square $$$2\times2$$$ we can color $$$14$$$ in ways: $$$2^4 - 2$$$ ($$$2^4$$$ this is the number of ways to color a square, 2 ways are incorrect when we turn the whole square either white or black). There are total of such squares $$$\frac{n^2}{4}$$$. So the answer is $$$14^\frac{n^2}{4}$$$. For a quick exponentiation, we use binary exponentiation.

#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';
    }
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

In the task, we are required to implement a stack with support for $$$gcd$$$

Let's learn how to answer each query for $$$\mathcal{O}(1)$$$ To do this, we will store a pair of numbers in the stack — the element itself, as well as $$$gcd$$$ elements lying in the stack no higher than this. In other words:
$$$stack_i.first = a_i$$$
$$$stack_i.second = gcd(a_1, a_2, ..., a_i)$$$
Then $$$gcd$$$ of the entire stack will be in $$$stack.top().second$$$
To make a deletion request, it is enough to delete the top element of the stack, since it does not affect the previous elements.
To add an element to the stack, we need to add a pair of $$$element,\;gcd(stack.top().second, element)$$$ (we must not forget to consider the case when the stack is empty)

#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';
    }
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Didn't decide:

First consider $$$x \le 11$$$. It's easy to make sure that only $$$8$$$ and $$$10$$$ are good ones. Next, $$$x \gt 11$$$ are considered.
Next, we note that one of the numbers $$$x-4$$$, $$$x-6$$$, $$$x-8$$$ will be composite, because it will be divisible by 3 (but not equal to three). Consequently, one of the pairs $$$(4, x-4)$$$, $$$(6, x-6)$$$, $$$(8, x-8)$$$ will fit, so the answer is always 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();
    }
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Didn't decide:

Solution 1:

Let's apply Goldbach's binary theorem (any even number starting from 4 can be represented as the sum of two primes). Then if 2 then the answer is $$$NO$$$. Otherwise, $$$YES$$$. Now note that an odd number is always the sum of an even number + an odd number. Since the only prime number is 2, it means we need to check that $$$x-2$$$ is prime.

Solution 2:

Let's use the Eratosthenes sieve to calculate all the primes up to $$$10^{6}$$$. It turns out that if there is such a $$$y$$$ that $$$y$$$ and $$$x - y$$$ are prime numbers, then $$$min(y, x - y) \le 600$$$. So you can iterate over the number y up to 600 and check with a sieve whether $$$x - y$$$ is simple.

#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();
    }
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

To begin with, we note that such a greedy algorithm is possible: while there are infected residents in the first city, we will fly on a segment of cities from $$$1$$$ to $$$k$$$ (otherwise we will not cure the first city in any way). After that, you can simply not fly over this city (since if we fly over it, we will not cure anyone in it, and it is better to start flying from the second city so that it is possible to treat residents in the $$$k + 1$$$ city. That is, we will remove the first city and solve the problem on the remaining cities (if we have k cities, then there will be only one way to cure all residents: let $$$x$$$ $$$-$$$ be the maximum number of infected residents in the city. Then add $$$\lceil{\frac{x}{k}}\rceil$$$ to the answer.

It remains only to quickly update the number of infected residents in cities from $$$l$$$ to $$$l + k - 1$$$ (when we fly over these cities). This can be done either through a tree of segments (then the asymptotics is $$$\mathcal{O}(n \cdot log(n))$$$, or you can store for each city how many segments begin in it and how many segments end in it, in the variable store how many segments contain the current city, then when switching to we add to this variable the number of segments starting in this city, and when considering it, we subtract from this variable the number of segments ending in the current city. When we count how many times we need to start flights in the

Unable to parse markup [type=CF_MATHJAX]

//#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;
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

To begin with, note that if $$$gcd(x, y) \gt 1$$$, then $$$gcd(x \cdot k, y) \gt 1$$$ for any natural $$$k$$$. It follows from this that if we build a graph of $$$n$$$ vertices, where two vertices are connected by an edge if $$$gcd$$$ of the corresponding numbers in the multiset $$$ \gt 1$$$, then during the game these vertices (and the edges of these vertices) will simply merge and will not change. Then the answer will simply be a set of multiplications of all the numbers in each component of the graph.

We need to learn how to build a graph quickly. In fact, we don't need a graph, we just need a partition into components in the graph. To do this, you can use the fast factorization of $$$n$$$ numbers (you can read about it on the Internet, but the bottom line is that for each number in the sieve of Eratosthenes, we will not store the simplicity of this number, but any prime number not equal to it, by which our number is divided. Then factorize the number $$$x$$$ in this way: let $$$f_x$$$$$$-$$$ be any prime number by which $$$x$$$ is divisible, while $$$f_x \lt x$$$. Then we add the number $$$f_x$$$ to our set of easy-to-decompose $$$x$$$ and we will continue to solve the problem for $$$\frac{x}{f_x}$$$). Then we will profactorize all $$$n$$$ numbers and combine them for each divisor (I did it through the DSU, but you can just store the graph, then the asymptotics will be reduced by $$$log(n)$$$ times). Next, for each set, we calculate the multiplication of the numbers in it by the desired modulus and output these numbers. The asymptotics of the author's solution is $$$\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 << ' ';
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Didn't decide:

We will search for the number of $$$r$$$ for each $$$l$$$ separately.

Let's forget about the condition $$$gcd(a_l, a_r) \gt 1$$$ for now. Then now the task is to find for each $$$l$$$ the minimum $$$r$$$ at which $$$gcd(a_l, a_{l + 1}, ...,a_r) = 1$$$ is executed. This can be done using bin-search, having previously written a tree of segments or sparse table to quickly find $$$gcd$$$ on a segment.

We have learned to find a suffix for each $$$l$$$ on which we can choose $$$r$$$. Now we need to quickly count on this suffix the number of $$$r$$$ such that $$$gcd(a_l, a_r) \gt 1$$$. Note that $$$2\le a_i\le 1000$$$, so we can calculate the number of $$$r$$$ on all suffixes for all possible $$$a_i$$$.
Let $$$dp_{x,i}$$$ be the number of numbers on the suffix $$$a_i, a_{i + 1}, ..., a_{n - 1}$$$ that are not mutually prime with x. As a base of dynamics, we will make $$$dp[x][n] = 0$$$. The dynamics is recalculated simply — $$$dp_{x,i} = dp_{x,i + 1} + (gcd(x, a_i) \gt 1)$$$. By calculating such dynamics for all $$$x$$$ from $$$2$$$ to $$$1000$$$, we will be able to quickly get the number of numbers we need on the suffix.

#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();
    }
}//

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved:

1 solution:

We will look for the answer from the end, assuming that upon arrival at the vertex n there will be exactly $$$t$$$ coins left. Then for $$$1$$$ step before arrival we will have $$$x$$$ coins such that $$$x - \frac{x}{w_1} \ge t$$$, and $$$x$$$ is minimal, for $$$2$$$ steps $$$y - \frac{y}{w_2} \ge x$$$, etc., where $$$w_1$$$ and $$$w_2$$$ are the weights of the roads from the optimal path. Let $$$d_i$$$ be the minimum number of coins that will be when we get from $$$n$$$ to $$$i$$$, then we can easily restore all the edge weights from $$$i$$$ in accordance with the inequality above. Now the task has been reduced to finding the shortest path from $$$n$$$ to $$$1$$$. To do this, you can use Dijkstra's algorithm (it works because the edges do not change randomly, and there are no negative edges).

2 solution:

We will search through the answer by bin-search: then we will make a regular Dijkstra for each possible answer (just the weights will change depending on the shortest path to the vertex). We check that the distance of the vertex $$$n$$$ is greater than or equal to $$$t$$$.

In both solutions, the asymptotics of $$$\mathcal{O}(n \cdot log(n) \cdot log(10^9))$$$.

The first solution is written in the code.

#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];
}

Great challenge:

Good task:

Normal task:

Bad task:

Disgusting task:

Not solved: