Download Problem A: Juego de PI (I)

Problem A: Juego de PI (I)
Time Limit: 2 seconds
Description
¿Conoces el juego de PI? Es un juego muy común en las reuniones con el
afán de castigar a alguien. Consiste principalmente en decir los números
naturales en el orden que conocemos, pero cualquier número múltiplo de 7
o que termine en 7 o que la suma de sus dígitos sea múltiplo de 7, debe
decirse “pi” en vez del número. De esta forma la serie de un juego perfecto
empezaría con
1, 2, 3, 4, 5, 6, pi, 8, 9, 10, 11, 12, 13, pi, 15, pi, pi, 18, 19, 20, pi, 22, 23,
24, pi, 26, pi, pi, 29 ...
Para realizar el juego se forma un círculo. Alguien empieza diciendo “1”, y
siguiendo el giro de las manecillas del reloj la persona de a lado le toca decir el siguiente valor de la serie y
así consecutivamente hasta que alguien no diga el número de PI correcto. Aquella persona que falla es
castigada y empieza el siguiente juego con el “1”.
Tu tarea consiste en dado un número entero positivo decir el número de PI correcto.
Input
La entrada consiste de varios casos de prueba. Cada caso consiste de una línea que contiene un número
entero positivo n < 10^9. La entrada termina con un caso cuando n = 0, este último caso no debe producir
salida alguna.
Output
Por cada caso, imprime una línea con el número de PI correcto que le corresponde a n en el formato que se
muestra en el ejemplo de salida.
Sample input
1
7
13
14
15
16
17
0
Sample output
1
pi
13
pi
15
pi
pi
Problemsetter: Gabriel Filiberto López Pérez
Problem B: Mayor, menor o igual
Time Limit: 2 seconds
Description
Se cree que el uso de la base 10 para nuestra representación numérica se debe al
hecho de que tenemos 5 dedos en cada una de nuestras manos. Sin embargo es
muy fácil darse cuenta que no es la única base que podría usarse. En ACMilandia
usan la base 27, eso quiere decir que un número de la forma xn … x1 x0
equivaldría a base 10 a la suma de (27^n)xn + … + 27x1 + x0.
Ellos no usan el signo “-” que utilizamos para los números negativos. Por ello
usan digitos de xi con valores negativos y positivos con un valor decimal entre
[-26, 26]. Los símbolos que utilizan para sus dígitos se muestran a continuación:
‘0’ = 0, ‘A’ = 1, ‘B’ = 2, ‘C’ = 3, …, ‘Z’ = 26, ‘a’ = -1, ‘b’ = -2, ‘c’ = -3, …, ‘z’ = -26.
Tu tarea consiste en dado dos números ACMilándicos, verifiques si el primero es mayor, menor o igual al
segundo.
Input
La entrada consiste de varios casos de prueba. Cada caso de entrada consiste de una línea que contiene dos
números válidos ACMilándicos A y B separados por un espacio (A y B contienen entre 1 y 1000 dígitos). La
entrada termina con A = B = “EOF”, este último caso no debe producir salida alguna.
Output
Por cada caso de entrada imprime una línea con el mensaje “mayor” si A > B, “menor” si A < B, o
“igual” si A = B.
Sample input
Aa Z
A0 AA
AA A0
EOF EOF
Sample output
igual
menor
mayor
Problemsetter: Gabriel Filiberto López Pérez
Problem C: Incongruencias
Time Limit: 4 seconds
Description
Supongamos que tenemos un número binario de 4 bits [a3 a2 a1 a0] su valor
decimal correspondería al valor que resulta de 8a3 + 4a2 + 2a1 + 1a0, por lo que
se puede decir que el vector de factores multiplicativos de un número binario de
4 bits comúnmente aplicado es [8, 4, 2, 1]. Sin embargo podemos utilizar otro
vector de factores multiplicativos para el caso particular de un número binario
de 4 bits como por ejemplo [4, 8, 1, 2] o también [1, 3, 5, 10]. Ve la siguiente
tabla para ver cómo afecta al valor decimal representado cambiando los factores.
Binario
0000
0001
0010
0011
0100
0101
0110
0111
[8,4,2,1]
0
1
2
3
4
5
6
7
[4,8,1,2]
0
2
1
3
8
10
9
11
[1,3,5,10]
0
10
5
15
3
13
8
18
Binario
1000
1001
1010
1011
1100
1101
1110
1111
[8,4,2,1]
8
9
10
11
12
13
14
15
[4,8,1,2]
4
6
5
7
12
14
13
15
[1,3,5,10]
1
11
6
16
4
14
9
19
Algo que tienen en común es que cualquiera de los 3 vectores multiplicativos usados en la tabla previa, asocian a un
número decimal de una única forma o no lo pueden asociar (por ejemplo, el número 2 decimal no puede ser
representado como un número binario de 4 bits usando el vector [1,3,5,10]). Por otra parte si utilizamos el vector
[1,2,3,4], el número decimal 6 puede ser representado con los números binarios de 4 bits: 1110 y 0101.
Tu problema consiste dado la base b (1 < b < 11), el número de dígitos n (n ≤ 1000), y un vector de factores
multiplicativos [e1 e2 … en]. Decidir si existen números que tienen más de una representación. Puedes estar seguro
que (b-1) (e1 + e2 + … + en) ≤ 10,000,000.
Input
La entrada consiste primero de una línea que un entero nc (0 < nc ≤ 100) que indica el número de casos a procesar.
Cada línea siguiente corresponde a un único caso de entrada con los valores de b, n y e1, e2, …, en descritos antes.
Output
Por cada caso imprime una línea con el mensaje ‘YES’ si existen números que tienen más de una representación, ‘NO’
en otro caso. Ve el ejemplo de entrada y salida para mas detalle.
Sample input
4
2
2
2
2
4
4
4
4
8
4
1
1
4
8
3
2
2
1
5
3
1
2
10
4
Sample output
NO
NO
NO
YES
Problemsetter: Gabriel Filiberto López Pérez
Problem D: Puentes
Time Limit: 5 seconds
Description
El arte de construir puentes tiene su origen en la misma prehistoria. Puede
decirse que nace cuando un buen día se le ocurrió al hombre prehistórico
derribar un árbol en forma que, al caer, enlazara las dos riberas de una
corriente sobre la que deseaba establecer un vado. La genial ocurrencia le
eximía de esperar a que la caída casual de un árbol le proporcionara un puente
fortuito. También utilizó el hombre primitivo losas de piedra para salvar las
corrientes de pequeña anchura cuando no había árboles a mano. Desde
entonces un puente se utiliza para conectar dos territorios que no son
fácilmente alcanzables entre sí.
El pueblo ACM está dividido en dos regiones: la Este y la Oeste, por el Río
UVAsimasinta. A su vez la región Este se divide en la secciones: Este 1, Este
2, …, Este n; mientras que la Oeste en: Oeste 1, Oeste2, …, Oeste n. Por
motivos de expansión y para no usar números negativos: los números pares
están en el lado norte, mientras que los impares en el sur. Para más claridad ve el dibujo del problema.
Cansados de atravesar por lancha, se optó por hacer puentes para comunicar una sección del este con otra del oeste. Lo
más óptimo sería hacer n puentes, cada uno conectando la sección Este i con la Oeste i. Sin embargo por motivos de
que existen represalias entre los habitantes de algunas secciones se hizo un consenso para que cada sección del Este
decidiera (después de todo ellos fueron los de la idea) a cuál sección del Oeste le gustaría construir su único puente.
Tu tarea consiste en decir cuál será la mayor cantidad de puentes que pueden ser construidos sin que se intercepte un
puente con otro.
Input
La entrada consiste de varios casos de entrada. Cada caso consiste de una línea con los valores de n P1 P2 … Pn,
donde n ( 0 < n <= 10,000) es el número de secciones en que está dividido cada sección principal y Pi ( 1 <= i, Pi <=
n) indica que la sección “Este i” desea conectarse con la sección “Oeste Pi”. La entrada termina con EOF.
Output
Por cada caso de entrada imprime una línea que indique el máximo número de puentes que se pueden construir sin que
se intercepte un puente con otro, aplicando las restricciones que los habitantes de la región Este han impuesto.
Sample input
3 1 3 2
3 1 1 1
3 3 1 2
Sample output
1
3
2
Problemsetter: Gabriel Filiberto López Pérez
Problem E: Juego de letras
Time Limit: 5 seconds
Description
Seguramente estás familiarizado con el juego de letras que consiste en buscar palabras en un mapa de letras. Las
palabras pueden estar en horizontal, vertical o en diagonal. Sin embargo este juego de letras es distinto a los demás,
como se puede observar en los siguientes ejemplos:
1
3
2
3
4
4
4
2
1
3
4
4
1
2
4
3
3
2
3
4
2
2
1
2
3
3
2
3
4
4
3
2
1
4
3
2
1
1
4
2
3
2
3
1
3
3
2
1
4
2
1
4
3
2
1
2
3
4
1
3
4
4
1
3
2
1
1
4
3
1
2
2
1
1
2
1
3
4
1
2
4
2
1
3
4
1
1
4
1
3
2
2
3
4
1
4
En este mapa los bordes no son limitantes. Ya que siempre existe una forma de continuar con el anagrama, tal y como
se muestran en los ejemplos anteriores donde se ilustran todas las formas en que se puede formar la cadena ‘1234’ o
‘4321’ como lo quieras ver.
Dado un mapa de n x n (2 < n < 501) caracteres alfanuméricos y m (0 < m < 31) palabras a buscar, imprime el valor
decimal del número binario de m digitos Bm Bm-1 … B1, donde Bi = 0 (0 < i <= m) si la i-ésima palabra no puede ser
encontrada en el anagrama y Bi = 1 en caso contrario. Puedes estar seguro que todas las letras que conforman al mapa
y a las palabras a buscar son todas minúsculas.
Input
La entrada consiste de varios casos de prueba. La primera línea de cada caso consiste de los valores de n y m, luego le
siguen n líneas con un mapa de n x n caracteres, y al final una lista de m palabras (cada una de ellas en una línea
diferente). La entrada termina con un caso m = n = 0, este último caso no debe producir salida alguna.
Output
Por cada caso imprime una línea con el número decimal formado a partir de las palabras que fueron o no encontradas
en el anagrama. Lee la descripción para más detalle.
Sample input
3 4
hol
aod
num
hola
mundo
nolu
cara
0 0
Sample output
7
Problemsetter: Gabriel Filiberto López Pérez
Problem F: Estrellas
Time Limit: 5 seconds
Description
La estrella más común de todas que dibujamos es aquella de 5 picos como
la que se muestra. Si queremos hacer que la estrella tenga otra cantidad de
picos (digamos n) podemos intentar lo siguiente para dibujarlo:
1. Dibuja una circunferencia
2. Pon n puntos de referencia en el contorno de la circunferencia de tal
forma que la distancia entre cualquier pareja de puntos vecinos sea
exactamente el mismo.
3. Selecciona un punto de referencia inicial Pi y un valor entero k
entre [2, n-2].
4. Traza una línea del punto inicial Pi a Pj donde Pj es el punto que se
encuentra k posiciones adelante siguiendo las manecillas del reloj.
Repite el procedimiento pero ahora a partir del punto Pj, y así hasta
que hayas dibujado exactamente n líneas.
5. Si el dibujo resultó una estrella de n picos felicidades, en caso contrario elige un nuevo valor de k y repite los
pasos 3, 4 y 5. Si ya intentaste todos los valores posibles de k, lo sentimos, pero si quieres dibujar una estrella
con la cantidad de picos que elegiste, tendrás que usar otro procedimiento.
Por ejemplo la estrella anterior resulta de (n = 5, k = 2) y también de (n = 5, k = 3).
Si lo intentas te darás cuenta que para muchos valores de k y n no forman una estrella, pero para otros si. Dado n (3 < n
< 10^9) calcula el número de valores de k distintos de entre [2, n-2] que forman una estrella de exactamente n picos
con el procedimiento anterior.
Input
La entrada consiste de varios casos de entrada. Cada caso consiste de una línea que contiene un número entero positivo
3 < n < 10^9. La entrada termina con un caso cuando n = 0, este último caso no debe producir salida alguna.
Output
Por cada caso imprime una línea con el número valores de k distintos de entre [2, n-2] que forman una estrella de
exactamente n picos con el procedimiento anterior.
Sample input
4
5
6
7
0
Sample output
0
2
0
4
Problemsetter: Gabriel Filiberto López Pérez
Problem G: Prime Network
Time Limit: 5 seconds
Description
En el año 1975, el módulo 1 de la FCC tenía n computadoras, cada
computadora estaba conectada físicamente con las (n-1) restantes para formar
su red local (si el cable que conectaba la computadora i con j se averiaba, ya
no existía forma alguna de comunicarse entre i y j). ¡Ya se imaginarán el
cablerío que existía!
Cada computadora tenía una dirección IP única 192.168.0.i (0 < i <= n) con
respecto a las demás computadoras enlazadas en la misma red. Un virus ha
atacado a la red y no permite comunicar a cualquier equipo con dirección
192.168.0.i con otro equipo con dirección 192.168.0.j si i + j no es primo.
Cansados de intentar eliminar el virus, optaron por modernizar la red a una
con topología de anillo donde cada computadora está conectada a otras dos computadoras distintas de tal forma que se
puedan comunicar entre ellas aún con el virus. Puedes ver un ejemplo de una red con topología de anillo en el dibujito
del problema.
Dada una red con n ( n < 256) computadoras con direcciones 192.168.0.1, 192.168.0.2, …, 192.168.0.n. Imprime
alguna configuración en que debe estar conectadas las computadoras de tal forma que se pueda hacer una red con
estructuras de anillo tomando en consideración las restricciones que el virus presenta.
Input
La entrada consiste de varios casos de entrada. Cada caso consiste de una línea que contiene un número entero positivo
2 < n < 256. La entrada termina con un caso cuando n = 0, este último caso no debe producir salida alguna.
Output
Por cada caso imprime una lista con las n direcciones IP, enteros separados por un espacio en blanco, de la forma en
que las computadoras deben estar conectadas para formar la estructura de anillo y que cumpla los requerimientos
mostrados antes. En caso de no existir ninguna imprime ‘Imposible’.
Sample input
3
4
0
Sample output
Imposible
192.168.0.1 192.168.0.2 192.168.0.3 192.168.0.4
Nota: Cualquier solución de más de 8K de código será respondido como 'Wrong Answer'. Lo cuál siendo
sinceros no es una limitante para enviar una tabla.
Problemsetter: Gabriel Filiberto López Pérez
Problem H: Palíndromos X
Time Limit: 4 seconds
Description
Una palabra se dice palíndromo si la misma palabra es
exactamente idéntica al derecho y al revés como por ejemplo 'ABA', 'AA', 'A' y 'CASAC'. Por otra parte cualquier
secuencia de caracteres puede ser vista como 1 o más secuencias de palíndromos concatenadas. Por ejemplo ‘guapa’ es
la concatenación de los palíndromos ‘g’, ‘u’ y ‘apa’; o ‘casacolorada’ es la concatenación de ‘casac’, ‘olo’, ‘r’, ‘ada’.
El problema consiste dado una palabra de a lo máximo 2000 letras minúsculas, imprime el número mínimo de palabras
palíndromas en que se puede dividir.
Input
La entrada consiste de una línea por caso, cada línea contiene una cadena s de entre 1 y 2000 caracteres. La entrada
termina con EOF. Puedes estar seguro que la entrada no contiene más de 1000 casos.
Output
Por cada caso imprime el número mínimo de palabras palíndromas en que se puede dividir s.
Sample input
casacolorada
casac
hola
Sample output
4
1
4
Problemsetter: Gabriel Filiberto López Pérez
Problem I: Juego de PI (II)
Time Limit: 10 seconds
Description
Seguramente ya has resuelto el problema A: Juego de PI (I), si no lo has hecho te
recomiendo que lo hagas para entender mejor este problema y te evites leer de
nuevo el mismo choro.
Este problema consiste en dado un número n entre 1 y 100, calcula la cantidad de
números que existen entre [1, 10^n] de tal forma que hay que decir ‘pi’ en vez del
número, en un juego de PI perfecto.
Input
La entrada consiste de varios casos de entrada. Cada caso consiste de una línea que contiene un número entero positivo
n <= 100. La entrada termina con un caso cuando n = 0, este último caso no debe producir salida alguna.
Output
Por cada caso imprime una línea con el número que representa a la cantidad de número que existen entre [1, 10^n] de
tal forma que hay que decir 'pi' en vez del número, en un juego de PI perfecto.
Sample input
1
0
Sample output
1
Problemsetter: Gabriel Filiberto López Pérez