L'Atelier Monstre

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

A. Génération de Chaînes Binaires (P6191) On commence par compter les solutions avec 0 ou 1 seul '1'. Ensuite, on modélise la séquence comme une succession de blocs "1 suivi de k zéros", terminée par un '1'. Pour i occurrences de '1', la longueur minimale est j = (k + 1)(i - 1) + 1. Si j dépasse n, on arrête. Sinon, on calcule le nomb ...

Problème : Soit \\(n\\) bombes, la \\(i\\)-ème ayant une position \\(pos\_i\\) et un état \\(state\_i\\) (0 pour non activé, 1 pour activé). On dispose de \\(m\\) opérations ; la \\(i\\)-ème opération inverse l'état de toutes les bombes situées entre \\(l\_i\\) et \\(r\_i\\). Déterminer s'il est possible de rendre toutes les bombes non activées ...