1. Élimination des positions impaires

Énoncé

Étant donné une séquence contenant tous les entiers de 0 à n en ordre croissant, on applique un filtrage répété : à chaque passage, on supprime les éléments situés aux positions impaires. On répète cette opération jusqu'à ce qu'il ne reste qu'un seul nombre. Il faut déterminer ce dernier nombre survivant.

Contrainte : 1 ≤ n ≤ 1000, entrées multiples possibles.

Approche 1 — Simulation avec une file

On modélise directement le processus d'élimination à l'aide d'une file (queue). À chaque tour, on parcourt la file actuelle et on ne ré-insère que les éléments en position paire. La taille est divisée par deux à chaque itération.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int limite;
    cin >> limite;
    
    queue<int> file;
    for (int val = 0; val <= limite; val++) {
        file.push(val);
    }
    
    int nbElements = limite + 1;
    while (nbElements > 1) {
        for (int pos = 1; pos <= nbElements; pos++) {
            if (pos % 2 == 0) {
                file.push(file.front());
            }
            file.pop();
        }
        nbElements /= 2;
    }
    
    cout << file.front() << endl;
    return 0;
}

Approche 2 — Solution mathématique

En observant le motif des résultats, on constate que le dernier survivant est toujours la plus grande puissance de deux moins un qui est inférieure ou égale à n. On peut donc calculer driectement la réponse sans simulation.

#include <iostream>

using namespace std;

int main() {
    int valeur;
    while (cin >> valeur) {
        int puissance = 1;
        while (puissance - 1 <= valeur) {
            puissance <<= 1;
        }
        cout << (puissance >> 1) - 1 << endl;
    }
    return 0;
}

2. Recherche de combinaisons dont la somme vaut m

Énoncé

Étant donné deux entiers n et m, on cherche toutes les combinaisons possibles de nombres pris dans la séquence 1, 2, 3, …, n dont la somme est exactement m. Les combinaisons doivent être affichées dans l'ordre lexicographique.

Contrainte : n, m ≤ 10.

Approche — Parcours avec retour arrière (backtracking)

On explore chaque nombre de 1 à n en décidant de l'inclure ou non dans la combinaison courante. Un élagage (pruning) est ajouté : si la somme partielle dépasse déjà m, on arrête la branche immédiatement.

#include <iostream>
#include <vector>

using namespace std;

int limite, cible;

void explorer(vector<int>& chemin, int idx, int cumul) {
    if (cumul == cible) {
        for (int& x : chemin) cout << x << ' ';
        cout << '\n';
        return;
    }
    if (idx > limite || cumul > cible) return;
    
    // Inclure le nombre courant
    chemin.push_back(idx);
    explorer(chemin, idx + 1, cumul + idx);
    chemin.pop_back();
    
    // Exclure le nombre courant
    explorer(chemin, idx + 1, cumul);
}

int main() {
    cin >> limite >> cible;
    vector<int> chemin;
    explorer(chemin, 1, 0);
    return 0;
}

3. Distance d'édition de Levenshtein

Énoncé

La distance de Levenshtein mesure le nombre minimal d'opérations d'édition nécessaires pour transformer une chaîne en une autre. Les opérations autorisées sont : remplacer un caractère, insérer un carractère et supprimer un caractère.

Par exemple, pour transformer "abcdefg" en "abcdef", il suffit de supprimer le caractère "g", ce qui coûte une seule opération.

Contrainte : 1 ≤ longueur des chaînes ≤ 1000.

Approche — Programmation dynamique

On construit une matrice matrice[i][j] représentant la distance d'édition entre le préfixe de longueur i de la première chaîne et le préfixe de longueur j de la seconde.

Transition :

• Si les caractères courants sont identiques : matrice[i][j] = matrice[i-1][j-1]
• Sinon, on prend le minimum parmi les trois opérasions (suppression, insertion, substitution) et on ajoute 1.

Initialisation : matrice[i][0] = i et matrice[0][j] = j (convertir une chaîne vide en une chaîne de longueur k coûte k insertions).

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

using namespace std;

const int MAX_LEN = 1010;
int matrice[MAX_LEN][MAX_LEN];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int long1 = s1.size(), long2 = s2.size();
    
    for (int i = 0; i <= long1; i++) matrice[i][0] = i;
    for (int j = 0; j <= long2; j++) matrice[0][j] = j;
    
    for (int i = 1; i <= long1; i++) {
        for (int j = 1; j <= long2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                matrice[i][j] = matrice[i - 1][j - 1];
            } else {
                matrice[i][j] = 1 + min({matrice[i - 1][j], matrice[i][j - 1], matrice[i - 1][j - 1]});
            }
        }
    }
    
    cout << matrice[long1][long2] << endl;
    return 0;
}