L'Atelier Monstre

Problème Étant donné n périodes mensuelles et m contraintes de la forme (début, fin, somme) indiquant le revenu total entre le mois début et le mois fin, déterminer si un ensemble de valeurs de revenus mensuels peut exister sans contradictions. Approche par Système de Contraintes de Différences Soit prefix[i] le revenu cumulé jusqu'au mois i (i ...

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

Introduction Le plus proche ancêtre commun (PPAC), noté lca(a, b), désigne le nœud le plus profond qui est ancêtre à la fois de a et b dans un arbre enraciné. Plusieurs algorithmes permettent de résoudre ce problème, chacun offrant un compromis différent entre le prétraitement, la complexité par requête et le mode de fonctionnement (en ligne ou ...

Problème A Énoncé : On vous donne deux entiers \(n\) et \(k\). En une opération, vous pouvez soustraire n'importe quelle puissance de \(k\) (c'est-à-dire \(k^x\) pour \(x \ge 0\)) de \(n\). Trouvez le nombre minimum d'opérations pour réduire \(n\) à \(0\). Analyse : La solution optimale consiste à représenter \(n\) en base \(k\). Le nombre mini ...

Problème 1 : Jeu de Nombres et Programmation Dynamique Ce problème modélise un jeu séquentiel impliquant N entités disposées en cercle. Chaque entité annonce un entier dans l'intervalle [x+1, x+K], où x est le nombre précédent, sans dépasser une limite maximale M. L'entité qui annonce M perd. L'objectif est de déterminer, pour chaque position d ...

Modélisation et analyse mathématique Le problème consiste à déplacer un élément unique (la valeur 1) dans un tableau de taille n, initialement situé à l'index p. À chaque étape, il est possible d'inverser un sous-tableau contigu de taille k. Certains indices sont interdits (tableau banned) et ne peuvent jamais contenir la valeur 1. L'objectif e ...

Problème C : Mangeur de bonbons L'approche fondamentale consiste à trier les valeurs et, pour chaque i, sélectionner les i plus petites valeurs en plaçant les plus grandes en premier afin de réduire la pénalité au minimum. Si l'on note dp[i] la pénalité minimale obtenue avec les i premiers éléments, alors dp[i + m] = dp[i] + somme[1 : i+m], ce ...

La fraude téléphonique est un problème persistant. Pour la combattre, un suspect est identifié s'il effectue plus de K appels courts à des personnes différentes quotidiennement, avec au plus 20% de rappels. Un appel court est défini par une durée totale de 5 minutes ou moins. Lorsque deux suspects s'appellent mutuellement, ils sont potentiellem ...

L'ancêtre commun le plus proche (LCA) de deux nœuds u et v dans un arbre enraciné est le nœud le plus profond qui est un ancêtre à la fois de u et de v. Par exemple, dans l'arbre ci-dessous, LCA(3,7) = 1 et LCA(3,4) = 2. Il existe plusieurs méthodes pour calculer le LCA, classifiées en algorithmes hors ligne (toutes les requêtes sont connues à ...

L'Union-Find est une structure de données efficace pour gérer des ensembles disjoints, souvent utilisée pour modéliser des relatoins entre éléments. Dans cet article, nous explorons son application à deux problèmes classiques : la détermination du nombre maximum de héros dans un scénario de vérité et de mensonge, et la vérification de relations ...