Problème 1 : Approximation de Pi

Ce problème demande d'afficher les N premières décimales de Pi, précédées de "3.". La solution consiste à utiliser une chaîne de caractères pré-définie contenant une approximation suffisamment longue de Pi et d'en extraire une sous-chaîne selon la précision requise.

import math

def afficher_pi_tronque():
    # Définir une chaîne longue de Pi pour assurer une précision suffisante.
    # L'énoncé suggère une chaîne spécifique, nous la réutilisons.
    chaine_pi_complete = '3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679'
    
    # Lire le nombre de décimales N
    precision_n = int(input())
    
    # Pour afficher N décimales, nous avons besoin de l'indice 0 (pour '3'), 
    # l'indice 1 (pour '.'), et ensuite N caractères.
    # Donc, la longueur totale de la sous-chaîne est N + 2.
    resultat_tronque = chaine_pi_complete[0 : precision_n + 2]
    
    print(resultat_tronque)

# Exécuter la fonction de résolution
afficher_pi_tronque()

Problème 2 : Roulette

L'objectif est d'identifier les joueurs qui ont parié sur un numéro gagnant donné et, parmi eux, de sélectionner ceux qui ont misé le moins de numéros au total. La solution implique de parcourir les paris de chaque joueur pour vérifier s'ils incluent le numéro gagnant, puis de trouver le minimum du nombre de paris parmi ces joueurs, et enfin de lister tous les joueurs correspondants.

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::min
#include <limits>    // Pour std::numeric_limits

