L'Atelier Monstre

Ce document présente les solutions pour les problèmes A, B et C du Round Éducatif Codeforces 174 (Classé pour la Division 2). A - Y avait-il un Tableau ? Analyse du Problème L'énoncé suggère qu'une solution est impossible s'il existe une sous-séquence spécifique dans un tableau dérivé. Le motif interdit semble être une combinaison de 1 et 0. Lo ...

La liste doublement chaînée (doubly linked list) est une structure de données linéaire où chaque élément, appelé nœud, contient des références vers son successeur et son prédécesseur. Contrairement à une liste simple, la variante la plus robuste et la plus utilisée en pratique est la liste doublement chaînée circulaire avec nœud sentinelle. 1. ...

Problème A : Shizuku Hoshikawa et les Pattes de la Ferme C'est un problème classique de coqs et de lapins (ou poules et lapins). L'objectif est de compter le nombre de combinaisons possibles d'animaux (coqs et lapins) ayant un nombre total de pattes égal à n. Il faut noter que le nombre d'animaux peut être nul. La solution consiste à itérer sur ...

Présentation du Problème Nous sommes confrontés à un ensemble de $N$ lampes, initialement toutes allumées. Nous disposons de quatre boutons distincts qui modifient l'état de ces lampes. Chaque appui sur un bouton inverse l'état (allumée devient éteinte, et vice-versa) des lampes affectées. Les actions des boutons sont les suivantes : Bouton 1 ...

Recherche de valeurs extrêmes via des pointeurs L'utilisation des pointeurs permet à une fonnction de modifier plusieurs variables dans la portée de l'appelant ou de renvoyer l'adresse d'un élément spécifique. Voici une implémentation permettant d'extraire les valeurs minimale et maximale d'un ensemble d'entiers. #include <stdio.h> #defi ...

Nous abordons trois problèmes LeetCode classiques impliquant des arbres binaires, en utilisant des techniques de parcousr en C++. Ces problèmes couvrent la vérification d'équilibre, la génération de tous les chemins et le calcul de la somme des feuilles gauches. Problème 110 : Arbre binaire équilibré Pour déterminer si un arbre binaire est équi ...

L'objectif est de compter le nombre d'inversions dans une séquence d'entiers. Une inversion est une paire d'indices (i, j) telle que i < j et arr[i] > arr[j]. Nous allons explorer deux approches principales, toutes deux offrant une complexité temporelle de O(log n) après prétraitement. Approche par Division et Fusion (Merge Sort) Cette mé ...

Introduction à la résolution par BFS La recherche en largeur (BFS) est une technique efficace pour déterminer le chemin le plus court dans un environnement structuré en grille, où chaque déplacement a un coût uniforme. Cet article explique comment appliquer BFS pour naviguer sur une carte carrée, en évitant les obstacles, afin de trouver la dis ...

Le problème consiste à multiplier deux nombres représentés par des chaînes de caractères et à retourner le résultat sous forme de chaîne. Les nombres peuvent être arbitrairement grands et sont non négatifs. Une première idée serait de convertir chaque chaîne en entier, d'effectuer la multiplication, puis de reconvertir le résultat en chaîne. Ce ...

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