Problème 1 : Construction du nombre

Analyse de l'algorithme

L'objectif est de former le plus grand nombre entier possible à partir des caractères numériques extraits d'une chaîne donnée. Pour maximiser la valeur, il faut placer les chiffres les plus élevés dans les positions de poids le plus fort, c'est-à-dire au début de la séquence. Par exemple, avec les chiffres 9, 2, 1, 0, 0, le résultat optimal est 92100.

L'approche consiste donc en :

1. Extraire tous les caractères numériques de la chaîne d'entrée.
2. Trier cet ensemble de caractères numériques par ordre décroissant ('9' > '8' > ... > '0').
3. Concaténer les caractères triés pour former la chaîne résultante, qui représente le nombre maximal.

Code solution (AC)

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

void configurerES() {
    std::freopen("number.in", "r", stdin);
    std::freopen("number.out", "w", stdout);
}

int main() {
    configurerES();
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string chaineEntree;
    std::cin >> chaineEntree;

    std::vector<char> listeChiffres;
    for (char symbole : chaineEntree) {
        if (std::isdigit(static_cast<unsigned char>(symbole))) {
            listeChiffres.push_back(symbole);
        }
    }

    std::sort(listeChiffres.begin(), listeChiffres.end(), std::greater<char>());

    for (char chiffre : listeChiffres) {
        std::cout << chiffre;
    }
    std::cout << std::endl;

    return 0;
}

Problème 2 : Attribution des places

Analyse de l'algorithme

Le problème demande de déterminer la position (en rangée et colonne) d'un candidat dans une salle d'examen de n rangées et m colonnes, selon un agencement en "serpentin" :

• Les colonnes impaires (1, 3, 5, ...) sont remplies de haut en bas (rangée 1 à n).
• Les colonnes paires (2, 4, 6, ...) sont rempleis de bas en haut (rangée n à 1).

La méthode de résolution est la suivante :

1. Lire n, m et les scores de tous les n*m candidats. D'après l'énoncé, le premier score lu (a1) est celui du candidat à localiser.
2. Trier l'ensemble des scores par ordre décroissant pour établir le classement.
3. Trouver la position (le rang) du score cible dans la liste triée.
4. Calculer les coordonnées (en indexation à base 0) à partir du rang :
   • Colonne : colonne0 = rang / n.
   • Position dans la colonne (selon le sens de remplissage) : posDansCol = rang % n.
5. Déterminer l'indice de rangée en fonction de la parité de la colonne :
   • Si colonne0 est paire (colonnes 1, 3...), le sens est de haut en bas : rangee0 = posDansCol.
   • Si colonne0 est impaire (colonnes 2, 4...), le sens est de bas en haut : rangee0 = n - 1 - posDansCol.
6. Ajouter 1 aux indices colonne0 et rangee0 pour obtenir la position en indexation à base 1.

Code solution (AC)

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

void configurerES() {
    std::freopen("seat.in", "r", stdin);
    std::freopen("seat.out", "w", stdout);
}

int main() {
    configurerES();
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int nbRangees, nbColonnes;
    std::cin >> nbRangees >> nbColonnes;

    int totalCandidats = nbRangees * nbColonnes;
    std::vector<int> tableauScores(totalCandidats);
    for (int i = 0; i < totalCandidats; ++i) {
        std::cin >> tableauScores[i];
    }

    int scoreCible = tableauScores[0];

    std::vector<int> scoresTries = tableauScores;
    std::sort(scoresTries.begin(), scoresTries.end(), std::greater<int>());

    int rang = 0;
    while (rang < totalCandidats && scoresTries[rang] != scoreCible) {
        ++rang;
    }

    int colonne0 = rang / nbRangees;
    int positionDansCol = rang % nbRangees;
    int rangee0;

    if (colonne0 % 2 == 0) {
        rangee0 = positionDansCol;
    } else {
        rangee0 = nbRangees - 1 - positionDansCol;
    }

    std::cout << colonne0 + 1 << " " << rangee0 + 1 << std::endl;

    return 0;
}

Problème 3 : Somme par OU exclusif

Analyse de l'algorithme

Le but est de trouver le nombre maximal d'intervalles disjoints dans une séquence tels que le OU exclusif (XOR) de tous les éléments d'un intervalle soit égal à k.

Il s'agit d'un problème classique de programmation dynamique. Pour calculer efficacement le XOR d'un intervalle, on utilise un préfixe XOR.

• Soit prefixe_xor[i] le XOR des éléments de a[1] à a[i].
• Le XOR de l'intervalle [j, i] est alors prefixe_xor[i] XOR prefixe_xor[j-1].
• La condition prefixe_xor[i] XOR prefixe_xor[j-1] = k se réécrit en prefixe_xor[j-1] = prefixe_xor[i] XOR k.

On définit dp[i] comme le nombre maximal d'intervalles valides que l'on peut sélectionner en considérant les i premiers éléments.

Le calcul de dp[i] offre deux options :

1. Ne pas terminer d'intervalle en i : dp[i] = dp[i-1].
2. Terminer un intervalle [j, i] : le total devient 1 + dp[j-1].

Pour éviter une recherche linéaire de tous les j, on utilise une table de hachage meilleur_dp_par_px où meilleur_dp_par_px[valeur] conserve la valeur maximale de dp associée à un préfixe XOR valeur.

Code solution (AC)

#include <iostream>
#include <vector>
#include <map>

