A. Time for Dinner

Le problème repose sur une séquence périodique de valeurs, où chaque bloc de taille p contient la valeur q. Pour déterminer si on peut atteindre une somme cible m avec n éléments, on calcule d'abord combien de blocs complets sont présents : u = n / p. Si n est divisible par p, alors la somme totale est u * q. Si cette somme égale m, la réponse est "YES", sinon "NO". Sinon, si n n'est pas un multiple de p, il reste un reste d = n % p. Dans ce cas, on peut toujuors ajuster la dernière partie pour atteindre m, donc la réponse est toujours "YES". Une attention particulière doit être portée aux valeurs négatives dans a_i, qui peuvent fausser le raisonnement initial.

#include <iostream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long n, m, p, q;
        cin >> n >> m >> p >> q;

        long long full_cycles = n / p;
        long long remainder = n % p;

        if (remainder == 0) {
            if (full_cycles * q == m)
                cout << "YES\n";
            else
                cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }

    return 0;
}

B. The Picky Cat

L'idée centrale est de tester les deux cas possibles pour la première valeur du tableau : a[1] ou -a[1]. Pour chaque cas, on analyse les autres éléments en fonction de leur distance par rapport à cette valeur. On distingue trois catégories : - Les éléments dont la valeur absolue est strictement inférieure à celle choisie. - Ceux dont la valeur absolue est strictement supérieure. - Ceux qui peuvent être soit plus petits, soit plus grands selon le choix. En triant les éléments, on cherche à savoir si la médiane peut être placée correctement. Cela revient à vérifier que le nombre d'éléments trop petits est inférieur ou égal au rang voulu de la médiane, et que le nombre d'éléments pouvant servir à remplir les positions avant la médiane est suffisant.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n + 1);
        for (int i = 1; i <= n; ++i)
            cin >> a[i];

        bool valid = false;
        long long candidate = abs(a[1]);

        // Essayer a[1] comme premier élément
        int low_count = 0, high_count = 0, mid_count = 0;
        for (int i = 2; i <= n; ++i) {
            long long val = abs(a[i]);
            if (val < candidate) low_count++;
            else if (val > candidate) high_count++;
            else mid_count++;
        }
        int median_pos = (n + 1) / 2 - 1; // position 0-based de la médiane
        if (low_count <= median_pos && low_count + mid_count >= median_pos)
            valid = true;

        // Essayer -a[1]
        low_count = high_count = mid_count = 0;
        for (int i = 2; i <= n; ++i) {
            long long val = abs(a[i]);
            if (val < candidate) low_count++;
            else if (val > candidate) high_count++;
            else mid_count++;
        }
        if (low_count <= median_pos && low_count + mid_count >= median_pos)
            valid = true;

        cout << (valid ? "YES" : "NO") << '\n';
    }

    return 0;
}

C. Mex in the Grid

La stratégie consiste à remplir une grille carrée de taille n × n en spirale, en commençant par le coin supérieur gauche et en allant vers l’intérieur. L’objectif est d’obtenir un maximum de Mex (minimum des entiers non présents), qui est optimisé par une distribution uniforme. La construction en spirale garantit que les valeurs décroissent progressivement depuis le bord extérieur vers le centre, assurant ainsi une bonne répartition.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<vector<long long>> grid(n + 1, vector<long long>(n + 1, 0));

        long long value = n * n - 1;
        int top = 1, bottom = n, left = 1, right = n;

        while (top <= bottom && left <= right) {
            // Remplir le haut
            for (int col = left; col <= right; ++col)
                grid[top][col] = value--;
            top++;

            // Remplir le droit
            for (int row = top; row <= bottom; ++row)
                grid[row][right] = value--;
            right--;

            // Remplir le bas
            if (top <= bottom)
                for (int col = right; col >= left; --col)
                    grid[bottom][col] = value--;
            bottom--;

            // Remplir la gauche
            if (left <= right)
                for (int row = bottom; row >= top; --row)
                    grid[row][left] = value--;
            left++;
        }

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j)
                cout << grid[i][j] << ' ';
            cout << '\n';
        }
    }

    return 0;
}

D. Quartet Swapping

Ce problème exige un tri par permutation circulaire entre éléments aux positions paires et impaires. Chaque opération permute deux éléments situés aux indices pairs ou impairs. La solution optimale utilise une approche par simulation via une liste chaînée pour maintenir efficacement les positions relatives. On trie les éléments impairs et pairs indépendamment, puis on vérifie si le nombre total d'inversions conserve la même parité. Si non, on effectue une permutation finale sur les derniers éléments selon la parité de n.

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

const int MAXN = 2e5 + 5;

int lowbit(int x) { return x & -x; }

void add(vector<int>& fenw, int idx, int delta) {
    for (int i = idx; i < MAXN; i += lowbit(i))
        fenw[i] += delta;
}

int query(vector<int>& fenw, int idx) {
    int res = 0;
    for (int i = idx; i > 0; i -= lowbit(i))
        res += fenw[i];
    return res;
}

int inversion_count(vector<int>& arr) {
    vector<int> fenw(MAXN, 0);
    int inv = 0;
    for (int i = 0; i < arr.size(); ++i) {
        add(fenw, arr[i], 1);
        inv += query(fenw, arr[i] - 1);
    }
    return inv;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> odd, even;
        for (int i = 1; i <= n; ++i) {
            int x;
            cin >> x;
            if (i % 2 == 1) odd.push_back(x);
            else even.push_back(x);
        }

        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());

        int odd_inv = inversion_count(odd);
        int even_inv = inversion_count(even);

        if ((odd_inv % 2) != (even_inv % 2)) {
            if (n % 2 == 1)
                swap(odd[odd.size()-1], odd[odd.size()-2]);
            else
                swap(even[even.size()-1], even[even.size()-2]);
        }

        int o = 0, e = 0;
        for (int i = 1; i <= n; ++i) {
            if (i % 2 == 1)
                cout << odd[o++] << ' ';
            else
                cout << even[e++] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

E. Kingdom of 23

On cherche à maximiser la différence entre la somme des dernières occurrences et celle des premières occurrences de chaque nombre. On parcourt le tableau de gauche à droite en maintenant un ensemble trié des nombres encore disponibles. À chaque étape, on sélectionne le plus grand nombre ≤ a[i], ce qui garantit une allocation optimale. On stocke les indices de première occurrence dans un tableau préfixe, et ceux de dernière occurrence dans un tableau suffixe. Enfin, on calcule la somme des différences positives entre ces deux tableaux.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i)
            cin >> a[i];

        set<int> available;
        for (int i = 1; i <= n; ++i)
            available.insert(i);

        vector<int> first_occurrence(n + 1, 0), last_occurrence(n + 1, 0);
        int cnt = 1;

        // Précédent : première occurrence
        for (int i = 1; i <= n; ++i) {
            auto it = available.upper_bound(a[i]);
            if (it != available.begin()) {
                --it;
                first_occurrence[cnt++] = i;
                available.erase(it);
            }
        }

        // Suffixe : dernière occurrence
        available.clear();
        for (int i = 1; i <= n; ++i)
            available.insert(i);

        cnt = 1;
        for (int i = n; i >= 1; --i) {
            auto it = available.upper_bound(a[i]);
            if (it != available.begin()) {
                --it;
                last_occurrence[cnt++] = i;
                available.erase(it);
            }
        }

        long long result = 0;
        for (int i = 1; i <= n; ++i)
            result += max(0LL, (long long)last_occurrence[i] - first_occurrence[i]);

        cout << result << '\n';
    }

    return 0;
}