Concurso Escolar de Programaci´on 2014 Cap´ıtulo Estudiantil ACM UCSP 6 de Diciembre del 2014

A.

´ Arbol de Navidad

La navidad est´ a cerca y todo el mundo ha comenzado a hacer los preparativos. Este a˜ no, Natasha debe armar el ´ arbol de navidad que colocar´a en la sala de su casa. ¿Puedes ayudarla? Un ´arbol de navidad est´ a compuesto por n tri´angulos, donde el primero tiene una base de longitud 3, el siguiente de longitud 5, el siguiente de longitud 7 y as´ı sucesivamente. Aqu´ı tienes un ejemplo para n = 4: * *** * *** ***** * *** ***** ******* * *** ***** ******* *********

Entrada La entrada consiste de una u ´nica l´ınea que contiene el entero n (1 ≤ n ≤ 10).

Salida Imprime un ´ arbol de navidad con n tri´angulos. Nota que no deben haber espacios al final del u ´ltimo asterisco en cada l´ınea.

Ejemplo Entrada 3 Salida * *** * *** ***** * *** ***** *******

1

B.

Henry y los tri´ angulos

Henry estaba un d´ıa muy aburrido y se puso a pensar en tri´angulos. Un pregunta invadi´ o su mente: ¿Es posible formar un tri´ angulo rect´angulo con 3 n´ umeros dados a, b y c?

Entrada La entrada consiste de una u ´nica l´ınea que contiene 3 enteros a, b y c (0 ≤ a ≤ b ≤ c ≤ 104 ), separados por un espacio.

Salida Debes imprimir una l´ınea conteniendo “SI” o “NO” seg´ un sea posible o no armar un tri´angulo rect´angulo con los n´ umeros dados.

Ejemplo 1 Entrada 3 4 5 Salida SI

Ejemplo 2 Entrada 3 6 8 Salida NO

2

C.

Pizza

Los miembros del Cap´ıtulo Estudiantil ACM de la UCSP, despu´es de sus reuniones mensuales, van siempre a comer pizza. Contrariamente a lo que se podr´ıa pensar, todos concuerdan en ir siempre a la misma pizzer´ıa. El problema es que en esta pizzer´ıa siempre cambian el n´ umero de piezas que trae cada pizza familiar. Adem´ as, no siempre asisten a la reuni´on la misma cantidad de miembros. Por ello, el Cap´ıtulo requiere de un programa que les ayude a calcular el m´ınimo n´ umero de pizzas que deben pedir para que todos coman la misma cantidad de piezas (sin dividirlas), dado que cada pizza consiste de n piezas y asisten m miembros a la reuni´on.

Entrada La entrada consiste de una u ´nica l´ınea que contiene los enteros n y m (1 ≤ n ≤ 10, 1 ≤ m ≤ 100)

Salida Debes imprimir una u ´nica l´ınea conteniendo un u ´nico entero: el m´ınimo n´ umero de pizzas que deben comprar seg´ un las restricciones dadas.

Ejemplo Entrada 8 6 Salida 3 Explicaci´ on

En 3 pizzas hay 24 piezas. Cada miembro comer´ıa 4 piezas.

3

D.

Arma tu Look

Jessenia quiere renovar su armario. Para ello, se dirigi´o a su centro comercial favorito CEP (Comercio, entretenimiento y pizza). All´ı encontr´o una gran promoci´on llamada “Arma tu look”. Para los n paquetes que Jessenia quiere llevar, cada uno con su propio precio Pi , ella deber´ a hacer lo siguiente: En cada paso tomar´ a 2 paquetes y pagar´a el precio del menor. Los 2 paquetes formar´an uno solo con un precio equivalente a la suma de ellos. El proceso se repite hasta que solo quede un paquete, el cual ya se lo puede llevar sin pagar m´as. Ella se dio cuenta que el monto total que pague depender´a del orden en que junte los paquetes. Sabiendo de tu gran capacidad algor´ıtmica, Jessenia te ha pedido que la ayudes.

Entrada La primera l´ınea contiene el entero n (1 ≤ n ≤ 105 ), el n´ umero de paquetes. La segunda l´ınea contiene n enteros Pi (1 ≤ Pi ≤ 100), separados por un espacio: el precio de cada paquete.

Salida Debes imprimir una u ´nica l´ınea conteniendo un u ´nico entero: el m´ınimo precio que Jessenia puede llegar a pagar para llevarse todos los paquetes.

