Problème 1 : Pluie de Météores de l'Ère

Ce problème ne présente pas de difficulté majeure et peut être résolu par une simulation simple.

Approche de Résolution

1. Déterminez l'âge de l'individu lors de la première apparition de la pluie de météores de sa vie. La pluie de météores se produit tous les 50 ans. Si E est l'année de début d'une ère et B est l'année de naissance de la personne, alors l'âge à la première observation est donné par la formule (E + B) % 50.
2. Si cet âge initial est supérieur à la durée de vie totale L, la personne n'observera aucune pluie de météores.
3. Sinon, calculez le nombre d'années restantes dans la vie de la personne après cette première observation : années_restantes = L - âge_première_observation.
4. Le nombre total de pluies de météores observées sera années_restantes / 50 + 1 (le +1 inclut la première pluie de météores).

Implémentation en C++

#include <iostream>

// Fonction pour calculer le nombre de pluies de météores observées
int calculer_pluies(int annee_naissance, int duree_vie, int debut_ere) {
    // Calcule l'âge de la personne à la première observation,
    // selon la convention du problème: (debut_ere + annee_naissance) % 50
    int age_premiere_observation = (debut_ere + annee_naissance) % 50;

    // Si la première observation a lieu après la durée de vie, aucune n'est vue.
    if (age_premiere_observation > duree_vie) {
        return 0;
    }

    // Années restantes dans la vie après la première observation.
    int vie_restante_apres_premiere = duree_vie - age_premiere_observation;

    // Nombre de cycles de 50 ans dans la vie restante, plus la première observation.
    return vie_restante_apres_premiere / 50 + 1;
}

int main() {
    std::ios_base::sync_with_stdio(false); // Optimisation des E/S
    std::cin.tie(NULL);                   // Optimisation des E/S

    int nombre_tests;
    std::cin >> nombre_tests;
    while (nombre_tests--) {
        int val_B, val_L, val_E;
        std::cin >> val_B >> val_L >> val_E;
        std::cout << calculer_pluies(val_B, val_L, val_E) << '\n';
    }
    return 0;
}

Implémentation en Python

def compter_pluies_meteores(annee_naissance, age_max, debut_ere):
    # Détermine l'âge auquel la première pluie de météores apparaît.
    # Ceci suit l'interprétation spécifique du problème (E+B) % 50 comme l'âge.
    age_premiere_pluie = (debut_ere + annee_naissance) % 50
    
    if age_premiere_pluie > age_max:
        return 0  # Aucune pluie observée si la première est après la durée de vie

    # Calcule les années restantes dans la vie après la première pluie observée
    annees_restantes = age_max - age_premiere_pluie
    
    # Compte combien de cycles complets de 50 ans s'intègrent dans les années restantes,
    # et ajoute 1 pour la pluie initiale elle-même.
    return annees_restantes // 50 + 1

def fonction_principale_pluies():
    nombre_cas = int(input())
    for _ in range(nombre_cas):
        val_B, val_L, val_E = map(int, input().split())
        print(compter_pluies_meteores(val_B, val_L, val_E))

if __name__ == "__main__":
    fonction_principale_pluies()

Problème 2 : MARCOncaténation

Il s'agit de simuler une opération de concaténation de chaînes de caractères selon une règle spécifique d'appariement de préfixes/suffixes.

Approche de Résolution

L'objectif est de trouver le plus long préfixe de la chaîne d'entrée S qui est également un suffixe de la chaîne "marco" (en minuscules). Une fois ce plus long chevauchement trouvé, on remplace cette partie de S par "MARCO" (en majuscules) et on y concatène le reste de S après le chevauchement. Si aucun chevauchement n'est trouvé, la chaîne d'origine est renvoyée.

Implémentation en C++

#include <iostream>
#include <string>
#include <algorithm> // Pour std::min

std::string traiter_chaine(const std::string& chaine_entree) {
    std::string patron_minuscules = "marco";
    std::string patron_majuscules = "MARCO";
    
    int longueur_chevauchement_max = 0;
    // Parcourir de la plus longue longueur de chevauchement possible (5) à 1.
    // Les bornes de la boucle: i va de min(taille de chaine_entree, 5) jusqu'à 1.
    for (int i = std::min((int)chaine_entree.size(), 5); i >= 1; --i) {
        // Vérifier si le préfixe de chaine_entree de longueur i
        // correspond au suffixe de 'marco' de longueur i.
        if (chaine_entree.substr(0, i) == patron_minuscules.substr(5 - i, i)) {
            longueur_chevauchement_max = i;
            break; // Le plus long chevauchement est trouvé, inutile de vérifier les plus courts
        }
    }

    if (longueur_chevauchement_max == 0) {
        return chaine_entree; // Pas de chevauchement, retourne la chaîne originale
    } else {
        // Concatène "MARCO" avec la partie de chaine_entree après le chevauchement.
        return patron_majuscules + chaine_entree.substr(longueur_chevauchement_max);
    }
}

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

    int nombre_cas;
    std::cin >> nombre_cas;
    while (nombre_cas--) {
        std::string chaine_actuelle;
        std::cin >> chaine_actuelle;
        std::cout << traiter_chaine(chaine_actuelle) << '\n';
    }
    return 0;
}

Implémentation en Python

def modifier_sequence_texte(sequence_entree: str) -> str:
    prefixe_standard_min = "marco"
    prefixe_standard_maj = "MARCO"
    
    longueur_max_chevauchement = 0
    
    # Parcourir les longueurs de chevauchement de 1 à 5 (ou la longueur de sequence_entree si plus courte)
    # L'algorithme original parcourt du plus long au plus court. Gardons cette logique en stockant le plus long valide.
    for longueur_actuelle in range(min(len(sequence_entree), 5), 0, -1):
        # Vérifier si le préfixe de sequence_entree correspond au suffixe de prefixe_standard_min
        if sequence_entree[0:longueur_actuelle] == prefixe_standard_min[5 - longueur_actuelle:]:
            longueur_max_chevauchement = longueur_actuelle
            break # Trouvé le plus long chevauchement, on peut arrêter

    if longueur_max_chevauchement == 0:
        return sequence_entree
    else:
        return prefixe_standard_maj + sequence_entree[longueur_max_chevauchement:]

def executer_tests():
    nombre_cas_tests = int(input())
    for _ in range(nombre_cas_tests):
        chaine_input = input()
        print(modifier_sequence_texte(chaine_input))

if __name__ == '__main__':
    executer_tests()

Problème 3 : Relais TNT

