A – Calendar Game

Ignoring the year, the losing positions follow the pattern (month + day) % 2 == 1, except for the two special dates 9/30 and 11/30 which allow the next player to flip the parity.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;  cin >> t;
    while (t--) {
        int y, m, d;  cin >> y >> m >> d;
        bool win = (m == 9 && d == 30) || (m == 11 && d == 30) || ((m + d) % 2 == 0;
        cout << (win ? "YES\n" : "NO\n");
    }
}

B – Student Grouping

Let avg = total / n. If avg ∉ [L, R] output -1. Otherwise the minimal moves are max(Σ(L - a[i])⁺, Σ(a[i] - R)⁺).

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;  cin >> n;
    vector<int> a(n);
    int64 sum = 0;
    for (int &x : a) { cin >> x; sum += x; }
    int64 L, R;  cin >> L >> R;
    if (sum < L * n || sum > R * n) { cout << -1 << '\n'; return 0; }
    int64 needL = 0, needR = 0;
    for (int x : a) {
        if (x < L) needL += L - x;
        if (x > R) needR += x - R;
    }
    cout << max(needL, needR) << '\n';
}

C – Collecting Cards

Sort edges descending by weight. Use a DSU with 2n nodes: x and x+n represent the two possible groups. The first edge whose endpoints are already in the same group gives the answer.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct DSU {
    vector<int> p;
    DSU(int n) : p(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        p[b] = a; return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;  cin >> n >> m;
    vector<tuple<int64,int,int>> e(m);
    for (auto &[w,u,v] : e) cin >> u >> v >> w;
    sort(e.rbegin(), e.rend());
    DSU dsu(2 * n + 2);
    int64 ans = 0;
    for (auto [w,u,v] : e) {
        if (dsu.find(u) == dsu.find(v)) { ans = w; break; }
        dsu.unite(u, v + n);
        dsu.unite(v, u + n);
    }
    cout << ans << '\n';
}

D – Range Add & Point Query

A segment tree with lazy propagation supporting range add and point query.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct Node { int l, r; int64 sum, tag; };

struct SegTree {
    vector<Node> t;
    SegTree(int n) : t(4 * n) { build(1, 1, n); }
    void build(int p, int l, int r) {
        t[p].l = l; t[p].r = r; t[p].tag = 0;
        if (l == r) { cin >> t[p].sum; return; }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    }
    void push(int p) {
        if (!t[p].tag) return;
        int l = p << 1, r = p << 1 | 1;
        t[l].sum += t[p].tag * (t[l].r - t[l].l + 1);
        t[r].sum += t[p].tag * (t[r].r - t[r].l + 1);
        t[l].tag += t[p].tag; t[r].tag += t[p].tag;
        t[p].tag = 0;
    }
    void add(int p, int l, int r, int v) {
        if (l <= t[p].l && t[p].r <= r) {
            t[p].sum += int64(v) * (t[p].r - t[p].l + 1);
            t[p].tag += v; return;
        }
        push(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid) add(p << 1, l, r, v);
        if (r > mid) add(p << 1 | 1, l, r, v);
        t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
    }
    int64 ask(int p, int pos) {
        if (t[p].l == t[p].r) return t[p].sum;
        push(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (pos <= mid) return ask(p << 1, pos);
        return ask(p << 1 | 1, pos);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;  cin >> n;
    SegTree st(n);
    cin >> q;
    while (q--) {
        int op; cin >> op;
        if (op == 1) {
            int l, r, d; cin >> l >> r >> d;
            st.add(1, l, r, d);
        } else {
            int x; cin >> x;
            cout << st.ask(1, x) << '\n';
        }
    }
}

E – Goldbach Triple

Generate all primes up to 50 000, then for each query iterate pairs and check if the remainder is prime.

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

const int N = 50000;
vector<int> primes;
bitset<50001> vis;
void sieve() {
    for (int i = 2; i <= 50000; ++i) {
        if (!vis[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > 50000) break;
            vis[i * p] = 1;
            if (i % p == 0) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    sieve();
    int t;  cin >> t;
    while (t--) {
        int n;  cin >> n;
        bool ok = false;
        for (int a : primes) {
            if (a > n) break;
            for (int b : primes) {
                if (a + b > n) break;
                int c = n - a - b;
                if (c >= 2 && !vis[c]) {
                    cout << a << ' ' << b << ' ' << c << '\n';
                    ok = true; goto nxt;
                }
            }
        }
        nxt: if (!ok) cout << -1 << '\n';
    }
}

F – Round-Trip Distances

Run Dijkstra from vertex 1 on the original graph to get forward distances, then on the reversed graph to get backward distances. Sum the two arrays.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct Graph {
    int n;
    vector<vector<pair<int,int>>> g;
    Graph(int n) : n(n), g(n + 1) {}
    void add(int u, int v, int w) { g[u].emplace_back(v, w); }
    vector<int64> dijkstra(int s) {
        vector<int64> d(n + 1, LLONG_MAX);
        priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
        d[s] = 0; pq.emplace(0, s);
        while (!pq.empty()) {
            auto [dist, u] = pq.top(); pq.pop();
            if (dist != d[u]) continue;
            for (auto [v, w] : g[u]) {
                if (d[v] > d[u] + w) {
                    d[v] = d[u] + w;
                    pq.emplace(d[v], v);
                }
            }
        }
        return d;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;  cin >> n >> m;
    Graph g1(n), g2(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;  cin >> u >> v >> w;
        g1.add(u, v, w);
        g2.add(v, u, w);
    }
    auto d1 = g1.dijkstra(1);
    auto d2 = g2.dijkstra(1);
    int64 ans = 0;
    for (int i = 2; i <= n; ++i) ans += d1[i] + d2[i];
    cout << ans << '\n';
}

G – Staircase DP

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] with base cases dp[1]=1, dp[2]=2, dp[3]=4.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;  cin >> n;
    vector<int64> dp(n + 1);
    dp[0] = 1; dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % MOD;
    cout << dp[n] << '\n';
}

H – Static RMQ

Fast I/O + Sparse Table for O(1) range maximum queries.

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int st[N][20];

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) st[i][0] = read();
    for (int j = 1; j < 20; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
    int q = read();
    while (q--) {
        int l = read(), r = read();
        int k = __lg(r - l + 1);
        printf("%d\n", max(st[l][k], st[r - (1 << k) + 1][k]));
    }
}

I – Optimal Tap Position

The median minimizes the sum of absolute deviations.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;  cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    nth_element(a.begin(), a.begin() + n / 2, a.end());
    int med = a[n / 2];
    int64 ans = 0;
    for (int x : a) ans += abs(x - med);
    cout << ans << '\n';
}

J – Integer Square Root

floor(sqrt(n)).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;  cin >> t;
    while (t--) {
        long long n;  cin >> n;
        cout << (long long)sqrt(n) << '\n';
    }
}

K – Minimax Path

Dijkstra where the distance to a node is the maximum edge weight on the best path from the source.

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;  cin >> n >> m;
    vector<vector<pair<int,int>>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;  cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    int s, t;  cin >> s >> t;
    vector<int64> d(n + 1, LLONG_MAX);
    priority_queue<pair<int64,int>, vector<pair<int64,int>>, greater<pair<int64,int>>> pq;
    d[s] = 0; pq.emplace(0, s);
    while (!pq.empty()) {
        auto [dist, u] = pq.top(); pq.pop();
        if (dist != d[u]) continue;
        for (auto [v, w] : g[u]) {
            int64 nd = max(d[u], (int64)w);
            if (nd < d[v]) {
                d[v] = nd;
                pq.emplace(d[v], v);
            }
        }
    }
    cout << d[t] << '\n';
}