Problem A – The Simple Tournament

We can derive a direct formula: The total number of matches is always 2n - 2. The reasoning: from the winners' bracket, n - 1 teams drop to the losers' bracket, from which n - 2 teams are eliminated, leaving two teams that play one final match. Alternatively, a straightforward simulation also works.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int winners = n, losers = 0, total = 0;
        while (winners > 1) {
            int half = winners / 2;
            total += half;
            losers += half;
            winners -= half;
        }
        while (losers > 1) {
            total += losers / 2;
            losers -= losers / 2;
        }
        total += 1;               // final match
        cout << total << "\n";
    }
    return 0;
}

Problem B – Abraham's Great Escape

We need to place directions on an n×n grid. If only one cell is blocked (k = n*n - 1), there is no solution. Otherwise, we construct a ‘LR’ cycle using two adjacent cells, then use ‘L’ on the first row to point into the cycle, and ‘U’ on the rows below to point upward, leaving all other cells as ‘D’. The code below implements this construction.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, blocked; cin >> n >> blocked;
        int freeCells = n * n - blocked;
        if (freeCells == 1) {
            cout << "NO\n";
            continue;
        }
        vector<string> grid(n, string(n, 'D'));
        freeCells -= 2;
        grid[0][0] = 'R'; grid[0][1] = 'L';
        int col = 2;
        while (col < n && freeCells > 0) {
            grid[0][col] = 'L';
            col++; freeCells--;
        }
        int row = 1;
        while (row < n && freeCells > 0) {
            for (int c = 0; c < n && freeCells > 0; c++) {
                grid[row][c] = 'U';
                freeCells--;
            }
            row++;
        }
        cout << "YES\n";
        for (const auto& line : grid) cout << line << "\n";
    }
    return 0;
}

Problem C – The Ancient Wizards' Capes

We are given an array a where ai counts how many capes are visible from cell i. The difference between consecutive a values cannot exceed 1; otherwise the answer is 0. The only possible sequences of directions are generated by fixing the first cell’s direction and then deducing the rest: if ai = ai-1, the directions must be opposite; if ai > ai-1, the direction must be left (0); otherwise right (1). We check both initial choices and verify for each cell whether the number of visible cells on the left plus visible cells on the right equals ai. A segment tree is used to quickly count left‑facing and right‑facing cells in any itnerval.

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

struct Info {
    int cnt[2] = {0,0};
};
Info operator+(const Info& l, const Info& r) {
    return {l.cnt[0] + r.cnt[0], l.cnt[1] + r.cnt[1]};
}

template<class T>
class SegTree {
    int n;
    vector<T> tree;
public:
    SegTree(int _n) : n(_n), tree(4 << __lg(_n)) {}
    void set(int pos, const T& val) { set(1, 0, n, pos, val); }
    T query(int l, int r) { return query(1, 0, n, l, r); }
private:
    void pull(int p) { tree[p] = tree[2*p] + tree[2*p+1]; }
    void set(int p, int L, int R, int pos, const T& val) {
        if (R - L == 1) { tree[p] = val; return; }
        int M = (L + R) / 2;
        if (pos < M) set(2*p, L, M, pos, val);
        else set(2*p+1, M, R, pos, val);
        pull(p);
    }
    T query(int p, int L, int R, int ql, int qr) {
        if (qr <= L || R <= ql) return T();
        if (ql <= L && R <= qr) return tree[p];
        int M = (L + R) / 2;
        return query(2*p, L, M, ql, qr) + query(2*p+1, M, R, ql, qr);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n);
        for (auto& x : a) cin >> x;
        bool impossible = false;
        for (int i = 1; i < n; ++i)
            if (abs(a[i] - a[i-1]) > 1) { impossible = true; break; }
        if (impossible) { cout << "0\n"; continue; }
        int good = 0;
        for (int start = 0; start < 2; ++start) {
            SegTree<Info> seg(n);
            vector<int> dir(n);
            dir[0] = start;
            seg.set(0, {start==0 ? 1:0, start==1 ? 1:0});
            for (int i = 1; i < n; ++i) {
                if (a[i] == a[i-1]) dir[i] = dir[i-1] ^ 1;
                else if (a[i] > a[i-1]) dir[i] = 0;
                else dir[i] = 1;
                seg.set(i, {dir[i]==0 ? 1:0, dir[i]==1 ? 1:0});
            }
            bool ok = true;
            for (int i = 0; i < n; ++i) {
                Info left = seg.query(0, i);
                Info right = seg.query(i+1, n);
                int visible = left.cnt[0] + right.cnt[1];
                if (visible != a[i]) { ok = false; break; }
            }
            if (ok) ++good;
        }
        cout << good << "\n";
    }
    return 0;
}

Problem D – Battteries

Place the batteries on a circle. We repeatedly query pairs with a fixed distance i (1 ≤ i ≤ n). For a given distanec, we test all starting positions j and ask whether the two batteries at positions j and (j+i) mod n are both good. If goodCount = a, the maximum minimal distance between two good batteries is at most ⌊n/a⌋. Therefore we will find a pair in at most n × ⌊n/a⌋ queries, which satisfies the limit ⌊n²/a⌋.

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

bool ask(int x, int y) {
    cout << x << " " << y << endl;
    int res; cin >> res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        for (int dist = 1; dist <= n; ++dist) {
            for (int start = 1; start <= n; ++start) {
                int nxt = start + dist;
                if (nxt > n) nxt -= n;
                if (ask(start, nxt)) goto found;
            }
        }
        found:;
    }
    return 0;
}