Le joueur doit traverser un pont constitué de N blocs. Certains blocs sont solides (#), d'autres sont fragiles (-). Le joueur peut sauter jusqu'à K blocs. Si le joueur atterrit sur un bloc fragile, il tombe. Pour traverser en toute sécurité, il faut placer des blocs de TNT sur certains blocs fragiles pour les rendre solides. Le but est de minimiser le nombre de TNT nécessaires.

Approche de Résolution

Le problème peut être résolu en utilisant une technique de fenêtre glissante. Chaque fois que le joueur fait un saut, il couvre une portée de K+1 blocs (son bloc de départ plus les K blocs qu'il peut atteindre). Pour garantir la sécurité, dans toute fenêtre de K+1 blocs, il ne doit pas y avoir trop de blocs fragiles. Plus précisément, si on veut minimiser le TNT, on doit maximiser le nombre de blocs solides ou "sûrs" dans chaque fenêtre. Si une fenêtre de K+1 blocs contient X blocs fragiles, il faut X TNT pour la rendre complètement sûre. Cependant, la question est de garantir que le joueur puisse toujours atteindre un bloc sûr. La condition de sécurité est que le joueur puisse toujours sauter d'un bloc sûr à un autre bloc sûr dans sa portée de K blocs. Autrement dit, dans toute séquence de K+1 blocs consécutifs, il ne doit pas y avoir plus de K blocs fragiles. Le nombre minimum de TNT à placer dans une telle séquence est (K+1) - (nombre maximal de blocs solides dans la fenêtre). Ou de manière équivalente, (K+1) - (nombre maximal de blocs non fragiles dans la fenêtre).

1. Définissez la taille de la fenêtre de sécurité : TailleFenetre = K + 1.
2. Si K >= N, le joueur peut sauter par-dessus tout le pont, donc la réponse est -1 (pas besoin de TNT).
3. Utilisez une fenêtre glissante de taille TailleFenetre. Pour chaque fenêtre, comptez le nombre de blocs fragiles (-).
4. Maintenez un maximum global des blocs fragiles rencontrés dans n'importe quelle fenêtre.
5. Le nombre minimum de TNT requis est TailleFenetre - max_fragiles_dans_fenetre.

Implémentation en C++

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

int determiner_min_tnt(int total_blocs, int portee_saut, const std::string& sequence_blocs) {
    // Si la portée de saut couvre tout le pont, aucun TNT n'est nécessaire.
    if (portee_saut >= total_blocs) {
        return -1;
    }

    // La taille effective de la fenêtre de danger est K+1 blocs.
    // Le joueur peut sauter K blocs, donc la distance entre son point de départ
    // et son point d'arrivée le plus éloigné est K.
    // La fenêtre considérée est de longueur (portee_saut + 1).
    int taille_fenetre = portee_saut + 1;
    int max_blocs_vides_fenetre = 0; // Compte max de '-' dans n'importe quelle fenêtre
    int compte_vides_actuel = 0;     // Compte actuel de '-' dans la fenêtre glissante

    // Initialiser la première fenêtre
    for (int i = 0; i < taille_fenetre; ++i) {
        if (sequence_blocs[i] == '-') {
            compte_vides_actuel++;
        }
    }
    max_blocs_vides_fenetre = compte_vides_actuel;

    // Faire glisser la fenêtre
    for (int i = taille_fenetre; i < total_blocs; ++i) {
        // Ajouter le nouvel élément à droite
        if (sequence_blocs[i] == '-') {
            compte_vides_actuel++;
        }
        // Retirer l'ancien élément à gauche
        if (sequence_blocs[i - taille_fenetre] == '-') {
            compte_vides_actuel--;
        }
        // Mettre à jour le maximum
        max_blocs_vides_fenetre = std::max(max_blocs_vides_fenetre, compte_vides_actuel);
    }

    // Le nombre minimum de TNT nécessaire est la taille de la fenêtre moins le nombre maximum de blocs non fragiles.
    // Ou, comme formulé dans l'original, TailleFenetre - max_vides_fenetre
    return taille_fenetre - max_blocs_vides_fenetre;
}

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

    int nombre_cas_tests;
    std::cin >> nombre_cas_tests;
    while (nombre_cas_tests--) {
        int val_N, val_K;
        std::cin >> val_N >> val_K;
        std::string val_S;
        std::cin >> val_S;
        std::cout << determiner_min_tnt(val_N, val_K, val_S) << '\n';
    }
    return 0;
}

Implémentation en Python

def calculer_tnt_necessaire(nombre_blocs: int, distance_saut_max: int, types_blocs: str) -> int:
    if distance_saut_max >= nombre_blocs:
        return -1  # Le joueur peut traverser directement

    # Une fenêtre de taille (distance_saut_max + 1) représente le segment de pont
    # qui doit être sûr.
    longueur_segment = distance_saut_max + 1
    
    compteur_blocs_fragiles_actuel = 0
    max_blocs_fragiles_segment = 0

    # Initialiser le compte pour le premier segment
    for i in range(longueur_segment):
        if types_blocs[i] == '-':
            compteur_blocs_fragiles_actuel += 1
    max_blocs_fragiles_segment = compteur_blocs_fragiles_actuel

    # Faire glisser la fenêtre sur le reste du pont
    for i in range(longueur_segment, nombre_blocs):
        # Ajouter le nouveau bloc entrant dans la fenêtre
        if types_blocs[i] == '-':
            compteur_blocs_fragiles_actuel += 1
        # Retirer le bloc sortant de la fenêtre
        if types_blocs[i - longueur_segment] == '-':
            compteur_blocs_fragiles_actuel -= 1
        
        # Mettre à jour le maximum de blocs fragiles trouvés dans n'importe quel segment
        max_blocs_fragiles_segment = max(max_blocs_fragiles_segment, compteur_blocs_fragiles_actuel)
    
    # Le TNT minimum nécessaire pour n'importe quel segment critique est sa longueur moins le maximum de blocs fragiles qu'il contenait.
    return longueur_segment - max_blocs_fragiles_segment

def main_tnt_relay():
    nombre_tests = int(input())
    for _ in range(nombre_tests):
        n_str, k_str = input().split()
        val_N, val_K = int(n_str), int(k_str)
        val_S = input()
        print(calculer_tnt_necessaire(val_N, val_K, val_S))

if __name__ == '__main__':
    main_tnt_relay()

Problème 4 : Évaluation de Main de Poker Spéciale

Ce problème demande d'évaluer une main de cinq cartes selon des règles de poker spécifiques, incluant une interprétation particulière pour les "cinq d'une sorte" et la résolution des conflits de type de main.

Règles Spécifiques

1. Une même valeur de carte peut apparaître cinq fois. Dans ce cas, la main est classée comme "High Card" (carte haute) selon la règle spécifique du problème.
2. Si une main correspond à plusieurs descriptions, la sortie doit être le type de main décrit en dernier dans la liste des règles (ce qui signifie généralement que l'on vérifie de la priorité la plus élevée à la plus basse, et la première correspondance valide est celle retenue).
3. Le nombre de cartes n'est pas limité aux jeux de poker traditionnels, et chaque carte peut avoir l'une des quatre couleurs spécifiées.

Approche de Résolution

Nous devons lire cinq cartes, les convertir en une représentation numérique pour faciliter la comparaison et le tri, puis analyser leurs propriétés (valeurs, couleurs) pour déterminer le type de main. Le tri est essentiel pour détecter les suites. Nous compterons les fréquences des valeurs pour identifier les paires, brelans, carrés, etc. Enfin, nous appliquerons les règles de détermination du type de main en tenant compte des particularités du problème.

Implémentation en C++

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

// Structure pour représenter une carte à jouer
struct Carte {
    int valeur_numerique;
    std::string couleur;

    // Opérateur de comparaison pour trier les cartes par valeur
    bool operator<(const Carte& autre) const {
        return valeur_numerique < autre.valeur_numerique;
    }
};

// Fonction pour convertir la valeur de la carte en chaîne en valeur numérique
int obtenir_valeur_rang(const std::string& rang_str) {
    if (rang_str == "J") return 11;
    if (rang_str == "Q") return 12;
    if (rang_str == "K") return 13;
    if (rang_str == "A") return 14; // L'As est la carte la plus haute
    if (rang_str == "10") return 10;
    return rang_str[0] - '0'; // Pour les cartes 2-9
}

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

    int nombre_cas_tests;
    std::cin >> nombre_cas_tests;
    while (nombre_cas_tests--) {
        std::vector<Carte> main_joueur(5);
        for (int i = 0; i < 5; ++i) {
            std::string rang_str, couleur_str;
            std::cin >> rang_str >> couleur_str;
            main_joueur[i] = {obtenir_valeur_rang(rang_str), couleur_str};
        }

        // Trier les cartes pour faciliter la vérification des suites et séquences
        std::sort(main_joueur.begin(), main_joueur.end());

        // --- Analyser les propriétés de la main ---
        int compte_valeurs[15] = {0}; // Fréquences des valeurs (indices 2-14)
        bool toutes_meme_couleur = true;
        bool est_suite = true; // Supposé trié
        int nombre_paires = 0;
        int frequence_max_valeur = 0;

        for (int i = 0; i < 5; ++i) {
            compte_valeurs[main_joueur[i].valeur_numerique]++;
            frequence_max_valeur = std::max(frequence_max_valeur, compte_valeurs[main_joueur[i].valeur_numerique]);

            if (i > 0) {
                if (main_joueur[i].couleur != main_joueur[i-1].couleur) {
                    toutes_meme_couleur = false;
                }
                if (main_joueur[i].valeur_numerique != main_joueur[i-1].valeur_numerique + 1) {
                    est_suite = false;
                }
            }
        }
        
        // Compter les paires
        for (int i = 2; i <= 14; ++i) {
            if (compte_valeurs[i] == 2) {
                nombre_paires++;
            }
        }

        // --- Déterminer le type de main selon les règles spécifiques ---
        // Les types de mains sont vérifiés par ordre de priorité décroissante.
        std::string type_main_resultat;

        if (est_suite && toutes_meme_couleur) {
            if (main_joueur[4].valeur_numerique == 14) type_main_resultat = "Royal Flush"; // Quinte Flush Royale (As-haut)
            else type_main_resultat = "Straight Flush"; // Quinte Flush
        } else if (frequence_max_valeur == 4) {
            type_main_resultat = "Four of a Kind"; // Carré
        } else if (frequence_max_valeur == 3 && nombre_paires == 1) { // Brelan ET une paire = Full House
            type_main_resultat = "Full House"; // Full
        } else if (est_suite) {
            type_main_resultat = "Straight"; // Suite
        } else if (frequence_max_valeur == 3) { // Seulement Brelan, pas de paire supplémentaire
            type_main_resultat = "Three of a Kind"; // Brelan
        } else if (nombre_paires == 2) {
            type_main_resultat = "Two Pairs"; // Deux paires
        } else if (nombre_paires == 1) {
            type_main_resultat = "One Pair"; // Une paire
        } else {
            type_main_resultat = "High Card"; // Carte haute
        }

        // Application de la règle spécifique: "si la même valeur apparaît cinq fois, la main est High Card"
        if (frequence_max_valeur == 5) {
            type_main_resultat = "High Card"; // Annule tout autre type de main
        }
        
        std::cout << type_main_resultat << '\n';
    }
    return 0;
}

Problème 5 : Verset de Sommet (Vertex Verse)

Le problème consiste à analyser les connexions dans un réseau de points organisé en grille N x M. Des paires de points (r1, c1)-(r2, c2) sont connectées séquentiellement. Après chaque connexion, nous devons compter le nombre de carrés complets de 1x1 unité qui sont formés par les arêtes existantes. Il y a deux joueurs, et chacun à tour de rôle connecte une paire de points.

Approche de Résolution

Les points peuvent être pensés comme des nœuds dans un graphe sur une grille 2D. Lorsque deux points sont connectés, une arête est ajoutée. Un carré 1x1 est formé par quatre points adjacents dans la grille. Pour une arête nouvellement ajoutée (P_A, P_B), elle ne peut former un nouveau carré que si elle en est le quatrième côté. Nous devons vérifier les deux carrés possibles adjacents à (P_A, P_B) et voir si leurs trois autres arêtes existent déjà. Nous utiliserons une carte pour stocker les arêtes existantes, où chaque arête est représentée par une paire de coordonnées canoniques (min_coord, max_coord).

Implémentation en C++

#include <iostream>
#include <vector>
#include <map>
#include <utility> // Pour std::pair
#include <algorithm> // Pour std::swap

// Une carte pour stocker les arêtes existantes.
// La clé est une paire de std::pair<int, int> représentant les deux points d'une arête (dans l'ordre canonique).
// La valeur est un int (1 si l'arête existe, 0 sinon).
std::map<std::pair<std::pair<int, int>, std::pair<int, int>>, int> carte_adjacence;

// Fonction utilitaire pour obtenir une représentation canonique d'une arête (le point le plus petit en premier)
std::pair<std::pair<int, int>, std::pair<int, int>> obtenir_arete_canonique(std::pair<int, int> p1, std::pair<int, int> p2) {
    if (p1 > p2) {
        std::swap(p1, p2);
    }
    return std::make_pair(p1, p2);
}

// Fonction pour vérifier si les quatre arêtes formant un carré existent
bool verifier_carre_existe(std::pair<int, int> p1, std::pair<int, int> p2,
                            std::pair<int, int> p3, std::pair<int, int> p4) {
    // Les quatre arêtes d'un carré avec sommets p1, p2, p3, p4 (où p1 et p4 sont en diagonale, p2 et p3 sont adjacents à p1)
    // sont (p1, p2), (p1, p3), (p2, p4), (p3, p4).
    return carte_adjacence[obtenir_arete_canonique(p1, p2)] &&
           carte_adjacence[obtenir_arete_canonique(p1, p3)] &&
           carte_adjacence[obtenir_arete_canonique(p2, p4)] &&
           carte_adjacence[obtenir_arete_canonique(p3, p4)];
}

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

    int lignes_grille, cols_grille, nombre_requetes;
    std::cin >> lignes_grille >> cols_grille >> nombre_requetes;

    // Chaque requête comprend deux opérations (une pour Macw, une pour Alex)
    // Nous traitons donc 2*nombre_requetes connexions.
    int scores_joueurs[2] = {0, 0}; // [Score Macw, Score Alex]

    for (int i = 0; i < 2 * nombre_requetes; ++i) {
        std::pair<int, int> point_A, point_B; // Points d'extrémité de l'arête actuelle
        std::cin >> point_A.first >> point_A.second >> point_B.first >> point_B.second;

        // Obtenir la représentation canonique de l'arête
        auto arete_actuelle_canonique = obtenir_arete_canonique(point_A, point_B);

        // Si l'arête existe déjà, elle ne peut pas former de nouveau carré.
        if (carte_adjacence[arete_actuelle_canonique] > 0) {
            continue;
        }
        
        // Marquer l'arête comme existante.
        carte_adjacence[arete_actuelle_canonique]++;

        // Vérifier les carrés potentiellement formés par cette nouvelle arête.
        // L'arête (point_A, point_B) est un côté d'un carré.
        // Il y a deux positions possibles pour un carré qui utilise cette arête.

        if (point_A.first == point_B.first) { // Arête horizontale: (r, c) à (r, c+1)
            // Vérifier le carré "au-dessus" (r-1,c)-(r-1,c+1)-(r,c+1)-(r,c)
            std::pair<int, int> p_haut_gauche = {point_A.first + 1, point_A.second};
            std::pair<int, int> p_haut_droite = {point_B.first + 1, point_B.second};
            if (point_A.first + 1 <= lignes_grille && verifier_carre_existe(point_A, point_B, p_haut_gauche, p_haut_droite)) {
                scores_joueurs[i % 2]++;
            }

            // Vérifier le carré "en-dessous" (r+1,c)-(r+1,c+1)-(r,c+1)-(r,c)
            std::pair<int, int> p_bas_gauche = {point_A.first - 1, point_A.second};
            std::pair<int, int> p_bas_droite = {point_B.first - 1, point_B.second};
            if (point_A.first - 1 >= 1 && verifier_carre_existe(p_bas_gauche, p_bas_droite, point_A, point_B)) {
                scores_joueurs[i % 2]++;
            }
        } else { // Arête verticale: (r, c) à (r+1, c)
            // Vérifier le carré "à droite" (r,c)-(r+1,c)-(r+1,c+1)-(r,c+1)
            std::pair<int, int> p_droite_haut = {point_A.first, point_A.second + 1};
            std::pair<int, int> p_droite_bas = {point_B.first, point_B.second + 1};
            if (point_A.second + 1 <= cols_grille && verifier_carre_existe(point_A, p_droite_haut, point_B, p_droite_bas)) {
                scores_joueurs[i % 2]++;
            }

            // Vérifier le carré "à gauche" (r,c-1)-(r+1,c-1)-(r+1,c)-(r,c)
            std::pair<int, int> p_gauche_haut = {point_A.first, point_A.second - 1};
            std::pair<int, int> p_gauche_bas = {point_B.first, point_B.second - 1};
            if (point_A.second - 1 >= 1 && verifier_carre_existe(p_gauche_haut, point_A, p_gauche_bas, point_B)) {
                scores_joueurs[i % 2]++;
            }
        }
    }
    std::cout << scores_joueurs[0] << " " << scores_joueurs[1] << '\n';
    return 0;
}