void configurerES() {
    std::freopen("xor.in", "r", stdin);
    std::freopen("xor.out", "w", stdout);
}

int main() {
    configurerES();
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    std::cin >> n >> k;

    std::vector<int> sequence(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> sequence[i];
    }

    std::vector<int> comptageSousEnsembles(n + 1, 0);
    std::map<int, int> tableDeHachage;
    tableDeHachage[0] = 0; // Préfixe vide, XOR = 0

    int xorCourant = 0;
    for (int idx = 1; idx <= n; ++idx) {
        xorCourant ^= sequence[idx - 1];

        comptageSousEnsembles[idx] = comptageSousEnsembles[idx - 1];

        int cible = xorCourant ^ k;
        if (tableDeHachage.count(cible)) {
            comptageSousEnsembles[idx] = std::max(comptageSousEnsembles[idx], tableDeHachage[cible] + 1);
        }

        if (tableDeHachage.count(xorCourant)) {
            tableDeHachage[xorCourant] = std::max(tableDeHachage[xorCourant], comptageSousEnsembles[idx]);
        } else {
            tableDeHachage[xorCourant] = comptageSousEnsembles[idx];
        }
    }

    std::cout << comptageSousEnsembles[n] << std::endl;

    return 0;
}

Problème 4 : Polygones

Analyse de l'algorithme

Le problème demande de compter le nombre de sous-ensembles de bâtonnets pouvant former un polygone. La condition est que la taille du sous-ensemble m >= 3 et que la somme des longueurs S soit strictement supérieure au double de la plus longue longueur L (S > 2L). Cela équivaut à la longueur du plus long côté doit être inférieure à la somme des longueurs des autres côtés.

C'est un problème de dénombrement combinatoire, résoluble par programmation dynamique (DP), similaire au problème du sac à dos 0/1.

1. Trier les bâtonnets par longueur croissante. Cette étape est cruciale car elle permet, lors de l'itération, de considérer le bâton courant a[i] comme le plus long, et de ne sélectionner des bâtonnets que parmi a[0]...a[i-1].
2. Utiliser un tableau nombreFacons où nombreFacons[s] représente le nombre de façons de sélectionner un sous-ensemble dont la somme des longueurs est s, parmi les bâtonnets déjà traités.
3. L'algorithme procède ainsi :
   • Trier le tableau a.
   • Initialiser nombreFacons[0] = 1 (un seul sous-ensemble de somme 0 : le vide).
   • Pour chaque i de 0 à n-1, traiter a[i] comme le côté potentiellement le plus long :
     1. Avant d'incorporer a[i], nombreFacons contient les combinaisons issues de {a[0], ..., a[i-1]}.
     2. Le nombre de sous-ensembles valides avec a[i] comme plus long côté est : (Nombre total de sous-ensembles du préfixe) - (Nombre de sous-ensembles dont la somme ≤ a[i]).
     3. Le nombre total de sous-ensembles du préfixe est 2^i.
     4. Le nombre de sous-ensembles de somme ≤ a[i] est la somme ∑nombreFacons[s] pour s de 0 à a[i].
     5. Ajouter le résultat au compteur global reponse. Ce décompte inclut automatiquement les sous-ensembles de taille ≥ 2 (le vide et un seul élément ne peuvent satisfaire la condition de somme > a[i]).
     6. Incorporer a[i] dans le sac à dos : mettre à jour nombreFacons de façon descendante : pour s de ... à a[i] en descendant : nombreFacons[s] += nombreFacons[s - a[i]].
4. Tous les calculs sont effectués modulo 998 244 353.

Code solution (AC)

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

const int MODULO = 998244353;
const int MAX_SOMME = 5000;

void configurerES() {
    std::freopen("polygon.in", "r", stdin);
    std::freopen("polygon.out", "w", stdout);
}

int main() {
    configurerES();
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> longueurs(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> longueurs[i];
    }

    std::sort(longueurs.begin(), longueurs.end());

    std::vector<long long> nombreFacons(MAX_SOMME + 1, 0);
    nombreFacons[0] = 1;

    std::vector<long long> puissancesDe2(n + 1);
    puissancesDe2[0] = 1;
    for (int p = 1; p <= n; ++p) {
        puissancesDe2[p] = (puissancesDe2[p - 1] * 2) % MODULO;
    }

    long long resultatFinal = 0;
    long long sommeCourante = 0;

    for (int i = 0; i < n; ++i) {
        // Étape 1 : Compter les combinaisons valides où longueurs[i] est le plus long côté
        long long compteurPetits = 0;
        for (int s = 0; s <= longueurs[i]; ++s) {
            compteurPetits = (compteurPetits + nombreFacons[s]) % MODULO;
        }

        long long totalSousEnsembles = puissancesDe2[i];
        long long compteurValides = (totalSousEnsembles - compteurPetits + MODULO) % MODULO;
        resultatFinal = (resultatFinal + compteurValides) % MODULO;

        // Étape 2 : Mettre à jour le sac à dos avec le bâtonnet courant
        sommeCourante += longueurs[i];
        int borne = std::min(static_cast<long long>(MAX_SOMME), sommeCourante);
        for (int s = borne; s >= longueurs[i]; --s) {
            nombreFacons[s] = (nombreFacons[s] + nombreFacons[s - longueurs[i]]) % MODULO;
        }
    }

    std::cout << resultatFinal << std::endl;

    return 0;
}