Prologin
2025
Énoncé¶
Une séquence d'ADN sera une suite finie constituée de lettres dans l'ensemble {A, T, G, C}. On vous donne en entrée deux séquences ADN de tailles N1 et N2. On souhaite calculer le nombre minimal de transformations pour passer de la première séquence à la deuxième. Les transformations possibles sont la modification, l'ajout ou la suppression d'une nucléotide. Les deux séquences sont très similaires; on garantit donc que l'on puisse passer de l'une à l'autre en moins de 100 transformations. Ecrivez un programme qui renvoie ce nombre demandé.
Contraintes¶
- 1 <= N1 <= 100000
- 1 <= N2 <= 100000
- Le nombre minimal de transformations pour passer d'une séquence à l'autre sera inférieur à 100.
Entrée¶
- Sur la première ligne, l'entier N1.
- Sur la deuxième ligne, l'entier N2.
- Sur la troisième ligne, la première séquence d'ADN, de taille N1
- Sur la quatrième ligne, la deuxième séquence d'ADN, de taille N2
Sortie¶
Un entier, indiquant le nombre minimal de transformations pour passer d'une séquence à l'autre.