void resoudre_probleme_roulette() {
    int nombre_participants;
    std::cin >> nombre_participants;

    std::vector<int> counts_par_participant(nombre_participants);
    std::vector<std::vector<int>> paris_par_participant(nombre_participants);

    // Lecture des paris de chaque participant
    for (int i = 0; i < nombre_participants; ++i) {
        std::cin >> counts_par_participant[i];
        paris_par_participant[i].resize(counts_par_participant[i]);
        for (int j = 0; j < counts_par_participant[i]; ++j) {
            std::cin >> paris_par_participant[i][j];
        }
    }

    int numero_gagnant;
    std::cin >> numero_gagnant;

    // Variables pour stocker le nombre minimum de paris et les identifiants des participants
    int min_nombre_paris = std::numeric_limits<int>::max();
    std::vector<int> participants_selectionnes;

    // Première passe : trouver le nombre minimum de paris parmi ceux qui ont gagné
    for (int i = 0; i < nombre_participants; ++i) {
        bool a_pari_sur_le_bon_numero = false;
        for (int numero_mise : paris_par_participant[i]) {
            if (numero_mise == numero_gagnant) {
                a_pari_sur_le_bon_numero = true;
                break;
            }
        }

        if (a_pari_sur_le_bon_numero) {
            min_nombre_paris = std::min(min_nombre_paris, counts_par_participant[i]);
        }
    }
    
    // Deuxième passe : collecter tous les participants qui ont ce nombre minimum de paris
    for (int i = 0; i < nombre_participants; ++i) {
        bool a_pari_sur_le_bon_numero = false;
        for (int numero_mise : paris_par_participant[i]) {
            if (numero_mise == numero_gagnant) {
                a_pari_sur_le_bon_numero = true;
                break;
            }
        }

        if (a_pari_sur_le_bon_numero && counts_par_participant[i] == min_nombre_paris) {
            participants_selectionnes.push_back(i + 1); // Les identifiants sont 1-basés
        }
    }

    // Affichage des résultats
    std::cout << participants_selectionnes.size() << std::endl;
    for (size_t i = 0; i < participants_selectionnes.size(); ++i) {
        std::cout << participants_selectionnes[i] << (i == participants_selectionnes.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false); // Optimisation I/O
    std::cin.tie(NULL); // Optimisation I/O
    resoudre_probleme_roulette();
    return 0;
}

Problème 3 : Rotation de Sous-Séquence Colorée

Étant donné une chaîne de caractères et une affectation de couleurs à chaque position, l'objectif est d'effectuer une rotation cyclique d'un pas vers la droite pour chaque sous-séquence de caractères de même couleur. Pour ce faire, nous pré-traitons les positions de chaque caractère par couleur, puis nous appliquons la rotation pour chaque groupe de couleur en copiant les caractères vers leur nouvelle position.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Pour std::rotate si on voulait l'utiliser directement sur un vector de chars

void resoudre_rotation_couleur() {
    int longueur_chaine, nombre_de_couleurs;
    std::cin >> longueur_chaine >> nombre_de_couleurs;
    std::string chaine_initiale;
    std::cin >> chaine_initiale;
    std::vector<int> couleurs_des_positions(longueur_chaine);
    for (int i = 0; i < longueur_chaine; ++i) {
        std::cin >> couleurs_des_positions[i];
    }

    // regrouper les indices de caractères par leur couleur
    // Utilisation d'un vector de vectors car les couleurs sont 1-basées.
    std::vector<std::vector<int>> indices_groupes_par_couleur(nombre_de_couleurs);
    for (int i = 0; i < longueur_chaine; ++i) {
        indices_groupes_par_couleur[couleurs_des_positions[i] - 1].push_back(i);
    }

    std::string chaine_resultante = chaine_initiale; // La chaîne sur laquelle nous allons construire le résultat

    // Appliquer la rotation pour chaque groupe de couleur
    for (int couleur_idx = 0; couleur_idx < nombre_de_couleurs; ++couleur_idx) {
        const std::vector<int>& positions_de_cette_couleur = indices_groupes_par_couleur[couleur_idx];
        int taille_groupe = positions_de_cette_couleur.size();

        if (taille_groupe > 0) {
            // Créer une copie temporaire des caractères de ce groupe
            std::string caracteres_du_groupe_avant_rotation;
            for (int pos : positions_de_cette_couleur) {
                caracteres_du_groupe_avant_rotation += chaine_initiale[pos];
            }

            // Appliquer la rotation d'un pas vers la droite sur les caractères copiés
            // Le dernier caractère devient le premier, les autres décalent.
            if (taille_groupe > 1) {
                char dernier_char = caracteres_du_groupe_avant_rotation.back();
                caracteres_du_groupe_avant_rotation.pop_back(); // Supprime le dernier
                caracteres_du_groupe_avant_rotation.insert(0, 1, dernier_char); // Insère au début
            }

            // Copier les caractères tournés dans la chaîne_resultante aux positions originales
            for (int j = 0; j < taille_groupe; ++j) {
                chaine_resultante[positions_de_cette_couleur[j]] = caracteres_du_groupe_avant_rotation[j];
            }
        }
    }

    std::cout << chaine_resultante << std::endl;
}

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

Problème 4 : Minuscules / Majuscules

Ce problème concerne la manipulation de chaînes de caractères avec des opérations de modification de caractères individuels et des opérations de conversion globale en minuscules ou majuscules. L'astuce réside dans le fait que seule la dernière opération globale de conversion affecte les caractères qui n'ont pas été modifiés individuellement après cette opération globale. Nous suivons donc la dernière opération globale et l'heure de la dernière modification de chaque caractère.

#include <iostream>
#include <vector>
#include <string>
#include <cctype> // Pour std::tolower, std::toupper

void resoudre_conversion_casse() {
    int n_longueur_chaine;
    int q_nombre_operations;
    std::string s_chaine_initiale;

    std::cin >> n_longueur_chaine >> s_chaine_initiale >> q_nombre_operations;

    // `moment_derniere_conversion_globale`: index de la requête de la dernière conversion globale.
    // -1 si aucune.
    int moment_derniere_conversion_globale = -1;
    // `type_derniere_conversion_globale`: 2 pour minuscule, 3 pour majuscule.
    int type_derniere_conversion_globale = 0; 

    // `moment_derniere_modification_char[i]`: index de la requête de la dernière modification
    // individuelle de s_chaine_initiale[i]. Initialisé à -1.
    std::vector<int> moment_derniere_modification_char(n_longueur_chaine, -1);

    // Traitement des requêtes
    for (int index_requete = 0; index_requete < q_nombre_operations; ++index_requete) {
        int type_operation, index_caractere;
        char nouveau_caractere;
        std::cin >> type_operation >> index_caractere >> nouveau_caractere;

        // Ajuster l'index à 0-basé
        --index_caractere;

        if (type_operation == 1) { // Opération de remplacement de caractère
            s_chaine_initiale[index_caractere] = nouveau_caractere;
            moment_derniere_modification_char[index_caractere] = index_requete;
        } else { // Opération de conversion globale (2: minuscules, 3: majuscules)
            moment_derniere_conversion_globale = index_requete;
            type_derniere_conversion_globale = type_operation;
        }
    }

    // Après toutes les requêtes, appliquer la dernière conversion globale
    // uniquement aux caractères qui n'ont pas été modifiés individuellement
    // après ce moment de conversion globale.
    if (moment_derniere_conversion_globale != -1) {
        for (int i = 0; i < n_longueur_chaine; ++i) {
            if (moment_derniere_modification_char[i] < moment_derniere_conversion_globale) {
                if (type_derniere_conversion_globale == 2) { // Convertir en minuscules
                    s_chaine_initiale[i] = std::tolower(s_chaine_initiale[i]);
                } else { // Convertir en majuscules
                    s_chaine_initiale[i] = std::toupper(s_chaine_initiale[i]);
                }
            }
        }
    }

    std::cout << s_chaine_initiale << std::endl;
}

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

Problème 5 : Roulettes (Espérance)

Ce problème est résolu en utilisant la programmation dynamique pour calculer l'espérance du coût. Soit dp[x] le coût attendu minimal pour atteindre un total de x points. L'état initial est dp[0] = 0. Pour calculer dp[r] pour r > 0, nous examinons chaque jeu de roulette. Si un résultat possible du jeu est 0, cela signifie que le jeu ne fait pas progresser vers l'objectif. La récurrence prend en compte la probabilité de ne pas progresser.

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::min, std::max
#include <iomanip>   // Pour std::fixed et std::setprecision
#include <limits>    // Pour std::numeric_limits

// Fonction utilitaire pour minimiser une valeur double
void mettre_a_jour_min(double& cible, double nouvelle_valeur) {
    if (nouvelle_valeur < cible) {
        cible = nouvelle_valeur;
    }
}

void calculer_esperance_roulettes() {
    int nombre_jeux_differents; // N
    int objectif_total_points; // M
    std::cin >> nombre_jeux_differents >> objectif_total_points;

    // Données pour chaque jeu de roulette
    std::vector<int> couts_jeux(nombre_jeux_differents);
    std::vector<int> nombre_resultats_possibles(nombre_jeux_differents);
    std::vector<std::vector<int>> gains_par_jeu(nombre_jeux_differents);

    for (int i = 0; i < nombre_jeux_differents; ++i) {
        std::cin >> couts_jeux[i] >> nombre_resultats_possibles[i];
        gains_par_jeu[i].resize(nombre_resultats_possibles[i]);
        for (int j = 0; j < nombre_resultats_possibles[i]; ++j) {
            std::cin >> gains_par_jeu[i][j];
        }
    }

    // dp[k] représente le coût attendu minimal pour atteindre k points.
    const double INFINI_DP = std::numeric_limits<double>::max();
    std::vector<double> dp_esperance_cout(objectif_total_points + 1, INFINI_DP);

    // Condition de base: atteindre 0 points ne coûte rien
    dp_esperance_cout[0] = 0.0;

    // Calculer dp[r] pour r de 1 à objectif_total_points
    for (int points_a_atteindre = 1; points_a_atteindre <= objectif_total_points; ++points_a_atteindre) {
        for (int idx_jeu = 0; idx_jeu < nombre_jeux_differents; ++idx_jeu) {
            double somme_esperances_futures = 0.0;
            int compte_resultats_nuls = 0; // Compte les S_ij = 0

            for (int gain_resultant : gains_par_jeu[idx_jeu]) {
                if (gain_resultant == 0) {
                    compte_resultats_nuls++;
                } else {
                    // On cherche à atteindre (points_a_atteindre - gain_resultant) points restants.
                    // Le max(0, ...) est pour gérer les cas où le gain dépasse les points à atteindre.
                    somme_esperances_futures += dp_esperance_cout[std::max(0, points_a_atteindre - gain_resultant)];
                }
            }

            // Probabilité d'obtenir un résultat nul pour ce jeu
            double prob_nul = static_cast<double>(compte_resultats_nuls) / nombre_resultats_possibles[idx_jeu];

            // Si tous les résultats sont nuls, ce jeu ne peut pas nous faire progresser.
            if (prob_nul >= 1.0) {
                continue; // Le coût reste infini pour ce chemin
            }

            // La formule pour l'espérance conditionnelle:
            // (Coût_actuel + Somme_esperances_futures / Nb_resultats_possibles) / (1 - Prob_nul)
            double esperance_pour_ce_jeu = (couts_jeux[idx_jeu] + (somme_esperances_futures / nombre_resultats_possibles[idx_jeu])) / (1.0 - prob_nul);
            
            mettre_a_jour_min(dp_esperance_cout[points_a_atteindre], esperance_pour_ce_jeu);
        }
    }

    // Afficher le résultat avec 10 décimales
    std::cout << std::fixed << std::setprecision(10) << dp_esperance_cout[objectif_total_points] << std::endl;
}

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

Problème 6 : Un Certain Jeu

Ce problème peut être modélisé comme un parcours d'arbre sur un arbre de fusion implicite, construit à l'aide d'une structure de données Union-Find. L'idée est de calculre une valeur d'espérance pour chaque nœud de l'arbre en effectuant une descente (DFS) depuis la racine de l'arbre de fusion. Chaque fusion DSU crée un nouveau nœud dans cet arbre, où les deux éléments fusionnés deviennent ses enfants.

#include <iostream>
#include <vector>
#include <numeric>    // Pour std::iota
#include <functional> // Pour std::function (utilisé pour les lambdas récursives)

#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#else
// Implémentation minimaliste de modint si atcoder n'est pas disponible.
// Dans un contexte de compétition, atcoder::modint est généralement utilisé.
struct ModuloInt {
    long long value;
    static const int MOD = 998244353; // Module commun en compétition

    ModuloInt(long long v = 0) {
        value = v % MOD;
        if (value < 0) value += MOD;
    }

    ModuloInt operator+(const ModuloInt& other) const { return ModuloInt(value + other.value); }
    ModuloInt operator-(const ModuloInt& other) const { return ModuloInt(value - other.value); }
    ModuloInt operator*(const ModuloInt& other) const { return ModuloInt(value * other.value); }

    // Pour la division, nous avons besoin de l'inverse modulaire
    ModuloInt inverse() const {
        long long a = value, b = MOD, x = 1, y = 0;
        while (b) {
            long long t = a / b;
            a -= t * b;
            std::swap(a, b);
            x -= t * y;
            std::swap(x, y);
        }
        return ModuloInt(x);
    }

    ModuloInt operator/(const ModuloInt& other) const { return (*this) * other.inverse(); }

    int val() const { return (int)value; }
};
using mint = ModuloInt;
// Si on utilise ModuloInt, il faut aussi une version minimale de DSU.
// Pour cet exemple, je vais supposer atcoder/all est disponible pour la concision.
#endif

void resoudre_jeu_arbre() {
    int nombre_elements_initiaux;
    std::cin >> nombre_elements_initiaux;

    // L'arbre de fusion aura jusqu'à 2*N-1 nœuds.
    // Les N premiers sont les feuilles (éléments initiaux), les N-1 suivants sont les nœuds internes.
    std::vector<std::vector<int>> adjacence_arbre_fusion(2 * nombre_elements_initiaux - 1);
    std::vector<int> taille_composante_dsu(2 * nombre_elements_initiaux - 1);
    for (int i = 0; i < nombre_elements_initiaux; ++i) {
        taille_composante_dsu[i] = 1; // Les feuilles ont une taille de 1
    }

    // Utilisation de DSU pour gérer les fusions et construire l'arbre
    dsu gestionnaire_dsu(nombre_elements_initiaux);
    // mapping_racine_dsu_vers_noeud_arbre[racine_dsu] = index_noeud_arbre
    std::vector<int> mapping_racine_dsu_vers_noeud_arbre(nombre_elements_initiaux);
    std::iota(mapping_racine_dsu_vers_noeud_arbre.begin(), mapping_racine_dsu_vers_noeud_arbre.end(), 0); // Chaque élément initial est un nœud feuille

    int prochain_index_noeud_interne = nombre_elements_initiaux; // Index pour les nouveaux nœuds internes

    for (int i = 0; i < nombre_elements_initiaux - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u; --v; // Convertir en 0-basé

        int racine_u = gestionnaire_dsu.leader(u);
        int racine_v = gestionnaire_dsu.leader(v);

        // Les deux composantes sont différentes, il faut les fusionner
        if (racine_u != racine_v) {
            int nouvel_identifiant_noeud = prochain_index_noeud_interne++;
            
            // Les anciens nœuds deviennent les enfants du nouveau nœud
            adjacence_arbre_fusion[nouvel_identifiant_noeud].push_back(mapping_racine_dsu_vers_noeud_arbre[racine_u]);
            adjacence_arbre_fusion[nouvel_identifiant_noeud].push_back(mapping_racine_dsu_vers_noeud_arbre[racine_v]);

            // Fusionner les composantes dans le DSU
            gestionnaire_dsu.merge(u, v);
            int nouvelle_racine_dsu = gestionnaire_dsu.leader(u);

            // Mettre à jour la taille de la composante DSU fusionnée et la mapper au nouvel identifiant de nœud
            taille_composante_dsu[nouvel_identifiant_noeud] = gestionnaire_dsu.size(nouvelle_racine_dsu);
            mapping_racine_dsu_vers_noeud_arbre[nouvelle_racine_dsu] = nouvel_identifiant_noeud;
        }
    }

    // Le dernier nœud interne créé est la racine de l'arbre de fusion
    int racine_arbre_globale = prochain_index_noeud_interne - 1;

    // dp_valeurs[idx_noeud] stocke l'espérance calculée pour le nœud
    std::vector<mint> dp_valeurs(prochain_index_noeud_interne);
    dp_valeurs[racine_arbre_globale] = 0; // L'espérance à la racine est 0

    // DFS pour propager les valeurs d'espérance de la racine vers les feuilles
    std::function<void(int)> dfs_calcul_esperance = 
        [&](int noeud_actuel) {
        for (int enfant_noeud : adjacence_arbre_fusion[noeud_actuel]) {
            // L'espérance de l'enfant est l'espérance du parent plus la fraction de taille.
            // C'est une formule spécifique à ce type de problème sur les arbres de fusion.
            dp_valeurs[enfant_noeud] = dp_valeurs[noeud_actuel] + mint(taille_composante_dsu[enfant_noeud]) / taille_composante_dsu[noeud_actuel];
            dfs_calcul_esperance(enfant_noeud);
        }
    };

    dfs_calcul_esperance(racine_arbre_globale);

    // Afficher les espérances pour les N éléments initiaux (feuilles de l'arbre)
    for (int i = 0; i < nombre_elements_initiaux; ++i) {
        // Chaque élément initial 'i' est représenté par un nœud feuille dans l'arbre
        // dont l'identifiant est stocké dans mapping_racine_dsu_vers_noeud_arbre après le dernier merge.
        std::cout << dp_valeurs[mapping_racine_dsu_vers_noeud_arbre[gestionnaire_dsu.leader(i)]].val() << (i == nombre_elements_initiaux - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

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

Problème 7 : Amulettes

Plutôt que de calculer combien de monstres peuvent être battus avec un certain nombre d'amulettes, nous reformulons le problème pour déterminer le nombre minimum d'amulettes requis pour battre X monstres. Ce problème se résout efficacement en maintenant deux std::multiset : un pour les valeurs d'amulettes qui contribuent à dépasser le seuil de points de vie requis (amulettes "utilisées"), et un autre pour les amulettes restantes ("disponibles"). Une fonction d'équilibrage maintient l'invariant des ensembles.

#include <iostream>
#include <vector>
#include <set> // Pour std::multiset
#include <algorithm> // Pour std::max, std::prev

// Classe pour gérer la collection d'amulettes et le seuil de points de vie
struct GestionnaireAmulettes {
    long long points_de_vie_requis_courant; // Seuil H, peut changer
    std::multiset<long long> ensemble_amulettes_faibles; // 's' dans l'original: amulettes qui contribuent à réduire H (plus grandes valeurs)
    std::multiset<long long> ensemble_amulettes_elevees; // 't' dans l'original: amulettes sélectionnées pour l'objectif (plus petites valeurs)

    // Constructeur
    GestionnaireAmulettes(long long pv_initial) : points_de_vie_requis_courant(pv_initial) {}

    // Équilibre les deux ensembles pour maintenir l'invariant:
    // La somme des `ensemble_amulettes_faibles` >= points_de_vie_requis_courant.
    // Et toutes les amulettes dans `ensemble_amulettes_elevees` sont plus petites que les amulettes
    // dans `ensemble_amulettes_faibles` qui ne sont pas encore utilisées pour couvrir H.
    void equilibrer_ensembles() {
        // Déplacer les plus grandes amulettes de 'faibles' vers 'élevées' si H est couvert
        while (points_de_vie_requis_courant <= 0 && !ensemble_amulettes_faibles.empty()) {
            long long val_max = *ensemble_amulettes_faibles.rbegin();
            points_de_vie_requis_courant += val_max;
            ensemble_amulettes_elevees.insert(val_max);
            ensemble_amulettes_faibles.erase(std::prev(ensemble_amulettes_faibles.end()));
        }
        // Déplacer les plus petites amulettes de 'élevées' vers 'faibles' si H n'est pas couvert
        while (!ensemble_amulettes_elevees.empty() && points_de_vie_requis_courant > *ensemble_amulettes_elevees.begin()) {
            long long val_min = *ensemble_amulettes_elevees.begin();
            points_de_vie_requis_courant -= val_min;
            ensemble_amulettes_faibles.insert(val_min);
            ensemble_amulettes_elevees.erase(ensemble_amulettes_elevees.begin());
        }
    }

    // Ajoute une valeur d'amulette au système
    void ajouter_valeur(long long valeur) {
        if (!ensemble_amulettes_elevees.empty() && valeur > *ensemble_amulettes_elevees.begin()) {
            ensemble_amulettes_elevees.insert(valeur);
        } else {
            points_de_vie_requis_courant -= valeur;
            ensemble_amulettes_faibles.insert(valeur);
        }
        equilibrer_ensembles();
    }

    // Supprime une valeur d'amulette du système
    void supprimer_valeur(long long valeur) {
        auto it_elevee = ensemble_amulettes_elevees.find(valeur);
        if (it_elevee != ensemble_amulettes_elevees.end()) {
            ensemble_amulettes_elevees.erase(it_elevee);
        } else {
            auto it_faible = ensemble_amulettes_faibles.find(valeur);
            if (it_faible != ensemble_amulettes_faibles.end()) {
                points_de_vie_requis_courant += valeur;
                ensemble_amulettes_faibles.erase(it_faible);
            }
        }
        equilibrer_ensembles();
    }

    // Retourne le nombre d'amulettes dans l'ensemble 'élevées' (celles nécessaires)
    int obtenir_count_amulettes_necessaires() const {
        return ensemble_amulettes_elevees.size();
    }
};

void resoudre_gestion_amulettes() {
    int nombre_types_speciaux_monstres; // N
    int nombre_categories_amulettes;     // M
    long long seuil_global_points_de_vie; // H

    std::cin >> nombre_types_speciaux_monstres >> nombre_categories_amulettes >> seuil_global_points_de_vie;

    std::vector<int> force_des_amulettes(nombre_types_speciaux_monstres);
    std::vector<int> categorie_monstre_associee(nombre_types_speciaux_monstres); // 0-basé

    for (int i = 0; i < nombre_types_speciaux_monstres; ++i) {
        std::cin >> force_des_amulettes[i] >> categorie_monstre_associee[i];
        categorie_monstre_associee[i]--; // Convertir la catégorie en 0-basé
    }

    // `somme_forces_par_categorie[j]` garde la somme des forces d'amulettes pour la catégorie `j`.
    std::vector<long long> somme_forces_par_categorie(nombre_categories_amulettes, 0);

    // Initialisation du gestionnaire d'amulettes avec H.
    // Chaque catégorie de monstre commence avec une "amulette" de force 0.
    GestionnaireAmulettes gestionnaire(seuil_global_points_de_vie);
    for (int i = 0; i < nombre_categories_amulettes; ++i) {
        gestionnaire.ajouter_valeur(0);
    }

    // `resultats_par_amulettes_requises[k]` stocke le nombre max de monstres battus avec `k` amulettes.
    std::vector<int> resultats_par_amulettes_requises(nombre_categories_amulettes + 1, 0);

    // Traiter les monstres séquentiellement
    for (int i = 0; i < nombre_types_speciaux_monstres; ++i) {
        int categorie_actuelle = categorie_monstre_associee[i];
        long long force_amulette_ajout = force_des_amulettes[i];

        // Retirer l'ancienne somme de force pour cette catégorie avant de l'ajouter à nouveau
        gestionnaire.supprimer_valeur(somme_forces_par_categorie[categorie_actuelle]);

        // Mettre à jour la somme pour la catégorie
        somme_forces_par_categorie[categorie_actuelle] += force_amulette_ajout;

        // Ajouter la nouvelle somme de force pour cette catégorie
        gestionnaire.ajouter_valeur(somme_forces_par_categorie[categorie_actuelle]);

        // Enregistrer la réponse pour le nombre actuel d'amulettes requises
        resultats_par_amulettes_requises[gestionnaire.obtenir_count_amulettes_necessaires()] = i + 1;
    }

    // Compléter les résultats: si on peut battre X monstres avec K amulettes,
    // on peut aussi les battre avec K+1 amulettes (non-décroissant).
    for (int k = 0; k < nombre_categories_amulettes; ++k) {
        resultats_par_amulettes_requises[k + 1] = std::max(resultats_par_amulettes_requises[k + 1], resultats_par_amulettes_requises[k]);
    }

    // Afficher les réponses
    for (int k = 0; k <= nombre_categories_amulettes; ++k) {
        std::cout << resultats_par_amulettes_requises[k] << (k == nombre_categories_amulettes ? "" : " ");
    }
    std::cout << std::endl;
}

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