Vous disposez de N masses, chacune ayant un poids unique A_1, A_2, ..., A_N. Votre tâche consiste à placer chaque masse sur un plateau d'une balance (gauche ou droite) dans un ordre spécifique. Une chaîne de caractères S de longueur N indique la condition d'équilibre à respecter après le placement de la i-ème masse : 'L' signifie que le plateau gauche doit être plus lourd, et 'R' signifie que le plateau droit doit être plus lourd. L'objectif est de trouver une séquence de placement des masses et leur côté respectif qui satisfasse toutes les conditions de S.

Stratégie de Résolution L'absence de cas "impossible" dans les exemples suggère qu'une solution existe toujours. L'approche consiste à trier les masses A par ordre croissant. Ensuite, nous allons raisonner à rebours, en déterminant quelle masse a été placée en dernier, puis l'avant-dernière, et ainsi de suite jusqu'à la première.

Initialement, nous distribuons les masses triées en deux groupes conceptuels : le groupe G1 (représentant les masses potentielles pour le côté gauche) reçoit A_1, A_3, A_5, ... et le groupe G2 (pour le côté droit) reçoit A_2, A_4, A_6, .... Ces groupes sont gérés comme des double-ended queues (deques) pour permettre des extractions efficaces aux deux extrémités.

La clé est d'aligner la distribution initiale avec la contrainte finale S[N]. Si la parité de N implique que G1 devrait être le côté le plus lourd, mais S[N] exige que G2 le soit, nous inversons simplement les deux groupes. À partir de ce point, G1 représentera le côté "gauche" et G2 le côté "droit" par rapport à l'état désiré pour S[N].

Nous parcourons les contraintes de S de N à 1. Pour chaque étape i :

1. Nous examinons si la condition d'équilibre change entre l'étape i-1 et l'étape i. Soit inverse_necessaire cette information (vrai si S[i] != S[i-1], faux sinon).
2. Si inverse_necessaire est vrai (le plateau dominant doit changer) : Pour que le retrait de la i-ème masse inverse l'équilibre, cette masse doit avoir été l'une des plus lourdes parmi celles disponibles dans les deux groupes. Nous comparons la plus grande masse de G1 (G1.back()) et la plus grande de G2 (G2.back()). Nous choisissons la plus grande des deux. Le fait de retirer une masse lourde aura un impact significatif et peut inverser l'équilibre.
3. Si inverse_necessaire est faux (le plateau dominant doit rester le même) : Pour que le retrait de la i-ème masse maintienne l'équilibre, cette masse doit avoir été l'une des plus légères parmi celles disponibles. Nous comparons la plus petite masse de G1 (G1.front()) et la plus petite de G2 (G2.front()). Nous choisissons la plus petite des deux. Retirer une masse légère a un impact minimal sur la direction de l'équilibre. La masse choisie à l'étape i est enregistrée avec le côté d'où elle a été retirée. Nous poursuivons ce processus jusqu'à i=1.

Implémentation Le code utilise deux std::deque<int></int>, nommées cotesGauche et cotesDroite, pour gérer les masses disponibles. Un tableau de booléens estCoteGauchePlusLourd enregistre la contrainte S. Le résultat est stocké dans un tableau de paires (masse, cote).

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <deque>

struct MassePlacee {
    int poids;
    char cote;
};

