L'Atelier Monstre

Problème A : Manipulation de Chaînes et Palindromes Énoncé : Étant donné une chaîne de caractères S, nous avons également son inverse S_rev. Nous effectuons k opérations. À chaque étape, nous pouvons ajouter l'inverse de la chaîne courante soit à la fin, soit au début. La question est de déterminer le nombre maximal de séquences distinctes que ...

Un problème classique de théorie des graphes consiste à déterminer le chemin optimal entre deux points, en minimisant la distance totale et, à distance égale, le coût associé. Ce problème est modélisé à l'aide d'un graphe pondéré non orienté où les arêtes représentent des routes avec une longueur et un tarif péage. Description du problème Étant ...

A. [ARC210D] Jeu d'ensemble indépendant (5) À chaque tour, un sommet u est supprimé, et A supprime également le voisinage de u. Si n est impair, A ne peut pas supprimer le voisinage, sinon l'ensemble de sommets devient vide. En explorant manuellement, on constate que dans ce cas, chaque composante connexe doit avoir ≤ 2 sommets. Si n est pair, ...

Énoncé du problème Une agence de voyage dans la ville d'Adelton sur l'île de Zanzibar souhaite proposer des circuits touristiques. Pour maximiser ses profits, elle a décidé de trouver le plus court circuit qui commence et se termine au même endroit. Écrivez un programme qui détermine un tel circuit. La ville comprend N intersections numérotées ...

Ce problème aborde l'optimisation des profits dans le commerce de puces quantiques à travers un réseau de bases de recherche, en utilisant les algorithmes de Tarjan pour la détection des composantes fortement connexes (CFC) et le tri topologique sur le graphe condensé. Description du Problème Le pays D dispose de n bases de recherche et m canau ...

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

Problème T1 : Arbre couvrant minimum avec poids conditionnel Énoncé : Soit un graphe G. On doit trouver un arbre couvrant minimum dont le poids est défini ainsi : si le poids maximal des arêtes w_max ≤ k, alors le poids est k - w_max ; sinon, le poids est la somme des |w_i - k| pour toutes les arêtes avec w_i ≥ k. Analyse : Les cas spéciaux où ...