Download Examen de C

Olimpiada de Informática del Estado de Jalisco
Ciclo Olímpico 2012
Etapa 3
CATEGORIA UNIVERSITARIA
PROBLEMA: BUSCANDO (buscando.cpp o buscando.c)
PROBLEMA
Dado un número entero 1≤ N ≤ 100,000,000 y un lista de M números enteros 3 ≤ Mi ≤ 50,000
Encuentra un conjunto de 3 números de la lista, tales que su suma sea igual al número N.
ENTRADA
Tu programa deberá leer de teclado el numero a buscar N en al primer linea, en la segunda línea el
número M y en las siguientes M líneas los números de la lista.
SALIDA
Tu programa deberá obtener como resultado tres números de la lista dada tales que su suma sea igual al
número N. Los tres números deberán estar escritos en la misma línea, separados cada uno por un espacio.
NOTA: En el caso de que exista más de una solución, tu programa solo deberá escribir una de ellas.
EJEMPLO
Entrada
25
10
15
8
1
4
18
3
32
12
4
10
Salida
4 18 3
Olimpiada de Informática del Estado de Jalisco
Ciclo Olímpico 2012
Etapa 3
PROBLEMA: WORSE (worse.cpp o worse.c)
La Organización Mundial de Información Justicia Armamento y Legalidad (OMIJAL) dirigida por el Dr.
Doofenshmirtz tiene secuestrado a Karel en sus cuarteles centrales. Tú, agente ‘P’, tendrás que descifrar la
contraseña de la puerta donde tienen secuestrado a Karel para después traerlo a salvo a Guadalajara.
Hemos estudiado la contraseña de la puerta y después de mucho estudiarla nos dimos cuenta que nos
permite escuchar un “recordatorio de la contraseña”. Este recordatorio está en lenguaje Worse donde se
repite siempre una cantidad N de veces la palabra “wo”, esta cantidad de veces representan las letras que
hay que presionar en el teclado para abrir la puerta, sabemos la cantidad de veces que repite “wo” para
representar cada una de las letras entre a y z, y tenemos una lista de K palabras que pudieran ser la
contraseña.
Por ejemplo si sabemos que la a es “wo” 1 vez, b es “wo” 2 veces y c es “wo” 3 entonces wo wo wo wo wo
wo wo (7 veces wo) presenta la cadena abc.
Problema
Dada la lista de palabras que pueden ser la contraseña que abre la puerta, la cantidad de veces que se dice
“wo” para cada letra y la cantidad de veces que se dice “wo” en el recordatorio de la contraseña, deberás
decir cuales palabras dentro de la lista pudieran abrir la puerta.
Entrada
En la primera línea de entrada tendrás dos números enteros K y N. Las siguientes K líneas serán las K
palabras que sospechamos son contraseña. Las siguientes 27 líneas contienen la cantidad de veces que se
dice “wo” por la i-ésima letra. (La primera de estas líneas es cuantas veces se dice “wo” por la a, la
segunda es cuantas veces se dice “wo” por la b y asi sucesivamente hasta la z)
Salida
La salida será una lista de palabras que dicen tantos “wo” como el recordatorio y por tanto pudieran abrir
la puerta.
Ejemplo
Entrada
57
hola
worse
karel
abc
uno
1
2
4
5
Salida
abc
Olimpiada de Informática del Estado de Jalisco
Ciclo Olímpico 2012
Etapa 3
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Olimpiada de Informática del Estado de Jalisco
Ciclo Olímpico 2012
Etapa 3
PROBLEMA: WORSE RELOAD (worser.cpp o worse.c)
(Si no entiendes el contexto del problema, lee el problema worse primero)
Has abierto la puerta y te has encontrado con Karel, ¡felicidades!, ahora tendrás que traerlo a
casa. Entendemos que tu situación es crítica dado que has sido capturado y han cambiado la
contraseña, para poder salir necesitarás obtener una lista de palabras que coincidan con la
cantidad N de “wo” que la puerta dice, sabemos que la cantidad de diferentes palabras con esta
cantidad de “wo” pueden ser muchas así que para poder entregarte una lista de posibles
contraseñas como lo hicimos anteriormente necesitamos que nos digas cuantas palabras podrían
ser aceptadas por la puerta.
Problema
Dados la cantidad N de “wo” que dice el recordatorio de la puerta para poder abrirla, y la
cantidad de “wo” que se dice por cada letra del abecedario debes decir cuantas palabras
diferentes podrían abrir la puerta.
Entrada
La primer línea tendrá un número N (1<=N<=100000). Las siguientes 27 líneas contienen la
cantidad de veces que se dice “wo” por la i-ésima letra. (La primera de estas líneas es cuantas
veces se dice “wo” por la a, la segunda es cuantas veces se dice “wo” por la b y asi sucesivamente
hasta la z)
Salida
Un único número entero que indique cuantas palabras diferentes pudieran abrir la puerta
módulo 1000000.
Ejemplo
Entrada
4
1
2
4
7
8
9
10
11
12
13
14
15
Salida
6
Olimpiada de Informática del Estado de Jalisco
Ciclo Olímpico 2012
Etapa 3
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Detalles de la salida:
La entrada especifica que la puerta dira 4 veces “wo” como recordatorio.
La letra a es 1 “wo”, la b son 2 “wo”, la c son 4 “wo”, la d son 7 “wo” etc, ….
Las palabras “c”,”bb”,”aaaa”,”aab”,”aba”,”baa” requerirían de 4 “wo” para ser mencionadas en worse, asi
que estas 6 serian las palabras como posibles contraseñas.