L'Atelier Monstre

Gestion des Cycles de Trafic et Arbre de Segment Pour déterminer le temps minimal requis pour atteindre l'école depuis chaque intersection, le traitement doit s'effectuer en ordre inverse, du nœud final vers la source. L'état des feux de signalisation étant périodique, le temps d'arrivée à un point donné peut être réduit modulo $T$, où $T$ repr ...

Codage de Huffman et Optimisation Greedy Pour minimiser le coût total d'un arbre de codage, l'approche gloutonne de Huffman est optimale. En utilisant une file de priorité (tas binaire), nous extrayons répétitivement les deux poids les plus faibles pour construire l'arbre de bas en haut. import heapq def calculer_cout_huffman(): n = int(in ...

Prérequis : Propriété Distributive L'application de ces structures de données avancées nécessite que l'opération mathématique sous-jacente satisfasse la propriété distributive. Si l'opération n'est pas distributive, ces algorithmes ne peuvent pas être appliqués. Arbre de Segments (Segment Tree) Bien que l'arbre de Fenwick soit plus simple, l'ar ...

Problème 1 : Sommes de Sous-ensembles (Collection) L'objectif est de calculer le produit de toutes les sommes possibles de sous-ensembles, chacune élevée à la puissance de sa fréquence d'apparition. Le cœur du problème repose sur un sac à dos (knapsack) pour compter ces occurrences. Soit $f[j]$ le nombre de façons d'obtenir une somme $j$. En ra ...

Énoncé du problème On dispose d'une grille de dimensions n × m (avec n, m ≤ 10⁹). Initialement, k cellules sont enflammées. Le feu se propage selon la connectivité 8 (distance de Tchebychev), c'est-à-dire qu'après t unités de temps, toute cellule (x', y') telle que max(|x - x'|, |y - y'|) ≤ t est également enflammée. L'objectif est d'allumer un ...

Partitionnement de Séquence et Optimisation de Pente CDQ Énoncé du Problème Étant donné une séquence \(t\) de longueur \(N\), l'objectif est de la diviser en \(K\) sous-segments contigus. Si le \(i\)-ème sous-segment s'étend de l'indice \(l_i\) à \(r_i\), le coût total est défini par \(\sum_{i = 1} ^ K (t_{l_i} - t_{r_i}) ^ 2\). Le but est de m ...

Problème G: Théorie des jeux avec Rikka Énoncé du problème: Étant donné un graphe non oreinté à n sommets (n ≤ 17), attribuer une valeur à chaque sommet telle que la valeur de chaque sommet soit le mex des valeurs des sommets adjacents. Calculer le nombre total d'attribution valide. Solution: La contrainte sur n suggère une approche par program ...