void resoudre() {
    int nombreMasses;
    std::cin >> nombreMasses;

    std::vector<int> poidsMasses(nombreMasses);
    for (int i = 0; i < nombreMasses; ++i) {
        std::cin >> poidsMasses[i];
    }
    std::sort(poidsMasses.begin(), poidsMasses.end());

    std::string sequenceDesiree;
    std::cin >> sequenceDesiree;

    std::vector<bool> estCoteGauchePlusLourd(nombreMasses + 1); // 1-indexed
    for (int i = 0; i < nombreMasses; ++i) {
        estCoteGauchePlusLourd[i + 1] = (sequenceDesiree[i] == 'L');
    }

    std::deque<int> cotesGauche, cotesDroite;
    for (int i = 0; i < nombreMasses; ++i) {
        if ((i + 1) % 2 != 0) { // Masses impaires vers le groupe "gauche" initial
            cotesGauche.push_back(poidsMasses[i]);
        } else { // Masses paires vers le groupe "droit" initial
            cotesDroite.push_back(poidsMasses[i]);
        }
    }

    // Ajuster les groupes en fonction de la contrainte finale S[N]
    // Si la contrainte finale indique que le côté lourd ne correspond pas à notre distribution initiale pour le groupe "gauche"
    // (i.e., si N est impair, G1 est naturellement plus lourd, si S[N] est 'R', il faut inverser)
    // C'est flag[N] vs (N&1) en C++. Ici, flag[N] est estCoteGauchePlusLourd[nombreMasses].
    // Si N est impair, le groupe cotesGauche a une masse de plus.
    // Si (estCoteGauchePlusLourd[nombreMasses] est VRAI et nombreMasses est PAIR)
    // OU (estCoteGauchePlusLourd[nombreMasses] est FAUX et nombreMasses est IMPAIR)
    // alors on inverse.
    // Equivalent à (estCoteGauchePlusLourd[nombreMasses] != (nombreMasses % 2 != 0))
    // C'est-à-dire, si le côté gauche doit être plus lourd (L) mais N est pair (cotesDroite initialement plus lourd)
    // ou si le côté droit doit être plus lourd (R) mais N est impair (cotesGauche initialement plus lourd)
    if (estCoteGauchePlusLourd[nombreMasses] != (cotesGauche.size() > cotesDroite.size())) {
         std::swap(cotesGauche, cotesDroite);
    }

    std::vector<MassePlacee> resultatPlacement(nombreMasses + 1);

    for (int i = nombreMasses; i >= 1; --i) {
        bool inversionAttendue = (estCoteGauchePlusLourd[i] != estCoteGauchePlusLourd[i - 1]);

        MassePlacee choixG = {0, 'O'}; // Sentinel
        MassePlacee choixD = {0, 'O'}; // Sentinel

        if (inversionAttendue) { // Le basculement de l'équilibre est attendu
            // On veut retirer la masse la plus lourde pour provoquer ou refléter le basculement
            if (!cotesGauche.empty()) choixG = {cotesGauche.back(), 'L'};
            if (!cotesDroite.empty()) choixD = {cotesDroite.back(), 'R'};

            // Comparer pour trouver la plus grande masse
            if (choixG.cote == 'O' || (choixD.cote != 'O' && choixD.poids > choixG.poids)) {
                resultatPlacement[i] = choixD;
                cotesDroite.pop_back();
            } else {
                resultatPlacement[i] = choixG;
                cotesGauche.pop_back();
            }
        } else { // L'équilibre doit être maintenu
            // On veut retirer la masse la plus légère pour perturber le moins possible
            if (!cotesGauche.empty()) choixG = {cotesGauche.front(), 'L'};
            if (!cotesDroite.empty()) choixD = {cotesDroite.front(), 'R'};

            // Comparer pour trouver la plus petite masse
            if (choixG.cote == 'O' || (choixD.cote != 'O' && choixD.poids < choixG.poids)) {
                resultatPlacement[i] = choixD;
                cotesDroite.pop_front();
            } else {
                resultatPlacement[i] = choixG;
                cotesGauche.pop_front();
            }
        }
    }

    for (int i = 1; i <= nombreMasses; ++i) {
        std::cout << resultatPlacement[i].poids << " " << resultatPlacement[i].cote << std::endl;
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    resoudre();
    return 0;
}

Algorithmique, Greedy, Déque, Tri, Structure de Données

Optimisation de l'Apprentissage de Cartes: Une Approche Probabiliste

Vous participez à un jeu où N cartes sont disponibles. Pour chaque partie, le système sélectionne aléatoirement trois cartes. Ensuite, vous et votre adversaire choisissez chacun une carte à bannir (il est possible de bannir la même carte). Enfin, le système sélectionne une carte au hasard parmi celles qui restent pour la partie. Pour maximiser vos chances de victoire, vous souhaitez étudier un minimum de cartes tout en garantissant une probabilité d'au moins P de jouer sur une carte que vous avez étudiée. Votre adversaire ignore quelles cartes vous avez étudiées.

Analyse du Problème et Calcul des Probabilités Nous devons déterminer le nombre minimal de cartes à étudier, disons k. Pour chaque valeur de k de 0 à N, nous calculons la probabilité de jouer sur une carte étudiée et vérifions si elle atteint ou dépasse P. Nous supposons un jeu optimal de votre part.

Le nombre total de façons de choisir 3 cartes parmi N est donné par le coefficient binomial C(N, 3) = N * (N-1) * (N-2) / 6. Pour simplifier les calculs et éviter les divisions par des nombres non entiers (pour P), nous allons travailler avec le numérateur, c'est-à-dire N * (N-1) * (N-2), qui représente le nombre total de façons ordonnées de choisir 3 cartes distinctes.

Soit k le nombre de cartes étudiées et N-k le nombre de cartes non étudiées. Nous analysons les cas en fonction de la composition des 3 cartes sélectionnées par le système :

1. 0 carte étudiée, 3 cartes non étudiées : - Nombre de sélections ordonnées : (N-k) \* (N-k-1) \* (N-k-2). - Dans ce cas, vous ne pouvez pas gagner, quelle que soit votre action. La probabilité de victoire est 0.
2. 1 carte étudiée, 2 cartes non étudiées : - Nombre de sélections ordonnées : k \* (N-k) \* (N-k-1) \* 3. Le facteur 3 vient des 3 positions possibles pour la carte étudiée dans l'ordre de sélection. - Soient les cartes S (étudiée), U1, U2 (non étudiées). - Vous jouez de manière optimale et bannissez toujours une carte non étudiée si possible. Vous bannissez U1 (ou U2). Il reste S, U2 (ou S, U1). - L'adversaire ne sait pas ce que vous avez étudié. Il bannit une carte au hasard parmi les deux restantes. - Si l'adversaire bannit S, il reste U2 : vous perdez. - Si l'adversaire bannit U2, il reste S : vous gagnez.
3. La probabilité de victoire dans ce cas est 1/2.
4. 2 cartes étudiées, 1 carte non étudiée : - Nombre de sélections ordonnées : k \* (k-1) \* (N-k) \* 3. Le facteur 3 vient des 3 positions possibles pour la carte non étudiée. - Soient les cartes S1, S2 (étudiées), U (non étudiée). - Vous bannissez U. Il reste S1, S2. - L'adversaire bannit une carte au hasard parmi S1, S2. Quoi qu'il arrive, une carte étudiée restera (soit S1, soit S2). - La probabilité de victoire est 1.
5. 3 cartes étudiées, 0 carte non étudiée : - Nombre de sélections ordonnées : k \* (k-1) \* (k-2). - Soient les cartes S1, S2, S3. - Vous bannisesz n'importe laquelle, par exemple S1. Il reste S2, S3. - L'adversaire bannit n'importe laquelle, par exemple S2. Il reste S3. - La probabilité de victoire est 1.

En additionnant les contributions pondérées par les probabilités de victoire pour chaque cas, nous obtenons le nombre total de résultats ordonnés favorables. Nous comparons cette somme à P multiplié par le nombre total de sélections ordonnées possibles pour les 3 cartes.

Implémentation Le code itère sur k de 0 à N. Pour chaque k, il calcule la somme des contributions favorables et la compare au seuil P * (N * (N-1) * (N-2)). Dès que la condition est remplie, il affiche k et termine.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip> // Pour std::fixed et std::setprecision

void resoudre() {
    int totalCartes;
    double probaMinRequise;
    std::cin >> totalCartes >> probaMinRequise;

    for (int cartesEtudiees = 0; cartesEtudiees <= totalCartes; ++cartesEtudiees) {
        double favorableWeightSum = 0; // Somme pondérée des issues favorables (numérateur pour proba)

        // Cas 1: 1 carte étudiée, 2 non étudiées
        // Nombre de façons ordonnées de choisir: C(cartesEtudiees, 1) * C(totalCartes - cartesEtudiees, 2) * 3!
        // Mais comme dans le code original, c'est directement k * (N-k) * (N-k-1) * 3
        if (cartesEtudiees >= 1 && totalCartes - cartesEtudiees >= 2) {
            favorableWeightSum += 3.0 * (cartesEtudiees) * (totalCartes - cartesEtudiees) * (totalCartes - cartesEtudiees - 1) * 0.5;
        }

        // Cas 2: 2 cartes étudiées, 1 non étudiée
        // Nombre de façons ordonnées de choisir: C(cartesEtudiees, 2) * C(totalCartes - cartesEtudiees, 1) * 3!
        // Mais comme dans le code original, c'est directement k * (k-1) * (N-k) * 3
        if (cartesEtudiees >= 2 && totalCartes - cartesEtudiees >= 1) {
            favorableWeightSum += 3.0 * (cartesEtudiees) * (cartesEtudiees - 1) * (totalCartes - cartesEtudiees) * 1.0;
        }

        // Cas 3: 3 cartes étudiées, 0 non étudiée
        // Nombre de façons ordonnées de choisir: C(cartesEtudiees, 3) * 3!
        // Mais comme dans le code original, c'est directement k * (k-1) * (k-2)
        if (cartesEtudiees >= 3) {
            favorableWeightSum += (cartesEtudiees) * (cartesEtudiees - 1) * (cartesEtudiees - 2) * 1.0;
        }

        // Le dénominateur commun, si on calculait C(N,3) puis multipliait par 6
        // C'est totalCartes * (totalCartes - 1) * (totalCartes - 2) pour les permutations des 3 cartes.
        double totalPermutations = (double)totalCartes * (totalCartes - 1) * (totalCartes - 2);

        // Si la somme pondérée des issues favorables atteint le seuil requis
        if (favorableWeightSum >= probaMinRequise * totalPermutations) {
            std::cout << cartesEtudiees << std::endl;
            return;
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    // Utiliser std::fixed et std::setprecision pour éviter les problèmes de précision des doubles,
    // bien que dans ce problème la comparaison semble être robuste.
    // std::cout << std::fixed << std::setprecision(10);
    resoudre();
    return 0;
}

Algorithmique, Probabilités, Combinatoire

Vérification de Progression Arithmétique par Sommes de Puissances Modulo

Étant donnée une séquence A = [a_1, a_2, ..., a_N] de longueur N. Pour chaque requête, on nous fournit un intervalle [l, r] et une différence commune d. La question est de savoir si les éléments dans le sous-tableau A[l..r] peuvent être réarrangés pour former une progression arithmétique de différence d. Tous les calculs doivent être effectués modulo 10^9 + 7.

Principes et Méthode Pour vérifier si un ensemble d'éléments peut former une progression arithmétique (PA) de différence d, nous utilisons une propriété basée sur les sommes de puissances. Si un ensemble de k nombres {x_0, x_1, ..., x_{k-1}} peut former une PA (a, a+d, ..., a+(k-1)d), alors la somme de leurs j-ièmes puissances doit être égale à la somme des j-ièmes puissances des termes de la PA. Cette méthode est robuste, surtout lorsque nous testons pour plusieurs puissances.

Pour un intervalle [l, r] de longueur len = r - l + 1 :

1. **Calcul du premier terme (a) de la PA potentielle :**La somme des éléments d'une PA est S_1 = len * a + d * sum_{i=0}^{len-1}(i). Nous pouvons calculer sum_{i=0}^{len-1}(i) = len * (len-1) / 2. La somme réelle des éléments dans A[l..r] (notée SommeReelle) est obtenue par des sommes de préfixes. En égalisant les deux, nous pouvons résoudre pour a :

a = (SommeReelle - d * (len * (len-1) / 2) ) * len^{-1} (mod M)

où len^{-1} est l'inverse modulaire de len. 2. **Vérification des sommes de puissances :**Une fois a et d sont connus, nous pouvons construire la PA attendue : a, a+d, a+2d, ..., a+(len-1)d. Pour k allant de 1 à une constante MAX_K (ici 10), nous comparons la somme des k-ièmes puissances des éléments réels de A[l..r] avec la somme des k-ièmes puissances des termes de la PA attendue.

La somme attendue S_k = sum_{i=0}^{len-1} (a + i*d)^k peut être calculée en utilisant le théorème binomial :

(a + i*d)^k = sum_{j=0}^k C(k, j) * a^{k-j} * (i*d)^j

En intervertissant les sommes, on obtient :

S_k = sum_{j=0}^k [ C(k, j) * a^{k-j} * d^j * (sum_{i=0}^{len-1} i^j) ]

Les termes C(k, j) (coefficients binomiaux) et sum_{i=0}^{len-1} i^j sont précalculés pour une efficacité optimale.

Précalculs Pour chaque k de 0 à MAX_K et pour chaque indice i de 0 à N, nous précalculons :

• coefficientsBinomiaux[k][j] = C(k, j).
• prefixSumsElementsPowers[k][i] : somme des k-ièmes puissances des a_1, ..., a_i.
• prefixSumsIndicesPowers[k][i] : somme des k-ièmes puissances des 0, ..., i (c'est-à-dire sum_{x=0}^i x^k).

Détails d'Implémentation

• Modulo Arithmétique : Toutes les opérations (addition, soustraction, multiplication) sont effectuées modulo 10^9 + 7. La division est remplacée par la multiplication par l'inverse modulaire (calculé avec l'exponentiation rapide pour x^(M-2) selon le petit théorème de Fermat).
• Efficacité : Les sommes de préfixes permettent de calculer les sommes sur un intervalle [l, r] en O(1). Chaque requête prend O(MAX_K) car la formule binomiale nécessite de sommer MAX_K+1 termes. Le précalcul est en O(N * MAX_K + MAX_K^2).
• Cas d=0 : Si d=0, la PA attendue est a, a, ..., a. La formule générale gère ce cas correctement, car la somme des puissances k devient simplement len * a^k. La vérification de la somme des puissances détectera si les éléments réels ne sont pas tous égaux à a.

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

// Utilisation de long long pour les calculs intermédiaires afin d'éviter les débordements avant l'opération modulo.
using ll = long long;

const int MAX_N = 2e5 + 10;
const int MOD = 1e9 + 7;
const int MAX_K = 10; // Niveau de puissance max pour la vérification

int N_elements, Q_queries;
ll valeursElements[MAX_N];

// prefixSumsElementsPowers[k][i] = sum_{j=1 to i} (valeursElements[j])^k
ll prefixSumsElementsPowers[MAX_K + 1][MAX_N];

// prefixSumsIndicesPowers[k][i] = sum_{x=0 to i} x^k
ll prefixSumsIndicesPowers[MAX_K + 1][MAX_N];

// coefficientsBinomiaux[k][j] = C(k, j)
ll coefficientsBinomiaux[MAX_K + 1][MAX_K + 1];

// Fonction pour l'exponentiation modulaire rapide (x^a % MOD)
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Fonction pour calculer l'inverse modulaire (x^(MOD-2) % MOD)
ll modInverse(ll n) {
    return power(n, MOD - 2);
}

// Calcule la somme des k-ièmes puissances de la PA attendue: sum_{i=0}^{len-1} (first_term + i*diff_com)^k
ll calculateExpectedSumOfPowers(ll first_term, ll diff_com, int len, int k_power) {
    ll total_sum = 0;
    for (int j = 0; j <= k_power; ++j) {
        ll term = coefficientsBinomiaux[k_power][j];
        term = (term * power(first_term, k_power - j)) % MOD;
        term = (term * power(diff_com, j)) % MOD;
        term = (term * prefixSumsIndicesPowers[j][len - 1]) % MOD; // sum_{i=0}^{len-1} i^j
        total_sum = (total_sum + term) % MOD;
    }
    return total_sum;
}

void solve() {
    std::cin >> N_elements >> Q_queries;

    // Précalcul des coefficients binomiaux C(k, j)
    for (int i = 0; i <= MAX_K; ++i) {
        coefficientsBinomiaux[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            coefficientsBinomiaux[i][j] = (coefficientsBinomiaux[i - 1][j - 1] + coefficientsBinomiaux[i - 1][j]) % MOD;
        }
    }

    // Précalcul des sommes de puissances des indices: sum_{x=0}^i x^k
    for (int i = 0; i < N_elements; ++i) {
        // x^0 = 1 pour x >= 0
        prefixSumsIndicesPowers[0][i] = (i == 0) ? 1 : (prefixSumsIndicesPowers[0][i-1] + 1) % MOD;
    }
    for (int k = 1; k <= MAX_K; ++k) {
        prefixSumsIndicesPowers[k][0] = 0; // 0^k = 0 pour k > 0
        for (int i = 1; i < N_elements; ++i) {
            prefixSumsIndicesPowers[k][i] = (prefixSumsIndicesPowers[k][i-1] + power(i, k)) % MOD;
        }
    }
    
    // Lecture des éléments et précalcul des sommes de puissances des éléments: sum_{j=1 to i} (valeursElements[j])^k
    for (int i = 1; i <= N_elements; ++i) {
        std::cin >> valeursElements[i];
        for (int k = 0; k <= MAX_K; ++k) {
            prefixSumsElementsPowers[k][i] = (prefixSumsElementsPowers[k][i - 1] + power(valeursElements[i], k)) % MOD;
        }
    }

    while (Q_queries--) {
        int idxDebut, idxFin;
        ll diffCommune;
        std::cin >> idxDebut >> idxFin >> diffCommune;

        int longueur = idxFin - idxDebut + 1;
        if (longueur == 0) { // Cas vide
            std::cout << "Yes\n";
            continue;
        }
        if (longueur == 1) { // Une seule valeur toujours une PA
            std::cout << "Yes\n";
            continue;
        }

        // Somme des éléments réels dans l'intervalle [idxDebut, idxFin]
        ll sommeElementsReels = (prefixSumsElementsPowers[1][idxFin] - prefixSumsElementsPowers[1][idxDebut - 1] + MOD) % MOD;

        // Somme des indices pour la PA (0 + 1 + ... + (longueur-1))
        ll sommeIndicesPA = (ll)longueur * (longueur - 1) / 2 % MOD;

        // Calcul du premier terme 'a' de la PA
        ll premierTerme = (sommeElementsReels - (diffCommune * sommeIndicesPA % MOD) + MOD) % MOD;
        premierTerme = (premierTerme * modInverse(longueur)) % MOD;

        bool estProgressionArithmetique = true;
        // Vérification des sommes de puissances pour k=1 à MAX_K
        for (int k = 1; k <= MAX_K; ++k) {
            ll sommePuissancesReelles = (prefixSumsElementsPowers[k][idxFin] - prefixSumsElementsPowers[k][idxDebut - 1] + MOD) % MOD;
            ll sommePuissancesAttendues = calculateExpectedSumOfPowers(premierTerme, diffCommune, longueur, k);

            if (sommePuissancesReelles != sommePuissancesAttendues) {
                estProgressionArithmetique = false;
                break;
            }
        }

        if (estProgressionArithmetique) {
            std::cout << "Yes\n";
        } else {
            std::cout << "No\n";
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}