Problème 6 : Emplacement Optimal du Bâtiment Gouvernemental - 2

Il s'agit de trouver l'emplacement optimal (X, Y) pour un nouveau bâtiment gouvernemental afin de minimiser la somme des "intentions" (distances pondérées) de N bâtiments existants. L'intention de chaque bâtiment i est calculée comme ( |X - x_i| + |Y - y_i| ) * w_i, où (x_i, y_i) sont les coordonnées du bâtiment i et w_i est son facteur d'influence.

Approche de Résolution

Le problème de la minimisation de la somme des distances de Manhattan pondérées peut être décomposé en deux problèmes indépendants pour les coordonnées X et Y. Pour chaque dimension, il s'agit de trouver la médiane pondérée. Pour une fonction f(x) = sum(w_i * |x - x_i|), cette fonction est convexe et son minimum est atteint à la médiane pondérée des x_i. La médiane pondérée peut être trouvée efficacement en triant les points et en cherchant le point qui divise la somme des poids en deux moitiés égales, ou par recherche ternaire.

Alternativement, pour des problèmes complexes ou des espaces de recherche multidimensionnels, l'algorithme de recuit simulé (Simulated Annealing) peut être utilisé. Bien que heuristique, il est souvent efficace pour trouver de bonnes solutions dans un temps raisonnable.

