Problème 1 : Classement des notes

Vous disposez des notes de N élèves, chacun ayant obtenu des scores en français, en mathématiques et en anglais. L'objectif est de classer ces élèves du meilleur au moins bon selon les critères suivants :

1. Le total des points (somme des trois matières) est le critère principal : celui qui a le score total le plus élevé est mieux classé.
2. Si les scores totaux sont identiques, on compare la somme des notes en français et en mathématiques. Le candidat avec la somme la plus élevée est mieux classé.
3. Si les scores totaux et les sommes français+mathématiques sont identiques, on compare la meilleure note obtenue entre le français et les mathématiques. Le candidat ayant la note la plus élevée dans l'une de ces deux matières est mieux classé.
4. Si tous les critères précédents sont identiques, les candidats sont considérés comme à égalité.

Vous devez afficher le rang de chaque élève dans l'ordre de leur apparition en entrée. En cas d'égalité, les élèves partagent le même rang, et les rangs suivants sont décalés en conséquence. Par exemple, si trois élèves sont classés 1er ex aequo, le candidat suivant sera classé 4ème.

Exemple d'entrée

6
140 140 150
140 149 140
148 141 140
141 148 140
145 145 139
0 0 0

Exemple de sortie

1
3
4
4
2
6

Approche de résolution

Pour résoudre ce problème, nous allons utiliser une structure de données pour stocker les informations de chaque élève, y compris leurs notes, les totaux calculés pour les critères de classemnet, un identifiant original et leur rang final. Ensuite, nous procéderons à un tri personnalisé en deux étapes :

1. Lecture des données et calcul des totaux intermédiaires.
2. Premier tri : Les élèves sont triés en fonction des règles de classement complexes définies.
3. Assignation des rangs : Après le tri, nous parcourons la liste triée pour attribuer les rangs, en gérant les égalités selon la règle de décalage des rangs.
4. Deuxième tri : La liste est triée à nouveau, cette fois par l'identifiant original pour restaurer l'ordre d'entrée.
5. Affichage des rangs dans l'ordre initial des élèves.

Implémentation C++

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::sort et std::max

// Structure pour représenter un élève et ses informations de classement
struct FicheEleve {
    int idInitial;       // L'identifiant original de l'élève (ordre d'entrée)
    int noteFrancais;    // Note en français
    int noteMathematiques; // Note en mathématiques
    int noteAnglais;     // Note en anglais
    int scoreTotal;      // Somme des trois notes
    int scoreFM;         // Somme des notes français + mathématiques
    int meilleurFouM;    // La meilleure note entre français et mathématiques
    int rangAttribution; // Le rang final attribué à l'élève
};

// Fonction de comparaison pour le tri principal (par notes)
bool comparerEleves(const FicheEleve& a, const FicheEleve& b) {
    if (a.scoreTotal != b.scoreTotal) {
        return a.scoreTotal > b.scoreTotal; // Règle 1: Score total le plus élevé en premier
    }
    if (a.scoreFM != b.scoreFM) {
        return a.scoreFM > b.scoreFM;       // Règle 2: Somme F+M la plus élevée en premier
    }
    if (a.meilleurFouM != b.meilleurFouM) {
        return a.meilleurFouM > b.meilleurFouM; // Règle 3: Meilleure note F ou M la plus élevée en premier
    }
    return a.idInitial < b.idInitial;     // Règle 4: Identifiant initial le plus petit en premier (pour stabilité du tri)
}

// Fonction de comparaison pour le tri final (par identifiant initial)
bool comparerParIdInitial(const FicheEleve& a, const FicheEleve& b) {
    return a.idInitial < b.idInitial;
}

int main() {
    std::ios_base::sync_with_stdio(false); // Optimisation des flux d'entrée/sortie
    std::cin.tie(NULL);                   // Désynchronisation de cin et cout

    int nombreEleves;
    std::cin >> nombreEleves;

    std::vector<FicheEleve> listeEleves(nombreEleves);

    // Lecture des entrées et calcul des champs nécessaires au classement
    for (int i = 0; i < nombreEleves; ++i) {
        listeEleves[i].idInitial = i; // Enregistre l'index original (0-basé)
        std::cin >> listeEleves[i].noteFrancais
                  >> listeEleves[i].noteMathematiques
                  >> listeEleves[i].noteAnglais;

        listeEleves[i].scoreTotal = listeEleves[i].noteFrancais +
                                  listeEleves[i].noteMathematiques +
                                  listeEleves[i].noteAnglais;

        listeEleves[i].scoreFM = listeEleves[i].noteFrancais +
                                listeEleves[i].noteMathematiques;

        listeEleves[i].meilleurFouM = std::max(listeEleves[i].noteFrancais,
                                         listeEleves[i].noteMathematiques);
    }

    // Premier tri: Selon les critères de notes complexes
    std::sort(listeEleves.begin(), listeEleves.end(), comparerEleves);

    // Attribution des rangs après le tri par notes
    // Le rang du premier élève est toujours 1
    listeEleves[0].rangAttribution = 1; 

    for (int i = 1; i < nombreEleves; ++i) {
        // Vérifie si l'élève actuel a les mêmes scores que l'élève précédent
        // selon tous les critères de classement (égalité parfaite)
        if (listeEleves[i].scoreTotal == listeEleves[i-1].scoreTotal &&
            listeEleves[i].scoreFM == listeEleves[i-1].scoreFM &&
            listeEleves[i].meilleurFouM == listeEleves[i-1].meilleurFouM) {
            
            // Si égalité, attribue le même rang que l'élève précédent
            listeEleves[i].rangAttribution = listeEleves[i-1].rangAttribution;
        } else {
            // Sinon, attribue un nouveau rang basé sur la position actuelle (i + 1)
            listeEleves[i].rangAttribution = i + 1; 
        }
    }

    // Deuxième tri: Pour afficher les rangs dans l'ordre initial des élèves
    std::sort(listeEleves.begin(), listeEleves.end(), comparerParIdInitial);

    // Affichage des rangs finaux
    for (int i = 0; i < nombreEleves; ++i) {
        std::cout << listeEleves[i].rangAttribution << "\n";
    }

    return 0;
}