Ejemplo Entrada 4 3 8 6 5 Salida 14 Explicaci´ on Si Jessenia junta el 2do y 3er paquete, paga 6 y obtiene un paquete de precio 14. Luego puede unir ´este con el paquete de precio 5, pagando 5 y obteniendo un paquete de tama˜ no 19. Finalmente, une ´este con el paquete de precio 3, pagando 3. En total, pag´o: 6 + 5 + 3 = 14.

4

E.

Halloween

Andrea y Juan salen cada Halloween a pedir dulces. Este a˜ no ellos piensan consiguir muchos dulces, pero a ambos les encanta los chocolates. Ninguno de los dos tiene la intenci´on de compartir los chocolates con el otro, por eso siempre juegan un peque˜ no juego y el perdedor se queda sin chocolates. El juego consiste en poner en una torre los chocolates obtenidos. En el primer turno, Andrea (Ella siempre iniciar´ a el juego) puede quitar cualquier n´ umero de chocolates de la torre, siempre que este n´ umero sea mayor a cero y menor al n´ umero de chocolates que hay en la torre. Luego de esto, ellos alternaran movimientos. En cada turno, el jugador debe quitar cualquier n´ umero mayor a cero de chocolates (incluso toda la torre), pero no podr´a quitar un n´ umero de chocolates igual al de un movimiento anterior (de ambos jugadores). El jugador que no pueda realizar un movimiento pierde. Andrea sabe que Juan siempre jugar´a de una manera ´optima, pues es muy astuto. Pero ella ya ha contado los chocolates que han recolectado, as´ı que podr´ıa saber si tiene alguna opci´on de ganar o, en caso contrario, le dir´ a a Juan que es muy tarde y que deber´ıan repartirse los chocolates equitativamente.

Entrada La entrada consiste de un u ´nico entero n (1 ≤ n ≤ 109 ), el n´ umero de chocolates.

Salida Deber´as imprimir el nombre del jugador que gana (Andrea o Juan) si ambos juegan de forma ´optima.

Ejemplo 1 Entrada 4 Salida Juan Explicaci´ on Si Andrea toma 1, Juan toma 3 y gana. Si Andrea toma 2, Juan toma 1 y gana (ya no le quedan movimientos a Andrea). Si Andrea toma 3, entonces Juan toma 1 y gana. En conclusi´on, Andrea no tiene ninguna opci´on de ganar.

Ejemplo 2 Entrada 6 Salida Andrea

5

F.

Enepelanders

Los ciudadanos de Algoritmilandia son personas muy pac´ıficas a las que les encanta resolver problemas. Sin embargo, los enepelanders no lo son. A decir verdad, siempre que dos de ellos se encuentran, terminan peleando por “querer reducir al otro”, como ellos arguyen. Lamentablemente, solo ellos pueden garantizar la seguridad de las calles de Algoritmilandia. Un enepelander se coloca en una esquina y puede vigilar todas las calles y esquinas adyacentes. Ninguna calle puede estar vigilada por dos enepelanders porque pelear´ıan. Dada esta informaci´on, los ciudadanos de Algoritmilandia te han pedido ayuda para saber si es posible tener las calles de su ciudad vigilada sin que los enepelanders puedan pelear y con el menor n´ umero de enepelanders posible.

Entrada La primera l´ınea contiene dos enteros v (1 ≤ v ≤ 200) y e (0 ≤ e ≤ 10000). v es el n´ umero de esquinas de la ciudad y e es el n´ umero de calles. Cada una de las siguientes e l´ıneas contiene 2 enteros s, t que indican que existe una calle entre las esquinas s y t. Las esquinas est´an numeradas de 0 a v − 1. Nota

Algoritmilandia es una ciudad un poco rara: a veces encuentras esquinas sin calles.

Salida Deber´as imprimir un u ´nico entero m, indicando el m´ınimo n´ umero de enepelanders necesarios para vigilar todas las calles y esquinas de Algoritmilandia o -1 si no es posible colocar los guardias sin que se peleen.

Ejemplo 1 Entrada 4 2 0 1 0 2 Salida 2 Explicaci´ on

Los enepelanders deben estar en los nodos marcados en negro:

6

Ejemplo 2 Entrada 5 0 1 2 0 3

5 1 2 3 4 4

Salida -1

7