Entrenamiento 2004
Tarea 4


Fecha de entrega: 11 de Mayo del 2004.


Problema 1: Predictivo

Problema 2: Anagrama

Problema 3: Ocurrencia


Problema 1: Predictivo

Se cuenta con un diccionario de M palabras y con un teclado de K botones. Cada botón se emplea para R letras (no necesariamente son diferentes las letras de un botón a otro). Dada una secuencia de N botones, tu misión es encontrar todas las palabras de largo N o mayor (que se encuentran en tu diccionario) tal que la letra i-esima de cada palabra, sea una letra de que pertenece al conjunto de letras del boton i de la secuencia dada.

Entrada (Archivo input.txt): En la primera línea vienen los dos valores 1 < K < 100 y 1 < R < 10. En las siguientes K líneas vienen el conjunto de letras para cada botón respectivamente. Cada línea contiene R caracteres separados por un espacio. En seguida, en una nueva línea viene el número 1 < M < 1000. En las siguientes M líneas vienen las M palabras del diccionario disponible. Cada palabra es a lo más de 20 caracteres. Por último viene el número 1 < N < 20 seguido de N enteros 0 < bi < K. Donde bi indica el índice del botón respectivo de la secuencia.

Salida (Archivo Output.txt): Debes imprimir en la primera línea un entero T que representa el número total de palabras encontradas. Después vienen las T palabras, una en cada línea.

Ejemplo:
Entrada Salida
4 3
a c o
o s a
t n o
r i e
9
casa
cocaina
asno
seso
tronco
conos
tinto
riso
saco
son
2
0 1 
4
casa
cocaina
asno
conos
 
 
 
 
 
 
 
 
 
 
 
 
 

Regresar a índice


Problema 2: Anagrama

Una palabra es anagrama de otra cuando se obtiene una letra de la otra por permutación de sus letras. Por ejemplo: saco es anagrama de cosa y de asco

Debes escribir un programa que: dado un diccionario castellano pueda determinar los conjuntos de anagramas.

Entrada (Archivo input.txt): En la primera línea viene un único entero 1 < N < 1000. En las siguientes N líneas vienen las N palabras del diccionario disponible. Cada palabra es a lo más de 20 caracteres.

Salida (Archivo Output.txt): Debes imprimir en la primera línea un entero T que representa el número total de conjunto de anagramas encontrados. Después vienen los T conjuntos, uno en cada línea. Cada línea contiene todas las palabras, separadas por un espacio, que son anagramas entre sí, la última palabra de cada línea va seguida de un salto de línea.

Ejemplo:
Entrada Salida
8
cava
empresa
cosa
torta
saco
trota
vaca
caso
4
cava vaca
empresa
cosa saco caso
torta trota
 
 
 
 

Regresar a índice


Problema 3: Ocurrencia

Se desea saber cual es la frecuencia de ocurrencia de una lista de letras en una lista de palabras. Se dice que la ocurrencia de una letra, en una lista de palabras, es K, si aparece K veces en la lista de palabras. Tu misión es escribir un programa que dada una lista de letras y una lista de palabras encuentre la ocurrencia de cada letra

Entrada (Archivo input.txt): En la primera línea viene un número 1 <N< 10 que indica el número de letras a evaluar. En la siguiente línea vienen los N caracteres a evaluar, separados por un espacio. De inmediato, en otra línea viene un único entero 1 < M < 10000. En las siguientes M líneas vienen las M palabras del diccionario disponible. Cada palabra es a lo más de 20 caracteres.

Salida (Archivo Output.txt): Debes imprimir N líneas. Cada línea contiene un caracter y su ocurrencia respectiva, primero el caracter y luego la ocurrencia separador por un espacio.

Ejemplo:
Entrada Salida
4
a e i k
7
edgar
limolin
kayam
marte
dan
rakel
kuko
a 6
e 3
i 2
k 4
 
 
 
 
 
 

Regresar a índice


Regresar

Última actualización: 4/Mayo/2004
Por Marte Ramírez