Problème 2 : Nombres B-friables

Un nombre entier positif est dit "B-friable" (ou B-smooth en anglais) si son plus grand facteur premier n'excède pas B. Un utilisateur souhaite déterminer, pour des valeurs N et B données, combien il existe de nombres B-friables inférieurs ou égaux à N.

Exemple d'entrée

10 3

Exemple de sortie

7

Pour l'entrée 10 3, les nombres 3-friables sont :

• 1 (plus grand facteur premier est 1, ce qui est ≤ 3)
• 2 (plus grand facteur premier est 2, ce qui est ≤ 3)
• 3 (plus grand facteur premier est 3, ce qui est ≤ 3)
• 4 (plus grand facteur premier est 2, ce qui est ≤ 3)
• 5 (plus grand facteur premier est 5, ce qui est > 3, donc non 3-friable)
• 6 (plus grand facteur premier est 3, ce qui est ≤ 3)
• 7 (plus grand facteur premier est 7, ce qui est > 3, donc non 3-friable)
• 8 (plus grand facteur premier est 2, ce qui est ≤ 3)
• 9 (plus grand facteur premier est 3, ce qui est ≤ 3)
• 10 (plus grand facteur premier est 5, ce qui est > 3, donc non 3-friable)

Il y a 7 nombres 3-friables : 1, 2, 3, 4, 6, 8, 9.

Approche de résolution

Pour résoudre ce problème, il est nécessaire de trouver le plus grand facteur premier (LPF) de chaque entier de 1 à N. Le crible d'Euler est un algorithme efficace pour précalcluer les propriétés des nombres premiers et composés sur une plage donnée. Nous adapterons le crible d'Euler pour stocker le plus grand facteur premier de chaque nombre.

L'idée générale est la suivante :

1. Initialiser un tableau plusGrandFacteurPremier[i] pour stocker le LPF de i.
2. Pendant le processus du crible, lorsque nous identifions un nombre premier p et l'utilisons pour marquer ses multiples i * p comme composés, nous mettons à jour plusGrandFacteurPremier[i * p]. La clé est de distinguer deux cas : si p est déjà un facteur de i ou non.
3. Après avoir rempli le tableau plusGrandFacteurPremier jusqu'à N, nous parcourons les nombres de 1 à N et comptons ceux pour lesquels plusGrandFacteurPremier[i] ≤ B.

Implémentation C++

#include <iostream>
#include <vector>
#include <algorithm> // Pour std::max

const int LIMITE_MAX_N = 1000000; // Limite maximale pour N

int N_max, B_friabilite; // Variables pour N et B du problème
int compteurNombresFriables;
std::vector<int> listeNombresPremiers;
std::vector<int> plusGrandFacteurPremier(LIMITE_MAX_N + 1);
std::vector<bool> estCompose(LIMITE_MAX_N + 1, false); // true si le nombre est composé

// Crible d'Euler modifié pour trouver le plus grand facteur premier (LPF)
void construireCribleEuler() {
    plusGrandFacteurPremier[1] = 1; // 1 n'a pas de facteur premier par convention pour la friabilité

    for (int i = 2; i <= N_max; ++i) {
        if (!estCompose[i]) { // Si i est premier
            listeNombresPremiers.push_back(i);
            plusGrandFacteurPremier[i] = i; // Un nombre premier a lui-même comme LPF
        }

        // Parcourir les nombres premiers trouvés (p) pour marquer les composés
        for (int p : listeNombresPremiers) {
            // Arrêter si le multiple dépasse N_max ou si p est trop grand
            if (static_cast<long long>(i) * p > N_max) { // Utiliser long long pour éviter l'overflow avant la comparaison
                break; 
            }
            
            estCompose[i * p] = true; // Marque i*p comme composé

            if (i % p == 0) { // Si p est le plus petit facteur premier de i
                // Dans ce cas, tous les facteurs premiers de i sont déjà inférieurs ou égaux à p.
                // Par conséquent, le plus grand facteur premier de i*p est le même que celui de i.
                plusGrandFacteurPremier[i * p] = plusGrandFacteurPremier[i];
                break; // Optimisation clé du crible d'Euler : chaque nombre composé est criblé une seule fois par son plus petit facteur premier
            } else {
                // Si p n'est pas un facteur de i, alors p est le plus petit facteur premier de i*p.
                // Le plus grand facteur premier de i*p sera le maximum entre p et le plus grand facteur premier de i.
                plusGrandFacteurPremier[i * p] = std::max(p, plusGrandFacteurPremier[i]);
            }
        }
    }
}


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

    std::cin >> N_max >> B_friabilite;

    construireCribleEuler();

    compteurNombresFriables = 0;
    // Compter les nombres B-friables en parcourant les résultats du crible
    for (int i = 1; i <= N_max; ++i) {
        if (plusGrandFacteurPremier[i] <= B_friabilite) {
            compteurNombresFriables++;
        }
    }

    std::cout << compteurNombresFriables << "\n";

    return 0;
}