Genoma Bovino


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal

El Granjero Juan tiene N vacas con manchas y N vacas sin manchas. El acaba de terminar un curso de genética bovina y está convencido que las manchas en sus vacas son causadas por mutaciones en una sola ubicación en el genoma bovino.

Con gran costo, el Granjero Juan obtiene los genomas de sus vacas. Cada genoma es una cadena de longitud M construida de cuatro caracteres A, C, G y T. Cuando él alinea los genomas de sus vacas, él obtiene una tabla como la mostrada a continuación para N=3:

Posiciones:         1 2 3 4 5 6 7 ... M
Vaca con manchas 1: A A T C C C A ... T
Vaca con manchas 2: G A T T G C A ... A
Vaca con manchas 3: G G T C G C A ... A

Vaca sin manchas 1: A C T C C C A ... G
Vaca sin manchas 2: A C T C G C A ... T
Vaca sin manchas 3: A C T T C C A ... T

Viendo cuidadosamente esta tabla, él sospecha que la posición 2 es una ubicación potencial para el genoma que podría explicar las manchas. Esto es, mirando al carácter precisamente en esta posición, el Granjero Juan puede predecir cuál de sus vacas tienen manchas y cuales no (aquí, A o G significan con manchas y C sin manchas; T es irrelevante pues no aparece en ninguna de las vacas del Granjero Juan en posición 2. La posición 1 no es suficiente por si sola para explicar las manchas, pues A en esta posición podría indicar una vaca con manchas o una vaca sin manchas.

Dados los genomas de las vacas del Granjero Juan, por favor cuente el número de posiciones que podrían potencialmente, por si solas, explicar las manchas.

Entrada

La primera línea de la entrada contiene N y M, ambos enteros positivos de tamaño a lo más 100. Cada una de las siguientes N líneas contiene una cadena de M caracteres; esas describen los genomas de las vacas con manchas. Las N líneas finales describen los genomas de las vacas sin manchas.

Salida

Por favor cuente el número de posiciones P (un entero en el rango 0 \leq P \leq M) en los genomas que podrían explicar potencialmente las manchas. Una posición explica potencialmente las manchas si la propiedad de tener manchas puede ser predicha con precisión entre la población de vacas del Granjero Juan mirando simplemente a esta posición en el genoma.

Ejemplo de Entrada

3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

Ejemplo de Salida

1

Comments

There are no comments at the moment.