L'Atelier Monstre

La programmation dynamique sur les chiffres permet d'exploiter la structure des nombres pour compter ou vérifier des propriétés sur des plages de valeurs. L'idée principale est de traiter les nombres chiffre par chiffre, souvent en partent du chiffre de poids fort. Comptage des occurrences de chiffres dans un intervalle Problème : Étant donné d ...

A - Range Product L'objectif est de déterminer le signe du produit des entiers compris dans l'intervalle $[a, b]$. Nous pouvons diviser le problème en trois scénarios distincts : Si $a \le 0 \le b$, l'intervalle contient zéro, donc le produit est Zero. Si $a > 0$, tous les nombres sont positifs, le produit est donc Positive. Si $b < 0$, ...

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

Soit \(p\) un nombre premier. Nous notons \(v_p(n)\) la valuation \(p\)-adique de \(n\), et \((n)_p\) le quotient de \(n\) par la plus grande puissance de \(p\) qui le divise. Ainsi, on a \(n = p^{v_p(n)} (n)_p\). Théorème de Lucas Le théorème de Lucas permet de calculer un grand coefficient binomial modulo un petit nombre premier. Il évite les ...

Liens du Concours Les performances d'AtCoder varient l'après-midi, mais les soirées de compétition sont toujours exceptionnelles. A - Redondance Redondante Étant donné un entier \(N(2\leq N\leq 30)\), trouver un entier \(x(N\leq x\leq 10^{13})\) tel que pour tout entier \(y(2\leq y\leq N)\), on ait \(x\bmod y=1\). Idées & Solution Problème ...

La clé de ce problème réside dans la notion d'« inclusion stricte ». Initialement, j'ai négligé cet aspect et j'ai eu du mal à trouver une solution. Dans le cas d'une inclusion stricte, nous devons sélectionner 2k arêtes respectivement horizontalement et verticalement. Les directions horizontale et verticale étant indépendantes, nous pouvons ap ...

Le principe d'inclusion-exclusion (PIE) est une technique combinatoire fondamentale permettant de calculer le cardinal d'une union de plusieurs ensembles. En informatique, il est particulièrement efficace pour résoudre des problèmes de dénombrement où il est plus simple de compter le complémentaire d'un ensemble ou des intersections spécifiques ...

Comprendre les fonctions génératrices par un exemple classique Les fonctions génératrices sont un outil fondamental en combinatoire analytique. Pour illustrer leur mécanisme, considérons le problème suivant : trouver le nombre de solutions entières non négatives de l'équation x + 2y = 10. Du point de vue combinatoire, chaque variable peut prend ...

Introduction à l'outil de raisonnement local Lorsque vous êtes cofnronté à des problèmes algorithmiques complexes, des défis en combinatoire ou des preuves logiques nécessitant une réflexion approfondie, un assistant de raisonnement local peut s'avérer précieux. Cet outil repose sur l'architecture du modèle Cosmos-Reason1-7B, optimisé pour les ...

11.23 LG14362 [CSP-S2025] Route Un ajout important : pour un graphe donné, après avoir calculé son arbre couvrant minimum (MST), si l'on ajoute d'autres arêtes pour former un nouveau graphe, le MST du nouveau graphe n'utilisera jamais les arêtes non-arbres de l'ancien graphe. LG14394/LOJ2729 [JOISC 2016] Poupée gigogne Analyse Le problème sembl ...