Problème 1 : Fréquence du mode dans un tableau

Étant donné un tableau d'entiers, déterminer la fréquence maximale d'un élément, c'est-à-dire le nombre d'occurrences de la valeur la plus courante.

Approche : Utiliser un tableau de comptage pour enregistrer la fréquence de chaque élément, puis identifier le maximum.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int nombre_elements;
    cin >> nombre_elements;
    vector<int> donnees(nombre_elements);
    vector<int> compteur(101, 0); // Hypothèse : valeurs entre 1 et 100
    for (int i = 0; i < nombre_elements; ++i) {
        cin >> donnees[i];
        compteur[donnees[i]]++;
    }
    int frequence_max = 0;
    for (int j = 1; j <= 100; ++j) {
        if (compteur[j] > frequence_max) {
            frequence_max = compteur[j];
        }
    }
    cout << frequence_max << endl;
    return 0;
}
</int></int></vector></iostream>

Problème 2 : Construction d'une chaîne binaire avec alternances spécifiées

Créer une chaîne composée de a zéros et b uns, avec exactement x alternances entre 0 et 1. La solution existe toujours.

Approche : Simuler la construction en ajustant les séquences de zéros et uns en fonction de la parité de x et des quantités disponibles.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int zeros, uns, alternances;
    cin >> zeros >> uns >> alternances;
    string resultat;
    if (zeros >= uns) {
        resultat += '0';
        zeros--;
        for (int i = 1; i < alternances; ++i) {
            resultat += (resultat.back() == '0') ? '1' : '0';
            if (i % 2 == 1) uns--;
            else zeros--;
        }
        if (alternances % 2 == 1) {
            resultat += string(zeros, '0') + string(uns, '1');
        } else {
            resultat += string(uns, '1') + string(zeros, '0');
        }
    } else {
        resultat += '1';
        uns--;
        for (int i = 1; i < alternances; ++i) {
            resultat += (resultat.back() == '1') ? '0' : '1';
            if (i % 2 == 1) zeros--;
            else uns--;
        }
        if (alternances % 2 == 1) {
            resultat += string(uns, '1') + string(zeros, '0');
        } else {
            resultat += string(zeros, '0') + string(uns, '1');
        }
    }
    cout << resultat << endl;
    return 0;
}
</string></iostream>

Problème 3 : Maximisation de la moyenne des sous-tableaux de longueur minimale k

Trouver la moyenne maximale parmi tous les sous-tableaux consécutifs de longueur au moins k.

Approche : Calculer les sommes préfixes pour accélérer le calcul des sommes de sous-tableaux, puis évaluer toutes les possibilités pour les petites contraintes.

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main() {
    int taille, longueur_min;
    cin >> taille >> longueur_min;
    vector<int> elements(taille);
    vector<int> prefixes(taille + 1, 0);
    for (int i = 0; i < taille; ++i) {
        cin >> elements[i];
        prefixes[i + 1] = prefixes[i] + elements[i];
    }
    double moyenne_max = -1.0;
    for (int debut = 0; debut < taille; ++debut) {
        for (int len = longueur_min; len <= taille - debut; ++len) {
            int somme = prefixes[debut + len] - prefixes[debut];
            double moyenne = static_cast<double>(somme) / len;
            if (moyenne > moyenne_max) {
                moyenne_max = moyenne;
            }
        }
    }
    cout << fixed << setprecision(7) << moyenne_max << endl;
    return 0;
}
</double></int></int></iomanip></vector></iostream>

Problème 4 : Représentation d'un nombre en puissances de deux avec termes minimaux

Étant donné un ensemble de puissances de deux, déterminer le nombre minimal de termes pour représenter une valeur donnée, ou -1 si impossible.

Approche : Convertir la valeur en binaire, puis appliquer une stratégie gloutonne en combinant les puissances inférieures si nécessaire.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int nb_elements, nb_requetes;
    cin >> nb_elements >> nb_requetes;
    vector<long long=""> puissances(32, 1);
    for (int i = 1; i < 32; ++i) {
        puissances[i] = puissances[i - 1] * 2;
    }
    vector<int> compteur(32, 0);
    for (int i = 0; i < nb_elements; ++i) {
        long long val;
        cin >> val;
        int expo = lower_bound(puissances.begin(), puissances.end(), val) - puissances.begin();
        compteur[expo]++;
    }
    for (int i = 0; i < nb_requetes; ++i) {
        long long cible;
        cin >> cible;
        vector<int> bits(32, 0);
        int index = 0;
        while (cible > 0) {
            bits[index++] = cible % 2;
            cible /= 2;
        }
        int termes = 0;
        for (int j = 31; j > 0; --j) {
            int requis = bits[j];
            if (compteur[j] < requis) {
                termes += compteur[j];
                bits[j - 1] += 2 * (requis - compteur[j]);
            } else {
                termes += requis;
            }
        }
        if (compteur[0] < bits[0]) {
            cout << -1 << endl;
        } else {
            cout << termes + bits[0] << endl;
        }
    }
    return 0;
}
</int></int></long></algorithm></vector></iostream>

Problème 5 : Génération d'un arbre avec diamètre et degré maximum spécifiés

Construire un arbre à n nœuds ayant un diamètre d et un degré maximum k, ou déterminer que c'est impossible.

Approche : Créer une chaîne de base pour le diamètre, puis étendre l'arbre en ajoutant des nœuds aux nœuds de la chaîne en respectant les contraintes de degré.

#include <iostream>
#include <vector>
using namespace std;

vector<vector>> adjacences;
int compteur_noeuds;

void construire_sous_arbre(int noeud, int profondeur, int profondeur_max, int degre_max) {
    if (profondeur == profondeur_max) return;
    int enfants_max = degre_max - 1 - (profondeur == 0 ? 1 : 0);
    for (int i = 0; i < enfants_max && compteur_noeuds < adjacences.size(); ++i) {
        int enfant = ++compteur_noeuds;
        adjacences[noeud].push_back(enfant);
        construire_sous_arbre(enfant, profondeur + 1, profondeur_max, degre_max);
    }
}

int main() {
    int nb_noeuds, diametre, degre_max;
    cin >> nb_noeuds >> diametre >> degre_max;
    if (degre_max == 1) {
        if (nb_noeuds == 2 && diametre == 1) {
            cout << "YES" << endl << "1 2" << endl;
        } else {
            cout << "NO" << endl;
        }
        return 0;
    }
    if (diametre >= nb_noeuds) {
        cout << "NO" << endl;
        return 0;
    }
    adjacences.resize(nb_noeuds + 1);
    for (int i = 1; i <= diametre; ++i) {
        adjacences[i].push_back(i + 1);
    }
    compteur_noeuds = diametre + 1;
    for (int j = 1; j <= diametre + 1; ++j) {
        int prof_max = min(j - 1, diametre - j + 1);
        construire_sous_arbre(j, 0, prof_max, degre_max);
    }
    if (compteur_noeuds < nb_noeuds) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
        for (int k = 1; k <= nb_noeuds; ++k) {
            for (int l : adjacences[k]) {
                cout << k << " " << l << endl;
            }
        }
    }
    return 0;
}
</vector></vector></iostream>