Implémentation en C++ (Médiane Pondérée)

#include <iostream>
#include <vector>
#include <cmath>      // Pour std::abs
#include <iomanip>    // Pour std::fixed et std::setprecision
#include <algorithm>  // Pour std::sort (non utilisé directement dans le median, mais utile pour d'autres méthodes)

// Epsilon pour les comparaisons en virgule flottante
constexpr double EPS_PRECISION = 1e-7;

// Fonction pour trouver la médiane pondérée pour une seule dimension.
// Il s'agit du point X qui minimise sum(poids_i * |X - val_i|).
// Cette fonction utilise la recherche ternaire.
double trouver_mediane_ponderee(const std::vector<double>& valeurs, const std::vector<int>& poids) {
    int nombre_points = valeurs.size();
    double borne_inf = -1e3; // Assumer des coordonnées dans une plage raisonnable
    double borne_sup = 1e3;

    // Fonction pour évaluer la somme des distances pondérées pour une coordonnée donnée
    auto evaluer_somme_pour_point = [&](double coord) {
        double distance_ponderee_totale = 0.0;
        for (int i = 0; i < nombre_points; ++i) {
            distance_ponderee_totale += std::abs(coord - valeurs[i]) * poids[i];
        }
        return distance_ponderee_totale;
    };

    // Recherche ternaire pour trouver le minimum d'une fonction convexe
    while (borne_sup - borne_inf > EPS_PRECISION) {
        double un_tiers = borne_inf + (borne_sup - borne_inf) / 3;
        double deux_tiers = borne_sup - (borne_sup - borne_inf) / 3;

        if (evaluer_somme_pour_point(un_tiers) < evaluer_somme_pour_point(deux_tiers)) {
            borne_sup = deux_tiers;
        } else {
            borne_inf = un_tiers;
        }
    }
    return borne_inf; // borne_inf ou borne_sup sont des réponses valides à cette précision
}

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

    int nombre_batiments;
    std::cin >> nombre_batiments;

    std::vector<int> facteurs_influence(nombre_batiments);
    for (int i = 0; i < nombre_batiments; ++i) {
        std::cin >> facteurs_influence[i];
    }

    std::vector<double> coord_x(nombre_batiments);
    std::vector<double> coord_y(nombre_batiments);
    for (int i = 0; i < nombre_batiments; ++i) {
        std::cin >> coord_x[i] >> coord_y[i];
    }

    // Le problème de distance L1 (Manhattan) peut être séparé en problèmes X et Y indépendants.
    double x_optimal = trouver_mediane_ponderee(coord_x, facteurs_influence);
    double y_optimal = trouver_mediane_ponderee(coord_y, facteurs_influence);

    double cout_total_min = 0.0;
    for (int i = 0; i < nombre_batiments; ++i) {
        cout_total_min += (std::abs(x_optimal - coord_x[i]) + std::abs(y_optimal - coord_y[i])) * facteurs_influence[i];
    }

    std::cout << std::fixed << std::setprecision(6) << cout_total_min << '\n';

    return 0;
}

Problème 7 : Ferme de Tortues

C'est un problème classique de programmation dynamique avec compression d'état (DP sur profil). Il s'agit de placer des tortues sur une grille N x M, où certaines cellules sont bloquées et ne peuvent pas cnotenir de tortue. Les règles de placement sont les suivantes : deux tortues ne peuvent pas être adjacentes horizontalement ni verticalement.

Approche de Résolution

Nous utilisons une approche de programmation dynamique où l'état dp[i][j] représente le nombre de façons de placer des tortues jusqu'à la ligne i, avec la ligne i ayant une configuration spécifique représentée par le masque binaire j. Chaque configuration de ligne peut être encodée par un masque binaire de M bits, où un bit à 1 signifie qu'une tortue est placée dans cette colonne.

1. Pré-traitement des terrains : Créez un masque binaire pour chaque ligne indiquant les cellules bloquées. Un bit à 1 dans ce masque signifie que la cellule correspondante est bloquée.
2. Pré-traitement des configurations de lignes valides : Générez toutes les configurations binaires possibles pour une ligne de largeur M. Pour chaque configuration (masque), vérifiez si elle est horizontalement valide (pas deux tortues adjacentes). Cela peut être fait en vérifiant si (masque << 1) & masque est zéro. Stockez ces masques valides dans une liste.
3. Initialisation DP : dp[0][index_masque_vide] = 1, indiquant qu'il y a une façon de ne placer aucune tortue avant la première ligne.
4. Transition DP : Pour chaque ligne r de 1 à N, et pour chaque configuration valide masque_actuel de cette ligne :
   1. Vérifiez si masque_actuel entre en conflit avec les cellules bloquées de la ligne r.
   2. Pour chaque configuration valide masque_precedent de la ligne r-1 :
      1. Vérifiez si masque_precedent entre en conflit avec les cellules bloquées de la ligne r-1.
      2. Vérifiez l'adjacence verticale : (masque_actuel & masque_precedent) doit être zéro (aucune tortue empilée).
      3. Si toutes les conditions sont remplies, ajoutez dp[r-1][index_masque_precedent] à dp[r][index_masque_actuel].
5. Calcul de la réponse finale : La somme de tous les dp[N][j] représente le nombre total de façons de placer des tortues. Soustrayez 1 pour exclure le cas où aucune tortue n'est placée du tout.

Implémentation en C++

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

