L'Atelier Monstre

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 ...