L'Atelier Monstre

Cet article explore diverses techniques algorithmiques à travers une sélection de problèmes de programmation compétitive, couvrant des domaines tels que la construction, la théorie des nombres, les structures de données avancées, la programmation dynamique et la théorie des graphes. CF1667C Couverture par Semi-Dames Tags: Construction, Mathémat ...

Algorithme de Prim pour l'Arbre Couvrnat Minimal (MST) L'algorithme de Prim est une méthode gloutonne permettant de trouver l'arbre couvrant minimal d'un graphe connexe pondéré. L'implémentation ci-dessous utilise une matrice d'adjacence pour représenter le graphe. #include <stdio.h> #include <stdlib.h> #define VAL_INF 65535 #defin ...

Définitoin du problème SAT SAT signifie Satisfaisabilité. Le problème k-SAT consiste à déterminer si une formule booléenne composée de m clauses, chacune contenant exactement k littéraux (variables ou leur négation), est satisfaisable. Pour k ≥ 3, il a été prouvé que k-SAT est NP-complet. Cependant, le cas particulier 2-SAT (où chaque clause co ...

Principe fondamental L'algorithme de Dijkstra calcule les plus courts chemins depuis un sommet source dans un graphe dont toutes les arêtes ont un poids non négatif. Sa complexité temporelle est de O(n²) dans sa version naïve et de O((n + m) log n) avec une optimisation par tas. L'idée centrale consiste à sélectionner itérativement le sommet no ...

L'algorithme du plus ancêtre commun (LCA) est une technique fondamentale pour résoudre des problèmes de distance ou de relations dans des arbres. Cet article présente plusieurs problèmes d'entraînement pour maîtriser le LCA, avec des explications et des implémentations en C++. Problème 1 : Distance entre maisons Lien : HDU 2586 Description : Un ...

Ce problème concerne un graphe non orienté comportant n sommets et m arêtes pondérées. De plus, il existe k arêtes supplémentaires connectant le sommet 1 à divers autres sommets. L'objectif est de déterminer le nombre maximal d'arêtes parmi ces k arêtes que l'on peut supprimer, tout en garantissant que les distances les plus courtes de tous les ...

Script de test automatisé Pour valider une solution, on peut utilisre un script qui génère des données, exécute une solution standard et la solution proposée, puis compare les sorties. Voici une version réécrite en C++ : #include<iostream> #include<cstdlib> #include<string> int main() { std::ios::sync_with_stdio(false); ...

Notes de Solutions APIO 2018-2024 Ces problèmes sont vraiment difficiles. (Mise à jour en cours...) Table des matières- Notes de Solutions APIO 2018-2024 [APIO2018] Ironman [APIO2018] Sélection de cercles [APIO2023] Cyberland [APIO2024] Septembre [APIO2018] Ironman D'abord, nous contractons les points doubles. Nous devons déterminer combien d ...

Problème du Mur Hamiltonien Énoncé du problème On vous donne une matrice $2\times m$ qui ne contient que les caractères B et W. Chaque colonne contient au moins un caractère B. La question est de savoir s'il existe un chemin qui satisfait les conditions suivantes : Les cellules adjacentes dans le chemin partagent un côté commun (pas seulement ...

Dans un réseau d'ordinateurs, certains sont connectés par des câbles de données bidirectionnels. Lorsqu'un ordinateur reçoit des données, il peut les transmettre à tous les ordinateurs directement ou indirectement connectés. L'objectif est de déterminer le nombre minimum d'rodinateurs auxquels il faut entrer les données initialement pour que to ...