const int MOD = 1e9 + 7;

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

    int lignes, colonnes;
    std::cin >> lignes >> colonnes;

    // grid_disponibilite[i][j] == 0 si la cellule (i,j) est bloquée, 1 si disponible
    std::vector<std::vector<int>> grid_disponibilite(lignes + 1, std::vector<int>(colonnes + 1));
    for (int i = 1; i <= lignes; ++i) {
        for (int j = 1; j <= colonnes; ++j) {
            std::cin >> grid_disponibilite[i][j];
        }
    }
    
    // `masque_cellules_bloquees[i]` stocke un masque binaire pour la ligne `i`
    // où un '1' au bit `j` indique que la cellule `(i, j)` est bloquée.
    std::vector<int> masque_cellules_bloquees(lignes + 1, 0);
    for (int i = 1; i <= lignes; ++i) {
        for (int j = 1; j <= colonnes; ++j) {
            if (grid_disponibilite[i][j] == 0) { // La cellule est bloquée
                masque_cellules_bloquees[i] |= (1 << (j - 1)); // Positionner le j-ième bit
            }
        }
    }

    // `configurations_ligne_valides` stocke tous les masques binaires qui représentent un arrangement horizontal valide
    // (pas deux tortues adjacentes horizontalement).
    std::vector<int> configurations_ligne_valides;
    for (int i = 0; i < (1 << colonnes); ++i) {
        // Vérifier les '1' adjacents : (i << 1) & i sera non-zéro si i a des '1' adjacents
        if (!((i << 1) & i)) {
            configurations_ligne_valides.push_back(i);
        }
    }

    // `dp[r][idx_masque]` stocke le nombre de façons de placer des tortues jusqu'à la ligne `r`,
    // où la ligne `r` a la configuration `configurations_ligne_valides[idx_masque]`.
    std::vector<std::vector<int>> dp(lignes + 1, std::vector<int>(configurations_ligne_valides.size(), 0));

    // Cas de base : Avant la première ligne (ligne 0), il y a une façon d'avoir une configuration vide.
    // Nous devons trouver l'indice du masque 0 dans `configurations_ligne_valides`.
    int idx_config_vide = -1;
    for(size_t i = 0; i < configurations_ligne_valides.size(); ++i) {
        if (configurations_ligne_valides[i] == 0) {
            idx_config_vide = i;
            break;
        }
    }
    // Le masque 0 est toujours une configuration valide pour M >= 1.
    dp[0][idx_config_vide] = 1;

    // Remplir la table DP
    for (int r = 1; r <= lignes; ++r) {
        for (size_t idx_config_actuelle = 0; idx_config_actuelle < configurations_ligne_valides.size(); ++idx_config_actuelle) {
            int masque_actuel = configurations_ligne_valides[idx_config_actuelle];

            // Si la configuration actuelle place des tortues sur des cellules bloquées, elle est invalide.
            if (masque_actuel & masque_cellules_bloquees[r]) {
                continue;
            }

            // Itérer sur les configurations valides pour la ligne précédente (r-1)
            for (size_t idx_config_precedente = 0; idx_config_precedente < configurations_ligne_valides.size(); ++idx_config_precedente) {
                int masque_precedent = configurations_ligne_valides[idx_config_precedente];

                // Vérifier les conflits avec les cellules bloquées de la ligne précédente (si une tortue est placée sur une cellule bloquée).
                if (masque_precedent & masque_cellules_bloquees[r-1]) {
                    continue;
                }

                // Vérifier l'adjacence verticale : (masque_actuel & masque_precedent) == 0 signifie qu'aucune tortue n'est empilée.
                if (!(masque_actuel & masque_precedent)) {
                    dp[r][idx_config_actuelle] = (dp[r][idx_config_actuelle] + dp[r-1][idx_config_precedente]) % MOD;
                }
            }
        }
    }

    // Sommer toutes les configurations valides pour la dernière ligne
    int total_solutions = 0;
    for (size_t i = 0; i < configurations_ligne_valides.size(); ++i) {
        total_solutions = (total_solutions + dp[lignes][i]) % MOD;
    }

    // Le problème demande des arrangements avec au moins une tortue,
    // donc nous soustrayons 1 (pour l'arrangement où aucune tortue n'est placée).
    std::cout << (total_solutions - 1 + MOD) % MOD << '\n'; 

    return 0;
}

Implémentation en Python

MOD = 10**9 + 7

def resoudre_ferme_tortues():
    lignes, colonnes = map(int, sys.stdin.readline().split()) # Utiliser sys.stdin.readline pour les E/S rapides

    valeurs_grille = []
    for _ in range(lignes):
        valeurs_grille.append(list(map(int, sys.stdin.readline().split())))

    # `masque_lignes_restreintes[r]` stocke un masque binaire pour la ligne `r`
    # où un '1' au bit `j` signifie que la cellule `(r, j)` est restreinte (valeur 0 dans l'entrée).
    masque_lignes_restreintes = [0] * (lignes + 1)
    for idx_ligne in range(lignes):
        masque_actuel_ligne = 0
        for idx_col in range(colonnes):
            if valeurs_grille[idx_ligne][idx_col] == 0:
                masque_actuel_ligne |= (1 << idx_col)
        masque_lignes_restreintes[idx_ligne + 1] = masque_actuel_ligne # 1-indexé pour la commodité

    # `configs_horizontales_possibles` stocke tous les masques binaires représentant des placements horizontaux valides
    # (pas deux tortues adjacentes dans une ligne).
    configs_horizontales_possibles = []
    for masque_valeur in range(1 << colonnes):
        # Un masque est invalide si `(masque_valeur << 1)` ET `masque_valeur` est non-zéro,
        # signifiant qu'il y a des '1' consécutifs.
        if not ((masque_valeur << 1) & masque_valeur):
            configs_horizontales_possibles.append(masque_valeur)

    nombre_configs = len(configs_horizontales_possibles)
    
    # `table_dp[r][idx_config]` = nombre de façons de placer des tortues jusqu'à la ligne `r`
    # avec la ligne `r` ayant la configuration `configs_horizontales_possibles[idx_config]`.
    table_dp = [[0] * nombre_configs for _ in range(lignes + 1)]

    # Cas de base : Ligne 0 (avant la première ligne réelle). Seule une configuration vide est possible.
    # Trouver l'indice du masque 0 dans `configs_horizontales_possibles`.
    index_masque_vide = configs_horizontales_possibles.index(0)
    table_dp[0][index_masque_vide] = 1

    # Itérer à travers les lignes
    for r_courant in range(1, lignes + 1):
        # Itérer à travers toutes les configurations horizontales possibles pour la ligne courante
        for idx_config_courante in range(nombre_configs):
            masque_courant = configs_horizontales_possibles[idx_config_courante]

            # Vérifier si la configuration courante est valide compte tenu des cellules restreintes
            if (masque_courant & masque_lignes_restreintes[r_courant]):
                continue # Cette configuration place des tortues sur des cellules restreintes

            # Itérer à travers toutes les configurations horizontales possibles pour la ligne précédente
            for idx_config_precedente in range(nombre_configs):
                masque_precedent = configs_horizontales_possibles[idx_config_precedente]
                
                # Vérifier si la configuration précédente est valide compte tenu des cellules restreintes
                if (masque_precedent & masque_lignes_restreintes[r_courant - 1]):
                    continue # Cette configuration précédente a placé des tortues sur des cellules restreintes

                # Vérifier l'adjacence verticale : aucune tortue dans la ligne courante ne doit être directement au-dessus d'une tortue dans la ligne précédente.
                if not (masque_courant & masque_precedent):
                    table_dp[r_courant][idx_config_courante] = (table_dp[r_courant][idx_config_courante] + table_dp[r_courant - 1][idx_config_precedente]) % MOD

    # Sommer toutes les façons valides pour la dernière ligne
    reponse_finale = 0
    for idx_config in range(nombre_configs):
        reponse_finale = (reponse_finale + table_dp[lignes][idx_config]) % MOD
    
    # Soustraire 1 pour exclure le cas où aucune tortue n'est placée du tout (tableau vide).
    print((reponse_finale - 1 + MOD) % MOD)

if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(1 << 25) # Augmenter la limite de récursion pour les arbres profonds
    resoudre_ferme_tortues()

Problème 8 : Analyse de la Consommation Énergétique des Centres de Données

Le problème consiste à maintenir un tableau d'entiers et à effectuer deux types d'opérations sur des intervalles (ranges) : ajouter une valeur constante à tous les éléments dans un intervalle donné, et demander la somme des cubes des éléments dans un intervalle donné. Étant donné que les valeurs et le nombre d'opérations peuvent être importants (jusqu'à 10^5), une solution naive serait trop lente. Une approche utilisant un arbre de segments (Segment Tree) avec propagation paresseuse (lazy propagation) est nécessaire.

Connaissances Préalables

1. Construction et maintenance d'un arbre de segments.
2. Formules d'expansion binomiale pour les carrés et les cubes parfaits :
   • (a + b)^2 = a^2 + 2ab + b^2
   • (a + b)^3 = a^3 + 3a^2b + 3ab^2 + b^3
3. Gestion du modulo pour les nombres négatifs : (val % M + M) % M pour garantir un résultat non-négatif.

