L'Atelier Monstre

Problème 1 : Superficie maximale d'une île Énoncé : Étant donné une grille composée de 1 (terre) et 0 (eau), calculer la superficie maximale des îles. La superficie est le nombre total de cellules terrestres connectées horizontalement ou verticalement. Exemple d'entrée : 4 5 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 Sortei attendue : 4 Approche ...

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

Implémentation d'une calculatrice basique prenant en charge les quatre opérations arithmétiques à partir d'une entrée formatée. #include <stdio.h> int main(void) { int x, y, res; char op; scanf("%d%c%d", &x, &op, &y); switch(op) { case '+': res = x + y; break; case '-': res = x - y; b ...

Problème 1 : Emplacement optimal de l'hôpital Description du problème Considérons un arbre binaire, comme illustré ci-dessous : Les valeurs dans les nœuds représentent la population des résidents, et les numéros à côté sont les identifiants des nœuds. L'objectif est de construire un hôpital sur un nœud de sorte que la somme des distances parcou ...

Le problème des régions encerclées consiste à modifier une matrice bidimensionnelle composée des caractères 'X' et 'O'. L'objectif est d'identifier tous les groupes de 'O' qui sont complètement entourés par des 'X' et de les remplacer par des 'X'. Une règle fondamentale s'aplique : les 'O' situés sur les bords de la matrice, ou connectés à un ' ...

L'algorithme du plus proche ancêtre commun (LCA) dans un arbre repose sur des techniques de prétraitement pour optimiser les requêtes. Trois types de relations d'ascendance existent entre deux nœuds : a est ancêtre de b, b est ancêtre de a, ou aucun lien direct. Pour un ensemble de nœuds, le LCA peut être déterminé en identifient les points ave ...

Introduction au tri topologique : Deux approches principales existent : l'algorithme de Kahn (basé sur BFS) et la méthode DFS. Leur objectif est d'ordonner les nœuds dans un graphe dirigé acyclique (DAG), offrant souvent plusieurs solutions valides. Ces algorithmes identifient également la présence de cycles. Principe de l'algorithme de Kahn (B ...

Problème classique de recherche combinatoire avec test de primalité. #include <iostream> using namespace std; int countPrimes(int val) { if (val < 2) return 0; for (int d = 2; d * d <= val; ++d) { if (val % d == 0) return 0; } return 1; } int totalComb = 0; void generateCombinations(int step, int lastIndex, int ...

Cet article présente une récapitulation technique des solutions pour les problèmes de l'AtCoder Beginner Contest 420, avec des explications et des exemples de code réécrits en C++. Problème A Un problème simple qui peut être résolu directement. La solution calcule la valeur modulo 12 après ajustement. #include <iostream> using namespace s ...

11.1 Recherche en profondeur (DFS) 11.1.1 Concepts de base Le DFS (Depth-First Search) est un algorithme récursif qui explore un chemin jusqu'au bout puis fait marche arrière. Gabarit de base void dfs(int etat) { // 1. Condition d'arrêt if (condition satisfaite) { traiter le résultat; return; } // 2. Élagage ...