A - Range Product

L'objectif est de déterminer le signe du produit des entiers compris dans l'intervalle $[a, b]$. Nous pouvons diviser le problème en trois scénarios distincts :

• Si $a \le 0 \le b$, l'intervalle contient zéro, donc le produit est Zero.
• Si $a > 0$, tous les nombres sont positifs, le produit est donc Positive.
• Si $b < 0$, tous les nombres sont négatifs. Le nombre d'éléments est $b - a + 1$. Si ce nombre est pair, le produit est Positive, sinon il est Negative.

#include <iostream>
#include <string>

int main() {
    long long debut, fin;
    if (!(std::cin >> debut >> fin)) return 0;

    if (debut <= 0 && fin >= 0) {
        std::cout << "Zero" << std::endl;
    } else if (debut > 0) {
        std::cout << "Positive" << std::endl;
    } else {
        long long nb_elements = fin - debut + 1;
        std::cout << (nb_elements % 2 == 0 ? "Positive" : "Negative") << std::endl;
    }
    return 0;
}

B - Box and Ball

Nous devons suivre le mouvement potentiel d'une unique balle rouge parmi $N$ boîtes. Initialement, la balle rouge est dans la boîte 1. À chaque opération de transfert d'une balle de la boîte $u$ vers $v$ :

• Si la boîte $u$ contient potentiellement la balle rouge, alors après le transfert, la boîte $v$ peut aussi la contenir.
• On décrémente le nombre de balles dans $u$ et on l'incrémente dans $v$.
• Si le nombre de balles dans $u$ tombe à zéro, elle ne peut plus contenir la balle rouge.

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> quantite(n + 1, 1);
    std::vector<bool> peut_contenir(n + 1, false);
    peut_contenir[1] = true;

    for (int i = 0; i < m; ++i) {
        int de, vers;
        std::cin >> de >> vers;
        if (peut_contenir[de]) {
            peut_contenir[vers] = true;
        }
        quantite[de]--;
        quantite[vers]++;
        if (quantite[de] == 0) {
            peut_contenir[de] = false;
        }
    }

    int resultat = 0;
    for (int i = 1; i <= n; ++i) {
        if (peut_contenir[i]) resultat++;
    }
    std::cout << resultat << std::endl;
    return 0;
}

C - Knot Puzzle

Le problème demande s'il est possible de dénouer toutes les cordes. La condition critique est que pour dénouer deux segments adjacents de longueurs $a_i$ et $a_{i+1}$, leur somme doit être au moins $L$.

En observant le problème à l'envers, si nous trouvons une paire adjacente $(j, j+1)$ telle que $a_j + a_{j+1} \ge L$, nous pouvons faire de cette coupe la toute dernière. Toutes les autres coupes peuvent être effectuées avant, car elles ne feront que réduire la longueur totale de la corde restante sans affecter cette paire spécifique. L'ordre sera : couper de 1 à $j-1$, puis de $n-1$ à $j+1$, et enfin couper $j$.

#include <iostream>
#include <vector>

int main() {
    int n;
    long long l;
    std::cin >> n >> l;
    std::vector<long long> segments(n + 1);
    int indice_critique = -1;

    for (int i = 1; i <= n; ++i) {
        std::cin >> segments[i];
        if (i > 1 && segments[i] + segments[i-1] >= l) {
            indice_critique = i - 1;
        }
    }

    if (indice_critique == -1) {
        std::cout << "Impossible" << std::endl;
    } else {
        std::cout << "Possible" << std::endl;
        for (int i = 1; i < indice_critique; ++i) std::cout << i << "\n";
        for (int i = n - 1; i > indice_critique; --i) std::cout << i << "\n";
        std::cout << indice_critique << std::endl;
    }
    return 0;
}

D - Stamp Rally

Pour chaque requête $(x, y, z)$, nous cherchons le plus petit indice d'arête $M_i$ tel que les composantes connexes contenant $x$ et $y$ possèdent au total au moins $z$ sommets distincts.

Une approche efficace utilise la recherche dichotomique parallèle ou un Union-Find persistant. Ici, nous utilisons un Union-Find où chaque nœud enregistre le momant (timestamp) de sa fusion. Pour vérifier l'état à un temps $t$, nous remontons l'arbre tant que le timestamp de l'arête est $\le t$.

#include <iostream>
#include <vector>
#include <algorithm>

struct DSU_Persistant {
    std::vector<std::pair<int, int>> parent;
    std::vector<std::vector<std::pair<int, int>>> taille;
    
    DSU_Persistant(int n) {
        parent.resize(n + 1);
        taille.resize(n + 1);
        for(int i = 1; i <= n; ++i) {
            parent[i] = {0, i};
            taille[i].push_back({0, 1});
        }
    }