Approche de Résolution

Pour gérer les mises à jour et les requêtes par intervalle efficacement, nous utiliserons un arbre de segments. Puisque nous ajoutons une valeur x à un intervalle et devons interroger la somme des cubes, nous devrons maintenir non seulement la somme des éléments (puissance 1), mais aussi la somme de leurs carrés (puissance 2) et la somme de leurs cubes (puissance 3) dans chaque nœud de l'arbre.

Lorsqu'une valeur x est ajoutée à un intervalle [L, R], pour chaque élément a_i dans cet intervalle, il devient (a_i + x). Les nouvelles sommes pour cet intervalle sont :

• Somme des éléments : Sum(a_i + x) = Sum(a_i) + n * x
• Somme des carrés : Sum((a_i + x)^2) = Sum(a_i^2 + 2*a_i*x + x^2) = Sum(a_i^2) + 2*x*Sum(a_i) + n*x^2
• Somme des cubes : Sum((a_i + x)^3) = Sum(a_i^3 + 3*a_i^2*x + 3*a_i*x^2 + x^3) = Sum(a_i^3) + 3*x*Sum(a_i^2) + 3*x^2*Sum(a_i) + n*x^3

Où n est la longueur de l'interavlle. Ces formules montrent que les nouvelles sommes des puissances dépendent des sommes des puissances inférieures de l'intervalle. Ainsi, chaque nœud de l'arbre de segments doit stocker sum1 (somme des éléments), sum2 (somme des carrés) et sum3 (somme des cubes), ainsi qu'une balise paresseuse lazy_tag pour les mises à jour en attente.

Fonctionnement de la Propagation Paresseuse

La fonction push_down applique la lazy_tag d'un nœud parent à ses enfants et met à jour les sum1, sum2, sum3 des enfants en utilisant les formules dérivées ci-dessus. Il est crucial d'appliquer les mises à jour dans le bon ordre (par exemple, sum1 d'abord, puis sum2 qui utilise le nouveau sum1, puis sum3 qui utilise le nouveau sum1 et sum2). Après la propagation, la lazy_tag du parent est réinitialisée à zéro.

Implémentation en C++

#include <iostream>
#include <vector>
#include <numeric> // Pour std::iota (non utilisé directement ici, mais utile parfois)
#include <algorithm> // Pour std::max, std::min

// Utiliser long long pour les sommes afin d'éviter les débordements avant l'opération modulo.
#define LL long long
const LL MOD = 1e9 + 7;

// Structure d'un nœud d'arbre de segments
struct SegmentTreeNode {
    LL sum1; // Somme des éléments (Σ a_i)
    LL sum2; // Somme des carrés (Σ a_i^2)
    LL sum3; // Somme des cubes (Σ a_i^3)
    LL lazy_delta; // Valeur à ajouter à tous les éléments de ce segment
};

std::vector<SegmentTreeNode> arbre_segments;
std::vector<LL> valeurs_initiales; // Éléments du tableau original

// Fonction auxiliaire pour calculer le modulo correctement, assurant des résultats non-négatifs
LL modulo_securise(LL val) {
    return (val % MOD + MOD) % MOD;
}

// Combine les résultats des enfants gauche et droit dans le parent
void fusionner_enfants_vers_parent(int idx_noeud_parent) {
    arbre_segments[idx_noeud_parent].sum1 = modulo_securise(arbre_segments[idx_noeud_parent * 2].sum1 + arbre_segments[idx_noeud_parent * 2 + 1].sum1);
    arbre_segments[idx_noeud_parent].sum2 = modulo_securise(arbre_segments[idx_noeud_parent * 2].sum2 + arbre_segments[idx_noeud_parent * 2 + 1].sum2);
    arbre_segments[idx_noeud_parent].sum3 = modulo_securise(arbre_segments[idx_noeud_parent * 2].sum3 + arbre_segments[idx_noeud_parent * 2 + 1].sum3);
}

// Applique la balise paresseuse aux enfants et efface celle du parent
// idx_noeud_parent: index du nœud parent
// longueur_segment: longueur du segment couvert par idx_noeud_parent
void propager_balise_paresseuse(int idx_noeud_parent, int longueur_segment) {
    LL val_a_ajouter = arbre_segments[idx_noeud_parent].lazy_delta;
    if (val_a_ajouter == 0) return; // Pas de balise à propager

    int idx_enfant_gauche = idx_noeud_parent * 2;
    int idx_enfant_droit = idx_noeud_parent * 2 + 1;
    int len_gauche = longueur_segment / 2;
    int len_droit = longueur_segment - len_gauche; // Plus robuste pour les longueurs impaires

    // Appliquer la balise à l'enfant gauche
    // Nouvelle sum1: sum1_old + len * val
    arbre_segments[idx_enfant_gauche].sum1 = modulo_securise(arbre_segments[idx_enfant_gauche].sum1 + len_gauche * val_a_ajouter);
    // Nouvelle sum2: sum2_old + 2*val*sum1_old + len*val^2
    arbre_segments[idx_enfant_gauche].sum2 = modulo_securise(arbre_segments[idx_enfant_gauche].sum2 + 2 * val_a_ajouter % MOD * arbre_segments[idx_enfant_gauche].sum1 % MOD + len_gauche * val_a_ajouter % MOD * val_a_ajouter % MOD);
    // Nouvelle sum3: sum3_old + 3*val*sum2_old + 3*val^2*sum1_old + len*val^3
    arbre_segments[idx_enfant_gauche].sum3 = modulo_securise(arbre_segments[idx_enfant_gauche].sum3 + 3 * val_a_ajouter % MOD * arbre_segments[idx_enfant_gauche].sum2 % MOD + 3 * val_a_ajouter % MOD * val_a_ajouter % MOD * arbre_segments[idx_enfant_gauche].sum1 % MOD + len_gauche * val_a_ajouter % MOD * val_a_ajouter % MOD * val_a_ajouter % MOD);
    arbre_segments[idx_enfant_gauche].lazy_delta = modulo_securise(arbre_segments[idx_enfant_gauche].lazy_delta + val_a_ajouter);

    // Appliquer la balise à l'enfant droit (même logique)
    arbre_segments[idx_enfant_droit].sum1 = modulo_securise(arbre_segments[idx_enfant_droit].sum1 + len_droit * val_a_ajouter);
    arbre_segments[idx_enfant_droit].sum2 = modulo_securise(arbre_segments[idx_enfant_droit].sum2 + 2 * val_a_ajouter % MOD * arbre_segments[idx_enfant_droit].sum1 % MOD + len_droit * val_a_ajouter % MOD * val_a_ajouter % MOD);
    arbre_segments[idx_enfant_droit].sum3 = modulo_securise(arbre_segments[idx_enfant_droit].sum3 + 3 * val_a_ajouter % MOD * arbre_segments[idx_enfant_droit].sum2 % MOD + 3 * val_a_ajouter % MOD * val_a_ajouter % MOD * arbre_segments[idx_enfant_droit].sum1 % MOD + len_droit * val_a_ajouter % MOD * val_a_ajouter % MOD * val_a_ajouter % MOD);
    arbre_segments[idx_enfant_droit].lazy_delta = modulo_securise(arbre_segments[idx_enfant_droit].lazy_delta + val_a_ajouter);

    arbre_segments[idx_noeud_parent].lazy_delta = 0; // Effacer la balise après la propagation
}

// Construit l'arbre de segments
// debut_intervalle, fin_intervalle: intervalle couvert par le nœud actuel
// idx_noeud: index du nœud actuel dans le tableau arbre_segments
void construire_arbre(int debut_intervalle, int fin_intervalle, int idx_noeud) {
    if (debut_intervalle == fin_intervalle) { // Nœud feuille
        LL val = valeurs_initiales[debut_intervalle - 1]; // Ajuster pour l'indexation 0 du tableau initial
        arbre_segments[idx_noeud].sum1 = modulo_securise(val);
        arbre_segments[idx_noeud].sum2 = modulo_securise(val * val);
        arbre_segments[idx_noeud].sum3 = modulo_securise(val * val % MOD * val);
        return;
    }

    int milieu = (debut_intervalle + fin_intervalle) / 2;
    construire_arbre(debut_intervalle, milieu, idx_noeud * 2);
    construire_arbre(milieu + 1, fin_intervalle, idx_noeud * 2 + 1);
    fusionner_enfants_vers_parent(idx_noeud);
}

// Met à jour un intervalle [cible_debut, cible_fin] en ajoutant `valeur_ajout`
// debut_intervalle, fin_intervalle: intervalle couvert par le nœud actuel
// cible_debut, cible_fin: intervalle à mettre à jour
void mettre_a_jour_intervalle(int debut_intervalle, int fin_intervalle, LL valeur_ajout, int cible_debut, int cible_fin, int idx_noeud) {
    if (cible_debut <= debut_intervalle && fin_intervalle <= cible_fin) { // Le nœud actuel est entièrement dans l'intervalle cible
        LL longueur_courante = fin_intervalle - debut_intervalle + 1;
        arbre_segments[idx_noeud].sum3 = modulo_securise(arbre_segments[idx_noeud].sum3 + 3 * valeur_ajout % MOD * arbre_segments[idx_noeud].sum2 % MOD + 3 * valeur_ajout % MOD * valeur_ajout % MOD * arbre_segments[idx_noeud].sum1 % MOD + longueur_courante * valeur_ajout % MOD * valeur_ajout % MOD * valeur_ajout % MOD);
        arbre_segments[idx_noeud].sum2 = modulo_securise(arbre_segments[idx_noeud].sum2 + 2 * valeur_ajout % MOD * arbre_segments[idx_noeud].sum1 % MOD + longueur_courante * valeur_ajout % MOD * valeur_ajout % MOD);
        arbre_segments[idx_noeud].sum1 = modulo_securise(arbre_segments[idx_noeud].sum1 + longueur_courante * valeur_ajout);
        arbre_segments[idx_noeud].lazy_delta = modulo_securise(arbre_segments[idx_noeud].lazy_delta + valeur_ajout);
        return;
    }

    // Chevauchement partiel ou pas de chevauchement, propager la balise paresseuse d'abord
    propager_balise_paresseuse(idx_noeud, fin_intervalle - debut_intervalle + 1);

    int milieu = (debut_intervalle + fin_intervalle) / 2;
    if (cible_debut <= milieu) {
        mettre_a_jour_intervalle(debut_intervalle, milieu, valeur_ajout, cible_debut, cible_fin, idx_noeud * 2);
    }
    if (cible_fin > milieu) {
        mettre_a_jour_intervalle(milieu + 1, fin_intervalle, valeur_ajout, cible_debut, cible_fin, idx_noeud * 2 + 1);
    }
    fusionner_enfants_vers_parent(idx_noeud); // Mettre à jour les sommes du parent après la mise à jour des enfants
}

// Interroge la somme des cubes pour un intervalle cible [cible_debut, cible_fin]
LL interroger_somme_cubes(int debut_intervalle, int fin_intervalle, int cible_debut, int cible_fin, int idx_noeud) {
    if (cible_debut <= debut_intervalle && fin_intervalle <= cible_fin) { // Le nœud actuel est entièrement dans l'intervalle cible
        return arbre_segments[idx_noeud].sum3;
    }

    // Chevauchement partiel ou pas de chevauchement, propager la balise paresseuse d'abord
    propager_balise_paresseuse(idx_noeud, fin_intervalle - debut_intervalle + 1);

    LL somme_cubes_totale = 0;
    int milieu = (debut_intervalle + fin_intervalle) / 2;
    if (cible_debut <= milieu) {
        somme_cubes_totale = modulo_securise(somme_cubes_totale + interroger_somme_cubes(debut_intervalle, milieu, cible_debut, cible_fin, idx_noeud * 2));
    }
    if (cible_fin > milieu) {
        somme_cubes_totale = modulo_securise(somme_cubes_totale + interroger_somme_cubes(milieu + 1, fin_intervalle, cible_debut, cible_fin, idx_noeud * 2 + 1));
    }
    return somme_cubes_totale;
}

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

    int n_elements, m_requetes;
    std::cin >> n_elements >> m_requetes;

    valeurs_initiales.resize(n_elements);
    for (int i = 0; i < n_elements; ++i) {
        std::cin >> valeurs_initiales[i];
    }

    arbre_segments.resize(4 * n_elements); // La taille du tableau de l'arbre de segments est typiquement 4*N
    construire_arbre(1, n_elements, 1); // Construire pour l'intervalle 1 à N, la racine est à l'index 1

    for (int q = 0; q < m_requetes; ++q) {
        int type_operation;
        std::cin >> type_operation;
        if (type_operation == 1) { // Opération de mise à jour
            int debut_q, fin_q;
            LL val_a_ajouter;
            std::cin >> debut_q >> fin_q >> val_a_ajouter;
            mettre_a_jour_intervalle(1, n_elements, val_a_ajouter, debut_q, fin_q, 1);
        } else { // Opération de requête
            int debut_q, fin_q;
            std::cin >> debut_q >> fin_q;
            std::cout << interroger_somme_cubes(1, n_elements, debut_q, fin_q, 1) << '\n';
        }
    }

    return 0;
}

