3387 - Generating Alien DNA II 3387 - Genética Alienígena II 3387 - Generating Alien DNA II

Statistics Sub: 151 | AC: 22 | AC%: 14,57 | Score: 3,64
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Fidel I. Schaposnik
Added by fidels (2015-10-12)
Limits
Total Time: 5000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

There is a fundamental and unchanging characteristic shared by all life on Earth, from the tiniest microbe to whales, dinosaurs and human beings: DNA. This is the only known mechanism for the transmission and replication of genetic information, which poses one of the most important questions in modern biology: is DNA the only way to encode this information, or are there other possible mechanisms?

Professor Gould is a theoretical exobiologist whose research considers the possibility of the existence of extra-terrestrial life not having its genetic information encoded as DNA. Presently, he is developing a model based on the encoding of genetic information in the form of a chain of pseudo-nucleotides, which we will represent with the characters 'b', 'd', 'o', 'p', 'q', 'v', 'w' and 'x'. Each pseudo-nucleotide has a conjugate: 'o', 'v', 'w' and 'x' are each its own conjugate, whereas 'b' is the conjugate of 'd', 'p' is the conjugate of 'q', and conversely 'd' is the conjugate of 'b' and 'q' is the conjugate of 'p'.

In the model developed by professor Gould, an organism can suffer a mutation starting from a given position in its pseudo-nucleotide chain, resulting in the inversion and conjugation of the second part of said chain. Specifically, if the original pseudo-nucleotide chain is a[1] a[2] ... a[N] and the mutation occurs starting from position i, the resulting pseudo-nucleotide chain is a[1] a[2] ... a[i-1] ã[N] ã[N-1] ... ã[i+1] ã[i], where ã[k] represents the conjugate of the pseudo-nucleotide originally at position k.

As it evolves, an organism may suffer many mutations in this manner, the only restriction being that successive mutations should occur starting from positions which are ever closer to the end of the pseudo-nucleotide chain. For example, the chain "bdopqvwx" can suffer a mutation starting from position 3 resulting in the chain "bdxwvpqo", and after that another mutation starting from position  7 giving thus the chain "bdxwvpop", but these two mutations couldn't have occurred the other way around.

At this point in his research, professor Gould has two pseudo-nucleotide chains which are particularly interesting, and he would like to know the minimum number of mutations the first of them must suffer in order to become the second one. Can you help him?
Hay una característica fundamental e inalterable que comparte toda la vida en la Tierra, desde el más minúsculo microbio hasta las ballenas, los dinosaurios y los seres humanos: el ADN. Este es el único mecanismo conocido para la transmisión y replicación de información genética, lo cual plantea una de las preguntas más importantes que la biología moderna no ha podido responder hasta ahora: ¿es el ADN la única forma de codificar esta información, o hay otros mecanismos posibles?

El profesor Gould es un exobiólogo teórico, y se dedica a estudiar la posibilidad de que exista vida extraterrestre cuya información genética no se encuentre codificada en la forma de ADN. Actualmente, está desarrollando un modelo basado en la codificación de información genética en la forma de una cadena de pseudo-nucleótidos, que vamos a representar mediante los caracteres 'b', 'd', 'o', 'p', 'q', 'v', 'w' y 'x'. Cada pseudonucle ótido tiene un conjugado: 'o', 'v', 'w' y 'x' son cada uno su propio conjugado, mientras que 'b' es el conjugado de 'd', 'p' es el conjugado de 'q', y viceversa, 'd' es el conjugado de 'b' y 'q' es el conjugado de 'p'.

En el modelo del profesor Gould, un organismo puede sufrir una mutación a partir de cierta posición de su cadena de pseudo-nucleótidos, que resulta en la inversión y conjugación de la segunda parte de dicha cadena. Más específicamente, si la cadena de pseudonucle ótidos original es a[1] a[2] ... a[N], y la mutación ocurre a partir de la posición i, la cadena de pseudo-nucleótidos resultante es a[1] a[2] ... a[i-1] ã[N] ã[N-1] ... ã[i+1] ã[i], donde ã[k] representa el conjugado del pseudo-nucleótido originalmente en la posición k.

A lo largo de su evolución, un organismo dado puede sufrir varias mutaciones de este tipo, siendo la única restricción que las sucesivas mutaciones deben ocurrir a partir de posiciones cada vez más cercanas al final de la cadena de pseudo-nucleótidos. Por ejemplo, la cadena "bdopqvwx" puede sufrir una mutación a partir de la posición 3 resultando en la cadena "bdxwvpqo", y luego otra mutación a partir de la posición 7 para dar la cadena "bdxwvpop", pero estas dos mutaciones no podrían haber ocurrido en el orden inverso.

