Nombre Password [ Regístrate ]

Representantes (OIE 1 - 1997)

 

Sean A y B dos palabras de X letras. Dado un número entero R, R>0, diremos que A es una R-representación de B, abreviado por A=RB, si entre A y B no existen más de R diferencias.
Formalmente, dadas A=a1 a2 ... aX y B=b1 b2 ... bX, donde las ai y bi son las letras que componen las palabras, se puede definir:
A=RB si y solo si ||{i / 1<=i<=X con ai<>bi }||<=R
donde ||S|| es el tamaño del conjunto S. Así, la cadena "ESPERO" es una 2-representación de "EMBERO" (las únicas diferencias entre ambas palabras son la segunda y la tercera letras, es decir, a2<>b2 y a3<>b3), pero no es ni una 2-representación de "EMPUJO" (pues existen tres letras diferentes; por lo tanto, sí que es una 3-representación) ni una 1-representación de la misma "EMBERO".

Dados dos conjuntos S y T de palabras de X letras, diremos que S es una R-representación de T si para cada palabra t de T existe una palabra s de S tal que s es una R-representación de t:
S=RT si para todo t de T, existe s de S tal que s=Rt

Se pide que, dado un conjunto T de palabras de X letras, se identifiquen todos los subconjuntos S de T tales que S sea una R-representación de T y que sea mínimo; es decir, S debe cumplir:
S=RT i {para todo V contenido en T, (V=RT implica que ||V||>=||S||) }

Por ejemplo, para T={aaaa,aaab,aaac,aaba,aabb,aabc,abba} y R=1, los subconjuntos S son {aaaa,aaba}, {aaab,aaba} y {aaac,aaba}. En el primer caso, la palabra de S "aaaa" es una 1-representación de las palabras de T "aaaa","aaab", "aaac" y "aaba", mientras que la palabra de S "aaba" es una 1-representación de las palabras de T "aaaa", "aaba", "aabb", "aabc" y "abba", con lo que efectivamente todas las palabras de T son 1-representadas por las palabras de S.

Entrada

Residente en el fichero de caracteres "REPR.DAT":
- Línea 1: valor de R (un carácter del '1' al '9')
- Líneas sucesivas: cada una de las palabras incluidas en T; las palabras estarán formadas por letras minúsculas.

Salida

A guardar en el fichero de caracteres "REPR.OUT":
Presentación de todos los subconjuntos S que respondan a la definición anterior. Cada palabra de cada uno de los subconjuntos ocupará una línea; además, todas las palabras de un subconjunto deberán aparecer en el mismo orden en el que aparecen en la entrada. Los subconjuntos deberán estar separados por una línea en blanco.

Ejemplo de entrada

1
aaaa
aaab
aaac
aaba
aabb
aabc
abba

Ejemplo de salida

aaaa
aaba

aaab
aaba

aaac
aaba



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