Set de Ejemplos de Problemas ODI

Los problemas de la clasificatoria están disponibles en concursos de práctica. Para intentar resolverlos, debes ir a: http://www.spoj.com/ODIPRACT/problems/main/

Más ejemplos en:

  1. CUADRADOS Y RECTANGULOS 
  2. MULTIPLOS PEQUEÑOS 
  3. BRACKETS
  4. INEVITABLEMENTE 100
  5. PARROTS
  6. GARDEN
  7. DREAMING

A continuación el contenido de algunos de problemas presentados en Olimpiadas pasadas:

ODI15F02 – Repartiendo Dulces

Ana es profesora del segundo año de primaria.  Ella está preparado un viaje de excursión con su curso para este fin de semana.  Como el viaje es largo, los estudiantes se impacientan.  Para mantener el grupo calmado, Ana tiene varias cajas de dulces, y cada una de estas cajas tiene exactamente la misma cantidad de dulces que las demás.

Si no se permite descartar ningún dulce ni dejar fuera ningún estudiante, cuántas cajas adicionales de dulce Ana debe comprar para repartir equitativamente los dulces entre todos lo estudiantes?

Entrada

La primera línea de entrada contiene un número entero C (1 ≤ C ≤ 5), la cantidad de casos de pruebas a procesar.

Cada una de las siguientes C líneas contiene 3 números enteros separados por un espacio en blanco. Los números son, en orden:

  • N (1 ≤  N ≤  1,000,000,000), la cantidad de estudiantes del curso
  • B (0 ≤  B ≤  100), la cantidad de cajas de dulces que Ana tiene inicialmente
  • K (1 ≤ K ≤  1,000), la cantidad de dulces en cada caja de dulces

Por lo menos 20% de los casos de pruebas tendrá N ≤  1,000,000.

Por lo menos 20% de los casos de pruebas tendrá B = 0.

Salida

Por cada caso de prueba, imprime una línea con la cantidad mínima de cajas que Ana debe comprar para repartir igual cantidad de dulces a cada estudiante de su curso.  Si no es posible hacer esta distribución equitativa, imprime -1.  La i-ésima línea debe corresponder con el i-ésimo caso de prueba.

Ejemplo

Entrada
3

35 12 4

35 4 12

32 12 4

Salida
23

31

4

Submit solution!

ODI14E04 – El Sueño de María

María es una adolescente muy soñadora. Tan soñadora, que afirma haberse soñado con el valor del dólar en los próximos n días. Esto es, María afirma saber el valor de compra y venta (que es el mismo) del dólar en los días D1, D2, D3, …, Dn.  Sabiendo esta información tan privilegiada, María pudiera incrementar sus ahorros, si compra barato y vende caro.

Sus padres son muy escépticos con estos sueños de María, pero de todas maneras llegaron a un acuerdo con ella. Le permitirán comprar una cantidad de dólares y luego venderlos no más de una vez en ése período de n días. Le pusieron una restricción adicional, ya que ellos no son muy buenos en matemáticas: María sólo podría comprar cantidades enteras (sin puntos decimales).

Conociendo esto, escribe un programa que compute la máxima cantidad de dinero (en pesos) que María pudiera tener luego de los n días, si sus sueños se volvieran realidad.

Entrada

En la primera línea habrán dos números enteros separados por un espacio: la cantidad de días (n) y la cantidad en pesos que María tiene ahorrado (D). Se garantiza que 1<= n, D <= 2000. La segunda línea tiene n enteros Ai (1 <= Ai <= 2000), cada uno de ellos representa el costo único de compra y venta en el día i.

Salida

Imprime un sólo número – la máxima cantidad de dinero (en pesos) que María puede obtener.

Ejemplos

Ejemplo #1:

Entrada
2 6

3 7

Salida
14

Ejemplo #2:

Entrada
5 20

5 4 3 2 1

Salida
20

Ejemplo #3:

Entrada
5 10

10 9 2 3 1

Salida
15

 Submit solution!

 ODI15E04 – El Ahorcado

El Ahorcado es un juego de adivinanzas de lápiz y papel para de dos jugadores. Uno de los jugadores piensa en una palabra y el otro jugador intenta adivinar la palabra letra por letra.

Bob y Alicia deciden jugar el juego.  Bob elige la palabra y Alicia adivina.

