Nombre Password [ Regístrate ]

El proyecto genoma (OIE 4 - 2000)

 

Una cadena de ADN es una palabra compuesta por las letras A, C, G y T. Queremos clasificar dichas cadenas según las relaciones entre sus integrantes considerados por parejas. Dada la cadena X = x1 x2 ... xk, el par (xm, xn) está ordenado si xm es alfabéticamente menor o i gual que xn. Definimos la función desorden(X) como el número de pares desordenados (xm, xn) tales que m < n. Así, desorden("CCGATC") = 5, siendo los pares desordenados (x1, x4), (x2, x4), (x3, x4), (x3, x6) y (x5, x6).

Objetivo

Dada una lista de cadenas de ADN todas del mismo tamaño, producir una lista de las mismas cadenas ordenadas según el valor de la función desorden.

Entrada

La entrada del programa consiste de una secuencia de líneas, que residen en un archivo de texto (ASCII) con nombre ADN.DAT, que tendrá el siguiente formato:

· La primera línea (la 1) contiene el número m de cadenas de ADN que aparecen en la entrada. Podéis suponer que se cumple 1 <= m < 100.
· Las m líneas siguientes (de la 2 a la m+1) contienen, cada una, una cadena de ADN. Cada cadena está formada íntegramente por las letras A, C, G y T. Todas las líneas tendrán la misma longitud, que será de 30 caracteres como máximo.

Salida

La salida del programa ha de grabarse en un archivo de texto (ASCII) con nombre ADN.RES, que contendrá una secuencia de m líneas con las mismas cadenas de ADN que en la entrada, pero ordenadas crecientemente según el valor de la función desorden aplicada sobre ellas. Aquellas cadenas con el mismo valor de desorden se ordenarán alfabéticamente, también de menor a mayor.

Ejemplo de entrada

6
TTTTGGCCAA
CCCGGGGGGA
TTTGGCCAAA
GATCAGATTT
AACATGAAGT
ATCGATGCAT

Ejemplo de salida

AACATGAAGG
CCCGGGGGGA
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA



© (2001-2008) ALGORITMIA.NET - Política de privacidad