L'Atelier Monstre

Problème T1 : F Raisonnement Comme les tableaux a et b sont liés par une relation biunivoque, le nombre de candidats possibles est au plus n. Pour chaque valeur candidate, on vérifie en un seul parcours si elle réalise une correspondance parfaite entre a et b. On peut utiliser une tible de hachage, un map ou un multiset pour stocker les élément ...

Jour 1 - Problème 1 : Le Carré Magique Fantastique Ce problème est une simulation directe de la construction d'un carré magique d'ordre impair. L'objectif est de remplir une matrice de taille $N \times N$ en suivant des règles de positionnement relatives au nombre précédemment placé. #include <iostream> #include <vector> using name ...

Considérons un problème classique de programmation dynamique (DP) dont la transition suit la forme suivante : \[f(i) = \min_{i-k \le j < i} \{f(j) + \max(a_{j+1}, \dots, a_i)\}\] L'objectif est d'optimiser cette transition pour passer d'une complexité naïve de \(O(n \cdot k)\) à une complexité linéaire ou quasi-linéaire. Approche en \(O(n \l ...