DIFFICULTE
LIMITE DE MEMOIRE
40000 ko
LIMITE DE TEMPS
200 ms
É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.
EXEMPLE(S) D'ENTREE/SORTIE
Exemple 1
en entrée ...
8 8 ATTGCAAA ATCTAAAT |
4 |
Exemple 2
en entrée ...
15 16 ATGCCGAAGGGGGCA CCGGGGGGAAGGGGGA |
7 |