Inicialmente, Bob dibuja N guiones bajos (_) en la hoja de papel, donde N es la cantidad de letras en la palabra que él eligió.  En cada jugada, Alicia sugiere una letra que ella cree que existe en la palabra.  En caso de que existe, Bob debe escribir la letra en todas las posiciones donde aparece esa letra.  En caso de que esa letra no ocurre en la palabra, Bob dibuja una pieza de la figura del hombre palo en la horca.

El juego termina cuando Alicia logra llenar todas las letras de la palabra o cuando Bob complete el diagrama del ahorcado. En este ejercicio, asumiremos que la figura del ahorcado tiene 9 piezas.

Dado la palabra elegida por Bob y las letras que Alicia adivina, determina el estado final del juego.

Entrada

En la primera línea de entrada, tenemos la palabra elegida por Bob.  Este consiste en 1 a 15 letras (de A a Z del alfabeto inglés).

En la siguiente línea, tenemos la secuencia de letras que Alicia adivina, en orden cronológico, todos juntos sin espacios.  Es decir, la primera letra en la secuencia corresponde a la primera letra que Alicia adivina, la segunda corresponde la segunda letra que Alicia adivina, etc.  Las letras van de A a Z (del abecedario ingles) y estan en mayusculas.  Ninguna de las letras se repite.

Salida

Si Alicia gana, imprime la frase “Alicia gana en X pasos” (sin comillas), donde X es la cantidad de letras que Alicia utilizó para completar la palabra.

Si Alicia pierde, imprime la frase “Ahorcado hasta S“, donde S es la palabra de Bob, pero con guiones bajos (_) en las posiciones que Alicia no logró completar.

Ejemplos

Ejemplo #1

 

Entrada
AHORCADO

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Salida
Ahorcado hasta AH__CAD_

Ejemplo #2

 

Entrada
TIERRA

ECIUHZSXNTRLADYMBFPWVJQOGK

Salida
Alicia gana en 13 pasos

Ejemplo #3

Entrada
TIERRA

ECIUHZSXNTRLDAYMBFPWVJQOGK

Salida
Ahorcado hasta TIERR_

 Submit solution!

ODI14F01 – Nombres Entrelazados

Needlehole era una pequeña aldea ubicada en las Cuadernas del Oeste de la Comarca, muy cerca de Hobbiton, la aldea donde habitaba el ilustre Frodo Baggins. Desde el principio del tiempo, los residentes de Needlehole se distinguían de los demás por ser exitosos científicos y matemáticos, aportando muchas ideas científicas y revoluciones tecnológicas a la sociedad Hobbit.

Cuenta la leyenda, que sus primeras civilizaciones nombraban a sus hijos siguiendo un nombrado entrelazadopues consideraban que los nombres tradicionales eran muy aburridos. ¿Por qué? Cosas de genios. Al ser cuestionados por Hobbits de otras aldeas sobre este asunto, ellos decían siempre que les era más fácil construirel nombre del hijo primogénito de una pareja de amigos, que recordarlo. Allá ellos.

Sea Y el nombre del padre y X el nombre de la madre (ambos nombres de exactamente N caracteres) de un nuevo Hobbit Z. El nombre del padre se representa como una sucesión de caracteres Y=y0y1y2…yN-1 y, similarmente, el de la madre como X=x0x1x2…xN-1. Al Z nacer, este sería nombrado como Z =  x0y0x1y1… En otras palabras, más formalmente, el nombre de Z es la secuencia (zi), i =0, 1, 2, … dada por:

Escriba un programa que, dado el nombre del padre y de la madre, imprima el nombre de su bebé.

Entrada

La primera línea contiene dos cadenas de caracteres no vacías X y Y, los nombres de los padres de Z, separados por un solo espacio. Se garantiza que estos nombres estarán siempre en minúscula, que todas sus letras son del alfabeto anglosajón (igual al hispano, sin incluir la ñ) y que ninguno excederá 100 caracteres de longitud. La segunda línea contiene un entero d (1 ≤d ≤ 2N), la longitud máxima del nombre de Z.

Salida

Imprime en una sola línea el nombre de Z de acuerdo al nombrado entrelazado. Si Z tiene más de d caracteres, imprime solamente los primeros d.

Ejemplos

Ejemplo #1

Entrada
ceonomo ilsgaro

6

Salida
cielos

Ejemplo #2

Entrada
cronos alsis

6

Salida
carlos

Ejemplo #3

Entrada
laura juan

3

Salida
lja

 Submit solution!