L'Atelier Monstre

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

A. Validation d'une chaîne « red » L'objectif est de vérifier si une chaîne de caractères donnée se compose exclusivement des lettres 'r', 'e' et 'd'. Une approche par énumération directe de chaque caractère suffit. #include <iostream> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); ci ...

Introduction aux Ensembles Disjoints La structure de données Union-Find (ou ensembles disjoints) est un type abstrait de données arborescent conçu pour gérer efficacement une collection de partitions. Elle prend en charge deux opérations fondamentales de manière optimale : Union : Fusionner deux ensembles distincts en un seul. Find : Détermine ...