Transformation – Qualification 2010

Level 4

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

Runtime constraints

Maximum memory usage
40000 kilobytes
Maximum execution time
200 milliseconds

Input/output samples

Sample input
8
8
ATTGCAAA
ATCTAAAT
Sample output
4
Sample input
15
16
ATGCCGAAGGGGGCA
CCGGGGGGAAGGGGGA
Sample output
7

Submit your solution

You have to register or log in to be able to submit your solution.