En este punto de su investigación, el profesor Gould tiene dos cadenas de pseudo-nucleótidos que son particularmente interesantes, y querría saber la mínima cantidad de mutaciones que debe sufrir la primera de ellas para transformarse en la otra. ¿Pueden ayudarlo?
There is a fundamental and unchanging characteristic shared by all life on Earth, from the tiniest microbe to whales, dinosaurs and human beings: DNA. This is the only known mechanism for the transmission and replication of genetic information, which poses one of the most important questions in modern biology: is DNA the only way to encode this information, or are there other possible mechanisms?

Professor Gould is a theoretical exobiologist whose research considers the possibility of the existence of extra-terrestrial life not having its genetic information encoded as DNA. Presently, he is developing a model based on the encoding of genetic information in the form of a chain of pseudo-nucleotides, which we will represent with the characters 'b', 'd', 'o', 'p', 'q', 'v', 'w' and 'x'. Each pseudo-nucleotide has a conjugate: 'o', 'v', 'w' and 'x' are each its own conjugate, whereas 'b' is the conjugate of 'd', 'p' is the conjugate of 'q', and conversely 'd' is the conjugate of 'b' and 'q' is the conjugate of 'p'.

In the model developed by professor Gould, an organism can suffer a mutation starting from a given position in its pseudo-nucleotide chain, resulting in the inversion and conjugation of the second part of said chain. Specifically, if the original pseudo-nucleotide chain is a[1] a[2] ... a[N] and the mutation occurs starting from position i, the resulting pseudo-nucleotide chain is a[1] a[2] ... a[i-1] ã[N] ã[N-1] ... ã[i+1] ã[i], where ã[k] represents the conjugate of the pseudo-nucleotide originally at position k.

As it evolves, an organism may suffer many mutations in this manner, the only restriction being that successive mutations should occur starting from positions which are ever closer to the end of the pseudo-nucleotide chain. For example, the chain "bdopqvwx" can suffer a mutation starting from position 3 resulting in the chain "bdxwvpqo", and after that another mutation starting from position  7 giving thus the chain "bdxwvpop", but these two mutations couldn't have occurred the other way around.

At this point in his research, professor Gould has two pseudo-nucleotide chains which are particularly interesting, and he would like to know the minimum number of mutations the first of them must suffer in order to become the second one. Can you help him?

Input specification

The first line contains an integer N, representing the length of both pseudo-nucleotide chains to be analyzed (1 <= N <= 1000). Each of the following two lines contains a string of N characters 'b''d''o''p''q''v''w' and 'x', representing a pseudo-nucleotide chain.
La primera línea contiene un entero N, que representa la longitud de las dos cadenas de pseudo-nucleótidos a ser analizadas (1 <= N <= 1000). Cada una de las siguientes dos líneas contiene una cadena de N caracteres 'b', 'd', 'o', 'p', 'q', 'v', 'w' y 'x', representando una cadena de pseudo-nucleótidos.
The first line contains an integer N, representing the length of both pseudo-nucleotide chains to be analyzed (1 <= N <= 1000). Each of the following two lines contains a string of N characters 'b''d''o''p''q''v''w' and 'x', representing a pseudo-nucleotide chain.

Output specification

Print one line containing an integer representing the minimum number of mutations the first chain in the input should suffer in order to become the second one. If this is not possible, print the number -1.
Imprimir en la salida una línea conteniendo un entero que representa la mínima cantidad de mutaciones que debe sufrir la primera cadena de la entrada para transformarse en la segunda. De no ser posible esto, imprimir el número -1.
The first line contains an integer N, representing the length of both pseudo-nucleotide chains to be analyzed (1 <= N <= 1000). Each of the following two lines contains a string of N characters 'b''d''o''p''q''v''w' and 'x', representing a pseudo-nucleotide chain.

Sample input

8
bdopqvwx
bdxwvpop

Sample output

2

Hint(s)

Sample input #2
5
bdopq
bdopq

Sample output #2
0

Sample input #3
10
ddbbddbbdd
bbddbbddbb

Sample output #3
1

Sample input #4
13
opoqpvbdxwwbp
vwpopvxxbdpqq

Sample output #4
-1
Sample input #2
5
bdopq
bdopq

Sample output #2
0

Sample input #3
10
ddbbddbbdd
bbddbbddbb

Sample output #3
1

Sample input #4
13
opoqpvbdxwwbp
vwpopvxxbdpqq

Sample output #4
-1
Sample input #2
5
bdopq
bdopq

Sample output #2
0

Sample input #3
10
ddbbddbbdd
bbddbbddbb

Sample output #3
1

Sample input #4
13
opoqpvbdxwwbp
vwpopvxxbdpqq

Sample output #4
-1

Recommendation

We have carefully selected several similar problems: 3378 | 3599 | 3147 | 1103 | 3134 | 2191