L'Atelier Monstre

Ce problème introduit un jeu où deux joueurs, S et T, évoluent sur deux graphes distincts. L'objectif est de trouver la valeur minimale d'une contrainte combinée permettant aux deux joueurs d'atteindre le nœud 1 de leur graphe respectif. Chaque joueur peut se déplacer d'un nœud actuel vers un nœud cible, à condition que tous les nœuds du chemin ...

Problème 1 : Approximation de Pi Ce problème demande d'afficher les N premières décimales de Pi, précédées de "3.". La solution consiste à utiliser une chaîne de caractères pré-définie contenant une approximation suffisamment longue de Pi et d'en extraire une sous-chaîne selon la précision requise. import math def afficher_pi_tronque ...

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