    int trouver_racine(int t, int u) {
        if (parent[u].second == u || parent[u].first > t) return u;
        return trouver_racine(t, parent[u].second);
    }

    void unir(int t, int u, int v) {
        int r1 = trouver_racine(1e9, u), r2 = trouver_racine(1e9, v);
        if (r1 == r2) return;
        if (taille[r1].back().second > taille[r2].back().second) std::swap(r1, r2);
        int nouvelle_taille = taille[r1].back().second + taille[r2].back().second;
        taille[r2].push_back({t, nouvelle_taille});
        parent[r1] = {t, r2};
    }

    int obtenir_taille(int t, int u) {
        auto it = std::upper_bound(taille[u].begin(), taille[u].end(), std::make_pair(t, (int)2e9));
        return std::prev(it)->second;
    }
};

int main() {
    int n, m;
    std::cin >> n >> m;
    DSU_Persistant dsu(n);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        std::cin >> u >> v;
        dsu.unir(i, u, v);
    }

    int q;
    std::cin >> q;
    while (q--) {
        int x, y, z;
        std::cin >> x >> y >> z;
        int gauche = 1, droite = m, rep = m;
        while (gauche <= droite) {
            int milieu = (gauche + droite) / 2;
            int rx = dsu.trouver_racine(milieu, x), ry = dsu.trouver_racine(milieu, y);
            int total = (rx == ry) ? dsu.obtenir_taille(milieu, rx) : dsu.obtenir_taille(milieu, rx) + dsu.obtenir_taille(milieu, ry);
            if (total >= z) {
                rep = milieu;
                droite = milieu - 1;
            } else {
                gauche = milieu + 1;
            }
        }
        std::cout << rep << "\n";
    }
    return 0;
}

E - Candy Piles

Le jeu peut être modélisé géométriquement. En triant les piles $a_i$ par ordre décroissant, nous obtenons une structure d'histogramme. Le jeu consiste à supprimer soit la ligne du bas, soit la colonne la plus à gauche. Cela reviant à déplacer un jeton sur une grille de $(0,0)$ vers les bords.

Un état $(i, j)$ est perdant si tous ses voisins immédiats (haut et droite) sont des états gagnants. Par observation des diagonales, on peut simplifier la recherche de l'état de victoire en vérifiant la parité des distances jusqu'aux bords de l'histogramme depuis la diagonale principale.

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) std::cin >> a[i];
    std::sort(a.rbegin(), a.rend());

    int k = 0;
    while (k + 1 < n && a[k+1] > k + 1) k++;

    int horizontal = 0;
    for (int i = k + 1; i < n; ++i) {
        if (a[i] > k) horizontal++;
        else break;
    }
    
    int vertical = a[k] - (k + 1);
    if (vertical % 2 == 1 || horizontal % 2 == 1) {
        std::cout << "First" << std::endl;
    } else {
        std::cout << "Second" << std::endl;
    }
    return 0;
}

F - Leftmost Ball

Nous utilisons la programmation dynamique. Soit $dp[i][j]$ le nombre de façons de placer $i$ balles blanches et d'avoir déjà utilisé $j$ couleurs (pour lesquelles les $K-1$ balles restantes ont été placées). La condition est $i \ge j$.

Transitions : 1. Ajouter une balle blanche : $dp[i-1][j]$. 2. Ajouter une nouvelle couleur : $dp[i][j-1] \times (N - j + 1) \times \binom{NK - i - (j-1)(K-1) - 1}{K-2}$. Le terme binomial correspond au choix des positions pour les $K-2$ balles restantes de la couleur choisei parmi les emplacements vides.

#include <iostream>
#include <vector>

using namespace std;
long long MOD = 1e9 + 7;

long long puissance(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long inverse(long long n) {
    return puissance(n, MOD - 2);
}

vector<long long> fact;
void precalcul(int n) {
    fact.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inverse(fact[r]) % MOD * inverse(fact[n - r]) % MOD;
}

int main() {
    int N, K;
    cin >> N >> K;
    if (K == 1) {
        cout << 1 << endl;
        return 0;
    }
    precalcul(N * K);
    vector<vector<long long>> dp(N + 1, vector<long long>(N + 1, 0));

    for (int i = 0; i <= N; i++) dp[i][0] = 1;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j]; // Balle blanche
            long long choix_pos = nCr(N * K - i - (j - 1) * (K - 1) - 1, K - 2);
            long long couleurs_restantes = N - j + 1;
            dp[i][j] = (dp[i][j] + dp[i][j - 1] * couleurs_restantes % MOD * choix_pos) % MOD;
        }
    }

    cout << dp[N][N] << endl;
    return 0;
}