Implémentation en Python

import sys

MOD = 10**9 + 7

# Classe pour un nœud de l'arbre de segments
class NoeudSegment:
    def __init__(self):
        self.somme_puissance1 = 0 # Somme des éléments (a_i)
        self.somme_puissance2 = 0 # Somme des carrés (a_i^2)
        self.somme_puissance3 = 0 # Somme des cubes (a_i^3)
        self.delta_paresseux = 0 # Valeur à ajouter à tous les éléments de ce segment

# Variables globales pour l'arbre et les données
noeuds_arbre_segments = []
donnees_initiales_tableau = []
N_elements = 0

# Assure que les résultats sont dans [0, MOD-1]
def modulo_securise(val):
    return (val % MOD + MOD) % MOD

# Fusionne les données des enfants pour mettre à jour le parent
def fusionner_enfants_vers_parent(idx_parent):
    idx_enfant_gauche = idx_parent * 2
    idx_enfant_droit = idx_parent * 2 + 1
    
    noeuds_arbre_segments[idx_parent].somme_puissance1 = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].somme_puissance1 + noeuds_arbre_segments[idx_enfant_droit].somme_puissance1)
    noeuds_arbre_segments[idx_parent].somme_puissance2 = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].somme_puissance2 + noeuds_arbre_segments[idx_enfant_droit].somme_puissance2)
    noeuds_arbre_segments[idx_parent].somme_puissance3 = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].somme_puissance3 + noeuds_arbre_segments[idx_enfant_droit].somme_puissance3)

