Optimisation des entraînements militaires

Approche gloutonne : Trier les soldats par nombre d'entraînements nécessaires. Calculer le coût total actuel et comparer avec le coût groupé pour prendre la décision optimale à chaque étape.

#include <iostream>
#include <vector>
#include <algorithm>

struct Soldat {
    long long prix;
    long long sessions;
};

bool comparer(const Soldat& a, const Soldat& b) {
    return a.sessions < b.sessions;
}

void resoudre() {
    int n;
    long long s;
    std::cin >> n >> s;
    
    std::vector<Soldat> troupes(n);
    long long cout_total = 0;
    for (auto& soldat : troupes) {
        std::cin >> soldat.prix >> soldat.sessions;
        cout_total += soldat.prix;
    }
    
    std::sort(troupes.begin(), troupes.end(), comparer);
    
    long long resultat = 0;
    long long sessions_effectuees = 0;
    
    for (const auto& soldat : troupes) {
        long long delta = soldat.sessions - sessions_effectuees;
        if (s < cout_total) {
            resultat += s * delta;
            sessions_effectuees = soldat.sessions;
        } else {
            resultat += soldat.prix * delta;
        }
        cout_total -= soldat.prix;
    }
    
    std::cout << resultat << std::endl;
}

int main() {
    resoudre();
    return 0;
}

Vérification de parties de Gomoku

Utilisation d'une recherche en profondeur pour générer toutes les configurations possibles d'une grille 5x5, avec élagage basé sur le comtpage des coups et la validation des alignements.

#include <vector>
#include <iostream>

int grille[6][6];
int compteur = 0;

bool valider_grille() {
    int countX = 0, countO = 0;
    for (int i = 1; i <= 5; i++) {
        for (int j = 1; j <= 5; j++) {
            if (grille[i][j] == 1) countX++;
            else if (grille[i][j] == 2) countO++;
        }
    }
    if (countX - countO != 1) return false;

    for (int i = 1; i <= 5; i++) {
        bool ligne_identique = true;
        for (int j = 2; j <= 5; j++) {
            if (grille[i][j] != grille[i][1] || grille[i][j] == 0) {
                ligne_identique = false;
                break;
            }
        }
        if (ligne_identique) return false;
    }

    for (int j = 1; j <= 5; j++) {
        bool colonne_identique = true;
        for (int i = 2; i <= 5; i++) {
            if (grille[i][j] != grille[1][j] || grille[i][j] == 0) {
                colonne_identique = false;
                break;
            }
        }
        if (colonne_identique) return false;
    }

    bool diag1 = true;
    for (int i = 2; i <= 5; i++) {
        if (grille[i][i] != grille[1][1] || grille[i][i] == 0) {
            diag1 = false;
            break;
        }
    }
    if (diag1) return false;

    bool diag2 = true;
    for (int i = 2; i <= 5; i++) {
        if (grille[i][6-i] != grille[1][5] || grille[i][6-i] == 0) {
            diag2 = false;
            break;
        }
    }
    if (diag2) return false;

    return true;
}

void explorer(int ligne, int colonne, int nbX, int nbO) {
    if (colonne == 6) {
        explorer(ligne + 1, 1, nbX, nbO);
        return;
    }
    if (ligne == 6) {
        if (valider_grille()) compteur++;
        return;
    }

    int restant = 25 - ((ligne-1)*5 + (colonne-1)) - 1;
    grille[ligne][colonne] = 1;
    if (nbX + 1 - nbO <= restant + 1) {
        explorer(ligne, colonne+1, nbX+1, nbO);
    }
    grille[ligne][colonne] = 2;
    if (nbX - (nbO + 1) <= restant + 1) {
        explorer(ligne, colonne+1, nbX, nbO+1);
    }
    grille[ligne][colonne] = 0;
}

int main() {
    explorer(1, 1, 0, 0);
    std::cout << compteur << std::endl;
    return 0;
}

Analyse statistique des performances

Calcul de la variance pour des sous-séquences en utilisant des sommes préfixées et des carrés préfixés, avec recherche binaire pour déterminer la longueur minimale satisfaisant une condition donnée.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

bool verifier_sous_sequence(const std::vector<long long>& valeurs, int debut, int fin, long long seuil) {
    long long somme = 0;
    long long somme_carres = 0;
    for (int i = debut; i <= fin; i++) {
        somme += valeurs[i];
        somme_carres += valeurs[i] * valeurs[i];
    }
    int k = fin - debut + 1;
    double variance = (double)somme_carres - (double)(somme * somme) / k;
    return variance <= k * seuil;
}

int trouver_longueur_minimale(int n, int k, long long T, const std::vector<long long>& scores) {
    int gauche = k, droite = n + 1;
    while (gauche < droite) {
        int milieu = (gauche + droite) / 2;
        bool possible = false;
        for (int i = 0; i <= n - milieu; i++) {
            if (verifier_sous_sequence(scores, i, i + milieu - 1, T)) {
                possible = true;
                break;
            }
        }
        if (possible) {
            droite = milieu;
        } else {
            gauche = milieu + 1;
        }
    }
    return gauche > n ? -1 : gauche;
}

int main() {
    int n, k;
    long long T;
    std::cin >> n >> k >> T;
    
    std::vector<long long> scores(n);
    for (auto& score : scores) {
        std::cin >> score;
    }
    
    int resultat = trouver_longueur_minimale(n, k, T, scores);
    std::cout << resultat << std::endl;
    
    return 0;
}