Problème A – Déplacement optimal sur une ligne

On dispose d’un point situé en x et d’une cible en y. À chaque seconde on peut avancer d’au plus k unités. Le coût est simplement la position finale. Si x ≥ y, on atteint déjà la cible ; sinon on avance jusqu’à min(y, x+k) puis on rebrousse chemin pour atteindre y. Le temps total est donc y + (y - min(y, x+k)).

#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 x, y, k;
        cin >> x >> y >> k;
        if (x >= y) cout << x << '\n';
        else        cout << y + max(0LL, y - (x + k)) << '\n';
    }
}

Problème B – Partition d’un tableau en deux sous-séquences équilibrées

Étant donné 2n entiers, on veut les répartir en deux groupes de taille n de façon à minimiser la somme des écarts absolus entre éléments consécutifs dans chaque groupe. Il suffit de trier le tableau et de prendre les n plus petits dans un groupe et les n plus grands dans l’autre ; la preuve repose sur l’inégalité des réarrangements.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc;  cin >> tc;
    while (tc--) {
        int n;  cin >> n;
        vector<int> v(2 * n);
        for (int &x : v) cin >> x;
        sort(v.begin(), v.end());

        long long cost = 0;
        for (int i = 1; i < n; ++i) cost += v[i] - v[i - 1];
        for (int i = n + 1; i < 2 * n; ++i) cost += v[i] - v[i - 1];
        cout << cost << '\n';
        for (int i = 0; i < n; ++i)
            cout << v[i] << " \n"[i == n - 1];
        for (int i = 0; i < n; ++i)
            cout << v[i + n] << " \n"[i == n - 1];
    }
}

Problème C – Appariements de chaînes numériques équilibrées

Une chaîne est « équilibrée » si, une fois coupée en deux parties de même longueur, la somme des chiffres de la première moitié égale celle de la seconde. Étant donné n chaînes, on compte les paires (i, j) (l’ordre compte, i = j autorisé) telles que la concaténation s<sub>i</sub> + s<sub>j</sub> soit équilibrée.

On remarque que seules la longueur et la somme des chiffres d’une chaîne importe. On maintient un tableau freq[len][sum] et on parcourt chaque chaîne pour déterminer avec quelles longueurs complémentaires elle peut s’apparier.

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

int freq[10][500];          // len <= 5, sum <= 9*5

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;  cin >> n;
    vector<string> s(n);
    vector<int> sum(n);

    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        int cur = 0;
        for (char c : s[i]) cur += c - '0';
        sum[i] = cur;
        ++freq[(int)s[i].size()][cur];
    }

    long long total = 0;
    for (int i = 0; i < n; ++i) {
        int len = (int)s[i].size();
        int pref = 0;
        for (int cut = 1; cut < len; ++cut) {
            pref += s[i][cut - 1] - '0';
            int need = 2 * pref - sum[i];
            int other = 2 * cut - len;
            if (other > 0 && other <= 5)
                total += freq[other][need];
        }
        pref = 0;
        for (int cut = len - 1; cut > 0; --cut) {
            pref += s[i][cut] - '0';
            int need = 2 * pref - sum[i];
            int other = len - 2 * cut;
            if (other > 0 && other <= 5)
                total += freq[other][need];
        }
    }
    cout << total + n << '\n';
}

Problème D – Reconstruction d’un tableau à partir de XOR adjacents

On connaît a<sub>1</sub>, …, a<sub>n-1</sub> avec a<sub>i</sub> = b<sub>i</sub> XOR b<sub>i+1</sub>. Il faut produire b<sub>1</sub>, …, b<sub>n</sub> distincts et compris entre 0 et n-1.

En posant s<sub>k</sub> = a<sub>1</sub> XOR … XOR a<sub>k</sub>, on obtient b<sub>k+1</sub> = s<sub>k</sub> XOR b<sub>1</sub>. Reste à choisir b<sub>1</sub> tel que l’ensemble {b<sub>1</sub>, s<sub>1</sub> XOR b<sub>1</sub>, …} soit exactement {0, 1, …, n-1}. On utilise un Trie binaire pour tester rapidement, en O(log n) par candidat, si le maximum obtenu reste inférieur à n.

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

const int LG = 20;
struct Trie {
    int ch[2]{}, cnt = 0;
} tr[LG * 200000];
int nodes = 1;

void insert(int x) {
    int cur = 0;
    for (int b = LG - 1; b >= 0; --b) {
        int bit = (x >> b) & 1;
        if (!tr[cur].ch[bit]) tr[cur].ch[bit] = nodes++;
        cur = tr[cur].ch[bit];
    }
}

int max_xor(int x) {
    int cur = 0, res = 0;
    for (int b = LG - 1; b >= 0; --b) {
        int bit = (x >> b) & 1;
        if (tr[cur].ch[!bit]) {
            res |= 1 << b;
            cur = tr[cur].ch[!bit];
        } else {
            cur = tr[cur].ch[bit];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;  cin >> n;
    vector<int> a(n - 1);
    for (int &x : a) cin >> x;

    vector<int> pref(n);
    for (int i = 1; i < n; ++i) pref[i] = pref[i - 1] ^ a[i - 1];
    for (int v : pref) insert(v);

    int b0 = 0;
    for (int cand = 0; cand < n; ++cand)
        if (max_xor(cand) < n) { b0 = cand; break; }

    cout << b0;
    for (int i = 1; i < n; ++i) cout << ' ' << (b0 ^ pref[i]);
    cout << '\n';
}