A - Cookie Quotidien

Énoncé du problème : Étant donné une chaîne de caractères de longueur n, où '.' représente une cellule vide et '@' représente un cookie, on consomme un cookie par jour. Combien de cellules sont vides après d jours ?

Approche : Simulation directe.

Code :

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

int main() {
    int longueur, jours;
    string donnees;
    cin >> longueur >> jours >> donnees;
    int nb_cookies = 0;
    for (char symbole : donnees) {
        if (symbole == '@') nb_cookies++;
    }
    int consommes = min(jours, nb_cookies);
    int cellules_vides = longueur - nb_cookies + consommes;
    cout << cellules_vides << endl;
    return 0;
}

B - Cookie Quotidien 2

Énoncé du problème : Identique à A, mais on mange le cookie le plus à droite chaque jour. Afficher l'état final de la chaîne.

Approche : Siumlation par parcours inverse.

Code :

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

int main() {
    int taille, objectif;
    string sequence;
    cin >> taille >> objectif >> sequence;
    int mange = 0;
    for (int idx = taille - 1; idx >= 0; idx--) {
        if (sequence[idx] == '@') {
            sequence[idx] = '.';
            mange++;
            if (mange == objectif) {
                cout << sequence << endl;
                return 0;
            }
        }
    }
    cout << sequence << endl;
    return 0;
}

C - Sushi Tournant

Énoncé du problème : n sushis avec des valeurs b_i ; m personnes avec des seuils a_i. Les sushis passent sur un tapis roulant. Une personne i mange un sushi j si a_i ≥ b_j, sinon elle ne fait rien. Trouver pour chaque sushi quelle personne le mange, ou -1 si personne ne le mange.

Approche : Identifier les personnes effectives (séquence décroissante des seuils), trier les sushis par valeur décroissante, puis assigner par recherche binaire.

Code :

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

int rechercherSeuil(vector<pair<int, int>>& personnes, int valeur) {
    int gauche = 0, droite = personnes.size();
    while (gauche < droite) {
        int milieu = gauche + (droite - gauche) / 2;
        if (personnes[milieu].first >= valeur) {
            gauche = milieu + 1;
        } else {
            droite = milieu;
        }
    }
    return gauche;
}

int main() {
    int nb_sushis, nb_personnes;
    cin >> nb_sushis >> nb_personnes;
    vector<int> valeurs_sushi(nb_sushis);
    for (int i = 0; i < nb_sushis; i++) {
        cin >> valeurs_sushi[i];
    }
    vector<pair<int, int>> personnes_effectives;
    int minimum = valeurs_sushi[0];
    personnes_effectives.push_back({valeurs_sushi[0], 1});
    for (int i = 1; i < nb_sushis; i++) {
        if (valeurs_sushi[i] < minimum) {
            minimum = valeurs_sushi[i];
            personnes_effectives.push_back({valeurs_sushi[i], i + 1});
        }
    }
    vector<pair<int, int>> attentes(nb_personnes);
    for (int i = 0; i < nb_personnes; i++) {
        cin >> attentes[i].first;
        attentes[i].second = i;
    }
    sort(attentes.begin(), attentes.end(), greater<pair<int, int>>());
    vector<int> resultat(nb_personnes, -1);
    int position = 0;
    for (auto& p : personnes_effectives) {
        int seuil = p.first;
        int index_personne = p.second;
        int prochain = rechercherSeuil(attentes, seuil);
        for (int j = position; j < prochain; j++) {
            resultat[attentes[j].second] = index_personne;
        }
        position = prochain;
    }
    for (int i = 0; i < nb_personnes; i++) {
        cout << resultat[i] << endl;
    }
    return 0;
}

D - Maintenir la Distance

Énoncé du problème : Étant donné n (n ≤ 12) et m (10×n-9 ≤ m ≤ 10×m), afficher dans l'ordre lexicographique toutes les séquences A de longueur n telles que A_{i-1} + 10 ≤ A_i et 1 ≤ A_i ≤ m.

Approche : Recherche en profondeur avec élagage basé sur la contrainte de distance.

Code :

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

int limite, longueur_seq;
vector<int> courante;
vector<vector<int>> solutions;

void explorer(int valeur) {
    if (courante.size() == longueur_seq) {
        solutions.push_back(courante);
        return;
    }
    for (int prochain = valeur + 10; prochain + (longueur_seq - courante.size() - 1) * 10 <= limite; prochain++) {
        courante.push_back(prochain);
        explorer(prochain);
        courante.pop_back();
    }
}

int main() {
    cin >> longueur_seq >> limite;
    for (int depart = 1; depart <= 10; depart++) {
        courante.push_back(depart);
        explorer(depart);
        courante.pop_back();
    }
    cout << solutions.size() << endl;
    for (auto& seq : solutions) {
        for (size_t i = 0; i < seq.size(); i++) {
            cout << seq[i];
            if (i < seq.size() - 1) cout << " ";
        }
        cout << endl;
    }
    return 0;
}

E - Paquets d'Expansion

Énoncé du problème : Un paquet de cartes contient n cartes, la i-ème carte a une probabilité p% d'être rare. Les tirages sont indépendants. Calculer l'espérance du nombre de paquets à ouvrir pour obtenir au moins x cartes rares.

Approche : Programmation dynamique pour calculer les probabilités et utiliser la formule de l'espérance conditionnelle.

Code :

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

const int MAXN = 5005;
double prob[MAXN][MAXN];
double esperance[MAXN];

int main() {
    int n, x;
    cin >> n >> x;
    vector<double> probabilites(n + 1);
    for (int i = 1; i <= n; i++) {
        int pourcentage;
        cin >> pourcentage;
        probabilites[i] = pourcentage * 1.0 / 100;
    }
    prob[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            prob[i][j] = prob[i - 1][j] * (1 - probabilites[i]);
            if (j > 0) {
                prob[i][j] += prob[i - 1][j - 1] * probabilites[i];
            }
        }
    }
    for (int objectif = 1; objectif <= x; objectif++) {
        double somme = 0;
        double denominateur = 1 - prob[n][0];
        for (int k = 1; k < n; k++) {
            if (k < objectif) {
                somme += prob[n][k] * esperance[objectif - k];
            }
        }
        esperance[objectif] = (somme + 1) / denominateur;
    }
    cout << fixed << setprecision(12) << esperance[x] << endl;
    return 0;
}