# Propage le delta_paresseux du nœud parent à ses enfants
def propager_delta_paresseux(idx_parent, longueur_segment):
    val_delta = noeuds_arbre_segments[idx_parent].delta_paresseux
    if val_delta == 0:
        return

    idx_enfant_gauche = idx_parent * 2
    idx_enfant_droit = idx_parent * 2 + 1
    longueur_gauche = longueur_segment // 2
    longueur_droite = longueur_segment - longueur_gauche

    # Appliquer le delta à l'enfant gauche
    # Somme1: (a+b) = a + b
    noeuds_arbre_segments[idx_enfant_gauche].somme_puissance1 = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].somme_puissance1 + longueur_gauche * val_delta)
    # Somme2: (a+b)^2 = a^2 + 2ab + b^2
    noeuds_arbre_segments[idx_enfant_gauche].somme_puissance2 = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].somme_puissance2 + 2 * val_delta % MOD * noeuds_arbre_segments[idx_enfant_gauche].somme_puissance1 % MOD + longueur_gauche * val_delta % MOD * val_delta % MOD)
    # Somme3: (a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3
    noeuds_arbre_segments[idx_enfant_gauche].somme_puissance3 = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].somme_puissance3 + 3 * val_delta % MOD * noeuds_arbre_segments[idx_enfant_gauche].somme_puissance2 % MOD + 3 * val_delta % MOD * val_delta % MOD * noeuds_arbre_segments[idx_enfant_gauche].somme_puissance1 % MOD + longueur_gauche * val_delta % MOD * val_delta % MOD * val_delta % MOD)
    noeuds_arbre_segments[idx_enfant_gauche].delta_paresseux = modulo_securise(noeuds_arbre_segments[idx_enfant_gauche].delta_paresseux + val_delta)

    # Appliquer le delta à l'enfant droit
    noeuds_arbre_segments[idx_enfant_droit].somme_puissance1 = modulo_securise(noeuds_arbre_segments[idx_enfant_droit].somme_puissance1 + longueur_droite * val_delta)
    noeuds_arbre_segments[idx_enfant_droit].somme_puissance2 = modulo_securise(noeuds_arbre_segments[idx_enfant_droit].somme_puissance2 + 2 * val_delta % MOD * noeuds_arbre_segments[idx_enfant_droit].somme_puissance1 % MOD + longueur_droite * val_delta % MOD * val_delta % MOD)
    noeuds_arbre_segments[idx_enfant_droit].somme_puissance3 = modulo_securise(noeuds_arbre_segments[idx_enfant_droit].somme_puissance3 + 3 * val_delta % MOD * noeuds_arbre_segments[idx_enfant_droit].somme_puissance2 % MOD + 3 * val_delta % MOD * val_delta % MOD * noeuds_arbre_segments[idx_enfant_droit].somme_puissance1 % MOD + longueur_droite * val_delta % MOD * val_delta % MOD * val_delta % MOD)
    noeuds_arbre_segments[idx_enfant_droit].delta_paresseux = modulo_securise(noeuds_arbre_segments[idx_enfant_droit].delta_paresseux + val_delta)

    noeuds_arbre_segments[idx_parent].delta_paresseux = 0 # Effacer le delta_paresseux du parent

# Construit l'arbre de segments de manière récursive
def construire_arbre_segments(debut_range_actuel, fin_range_actuel, idx_noeud_arbre):
    if debut_range_actuel == fin_range_actuel: # Nœud feuille
        val = donnees_initiales_tableau[debut_range_actuel - 1] # Ajuster pour l'indexation 0 du tableau d'entrée
        noeuds_arbre_segments[idx_noeud_arbre].somme_puissance1 = modulo_securise(val)
        noeuds_arbre_segments[idx_noeud_arbre].somme_puissance2 = modulo_securise(val * val)
        noeuds_arbre_segments[idx_noeud_arbre].somme_puissance3 = modulo_securise(val * val * val)
        return

    milieu = (debut_range_actuel + fin_range_actuel) // 2
    construire_arbre_segments(debut_range_actuel, milieu, idx_noeud_arbre * 2)
    construire_arbre_segments(milieu + 1, fin_range_actuel, idx_noeud_arbre * 2 + 1)
    fusionner_enfants_vers_parent(idx_noeud_arbre)

# Met à jour un intervalle donné [debut_requete, fin_requete] en ajoutant `valeur_a_ajouter`
def mettre_a_jour_range_add(debut_range_actuel, fin_range_actuel, valeur_a_ajouter, debut_requete, fin_requete, idx_noeud_arbre):
    if debut_requete <= debut_range_actuel and fin_range_actuel <= fin_requete: # Le nœud actuel est entièrement dans l'intervalle de requête
        longueur_courante = fin_range_actuel - debut_range_actuel + 1
        noeuds_arbre_segments[idx_noeud_arbre].somme_puissance3 = modulo_securise(noeuds_arbre_segments[idx_noeud_arbre].somme_puissance3 + 3 * valeur_a_ajouter % MOD * noeuds_arbre_segments[idx_noeud_arbre].somme_puissance2 % MOD + 3 * valeur_a_ajouter % MOD * valeur_a_ajouter % MOD * noeuds_arbre_segments[idx_noeud_arbre].somme_puissance1 % MOD + longueur_courante * valeur_a_ajouter % MOD * valeur_a_ajouter % MOD * valeur_a_ajouter % MOD)
        noeuds_arbre_segments[idx_noeud_arbre].somme_puissance2 = modulo_securise(noeuds_arbre_segments[idx_noeud_arbre].somme_puissance2 + 2 * valeur_a_ajouter % MOD * noeuds_arbre_segments[idx_noeud_arbre].somme_puissance1 % MOD + longueur_courante * valeur_a_ajouter % MOD * valeur_a_ajouter % MOD)
        noeuds_arbre_segments[idx_noeud_arbre].somme_puissance1 = modulo_securise(noeuds_arbre_segments[idx_noeud_arbre].somme_puissance1 + longueur_courante * valeur_a_ajouter)
        noeuds_arbre_segments[idx_noeud_arbre].delta_paresseux = modulo_securise(noeuds_arbre_segments[idx_noeud_arbre].delta_paresseux + valeur_a_ajouter)
        return

    # Si chevauchement partiel, propager la balise paresseuse avant la récursion
    propager_delta_paresseux(idx_noeud_arbre, fin_range_actuel - debut_range_actuel + 1)

    milieu = (debut_range_actuel + fin_range_actuel) // 2
    if debut_requete <= milieu:
        mettre_a_jour_range_add(debut_range_actuel, milieu, valeur_a_ajouter, debut_requete, fin_requete, idx_noeud_arbre * 2)
    if fin_requete > milieu:
        mettre_a_jour_range_add(milieu + 1, fin_range_actuel, valeur_a_ajouter, debut_requete, fin_requete, idx_noeud_arbre * 2 + 1)
    fusionner_enfants_vers_parent(idx_noeud_arbre)

# Interroge la somme des cubes pour un intervalle cible [debut_requete, fin_requete]
def interroger_somme_cubes(debut_range_actuel, fin_range_actuel, debut_requete, fin_requete, idx_noeud_arbre):
    if debut_requete <= debut_range_actuel and fin_range_actuel <= fin_requete: # Le nœud actuel est entièrement dans l'intervalle de requête
        return noeuds_arbre_segments[idx_noeud_arbre].somme_puissance3

    propager_delta_paresseux(idx_noeud_arbre, fin_range_actuel - debut_range_actuel + 1)

    somme_cubes_totale = 0
    milieu = (debut_range_actuel + fin_range_actuel) // 2
    if debut_requete <= milieu:
        somme_cubes_totale = modulo_securise(somme_cubes_totale + interroger_somme_cubes(debut_range_actuel, milieu, debut_requete, fin_requete, idx_noeud_arbre * 2))
    if fin_requete > milieu:
        somme_cubes_totale = modulo_securise(somme_cubes_totale + interroger_somme_cubes(milieu + 1, fin_range_actuel, debut_requete, fin_requete, idx_noeud_arbre * 2 + 1))
    return somme_cubes_totale

def main_analyse_energie():
    global N_elements, donnees_initiales_tableau, noeuds_arbre_segments
    sys.setrecursionlimit(1 << 25) # Augmenter la limite de récursion pour les arbres profonds

    N_elements, M_requetes = map(int, sys.stdin.readline().split())
    donnees_initiales_tableau = list(map(int, sys.stdin.readline().split()))

    noeuds_arbre_segments = [NoeudSegment() for _ in range(4 * N_elements)]
    construire_arbre_segments(1, N_elements, 1) # Construire à partir d'un intervalle 1-indexé

    for _ in range(M_requetes):
        parties_requete = list(map(int, sys.stdin.readline().split()))
        type_requete = parties_requete[0]
        debut_q = parties_requete[1]
        fin_q = parties_requete[2]

        if type_requete == 1:
            valeur_ajout = parties_requete[3]
            mettre_a_jour_range_add(1, N_elements, valeur_ajout, debut_q, fin_q, 1)
        else:
            print(interroger_somme_cubes(1, N_elements, debut_q, fin_q, 1))

if __name__ == '__main__':
    main_analyse_energie()