Download Guía de Ricardo Monascal

Universidad Simón Bolívar
Departamento de Computación y Tecnología de la Información
Guías de Entrenamiento para Maratones de Programación al estilo ACMICPC.
Guía de Entrenamiento:
(
)
Principiantes
Esta guía está pensada para servir como un apoyo para aquellos que deseen entrenar y participar en maratones de programación al estilo de ACMICPC, Google Code Jam, etc. En esta
guía no habrá problemas resueltos, sino enlaces a problemas interesantes que deberían tratar de
resolver ustedes mismos para medir el nivel en el que se encuentran. Cada guía tendrá 100 puntos
repartidos en varios problemas, valuados según su dicultad. Es recomendable que no avancen a
la siguiente guía hasta obtener al menos 80 puntos en la actual.
Esta guía es la primera que deberían intentar resolver. Está orientada a aquellos que aún no
han participado en su primer maratón, o que deseen practicar problemas estilo adhoc, que no
requieren de una técnica en particular (las cuales se tocarán en guías posteriores).
1
¾Donde comenzar?
Los problemas a resolver serán del juez virtual SPOJ, por lo que lo primero que hay que hacer
es ingresar a la página: www.spoj.pl y crear una cuenta (si no la tiene ya).
SPOJ es un juez virtual, que toma soluciones para problemas de programación y emite un
veredicto sobre si es correcta o no. Entre los posibles veredictos más comunes se encuentran:
Accepted:
La solución al problema es correcta.
Wrong Answer:
La solución del problema no es correcta.
La solución del problema tomó mas tiempo ejecutándose que el tiempo
límite para el problema.
Time Limit Exceeded:
La solución del problema no compiló (posiblemente se seleccionó mal el
Lenguaje en las opciones de envío.)
Compilation Error:
Run Time Error:
La solución del problema abortó con un error.
Existen otros posibles resultados, sin embargo estos son los más comunes. La entrada y salida
para los problemas es tomada por la entrada/salida estándar y no hace falta leer toda la entrada
antes de comenzar a imprimir la salida pues, a pesar de que la consola los muestra juntos, la
entrada y la salida corresponden a destinos diferentes.
1
Una vez creada la cuenta, llega la hora de resolver nuestro primer problema:
Problema:
a)
Código:
Enlace:
Valor:
Life, the Universe, and Everything
TEST
www.spoj.pl/problems/TEST/
5 puntos
¾Pero en que Lenguaje lo resolvemos? SPOJ permite muchos diferentes lenguajes de programación, sin embargo deberemos resolver los problemas exclusivamente en Java o C/C++ (ya que
son los lenguajes aceptados en ACMICPC). Aunque es recomendable que uno conozca muy bien
uno de estos lenguajes, no se puede ignorar el otro. Cada Lenguaje de programación tiene sus
ventajas y desventajas que hay que saber manejar. Para saber un poco más sobre esto, les recomiendo esta entrada de blog: throwingcodes.blogspot.com/2010/10/escoge-tu-bien-arma.html.
Para este problema en particular, debe dar una solución tanto en Java como en C/C++ (uno
solo de entre C y C++), para considerar ganados los puntos del problema. Para el resto de los
problemas de la guía el lenguaje es libre, aún entre Java o C/C++, pero basta con resolverlo en
uno solo de ellos (a menos que se especique lo contrario).
2
Problemas propuestos:
Problema:
b)
Código:
Enlace:
Valor:
Problema:
c)
Código:
Enlace:
Valor:
Problema:
d)
Código:
Enlace:
Valor:
Problema:
e)
Código:
Enlace:
Valor:
Problema:
f)
Código:
Enlace:
Valor:
Problema:
g)
Código:
Enlace:
Valor:
Adding Reversed Numbers
ADDREV
www.spoj.pl/problems/ADDREV/
5 puntos
Hello Kitty
HELLOKIT
www.spoj.pl/problems/HELLOKIT/
5 puntos
He is oside!
OFFSIDE
www.spoj.pl/problems/OFFSIDE/
5 puntos
Candy I
CANDY
www.spoj.pl/problems/CANDY/
5 puntos
Number Steps
NSTEPS
www.spoj.pl/problems/NSTEPS/
5 puntos
Hangover
HANGOVER
www.spoj.pl/problems/HANGOVER/
5 puntos
2
Problema:
h)
Código:
Enlace:
Valor:
Problema:
i)
Código:
Enlace:
Valor:
Problema:
j)
Código:
Enlace:
Valor:
Problema:
k)
Código:
Enlace:
Valor:
Problema:
l)
Código:
Enlace:
Valor:
Problema:
m)
Código:
Enlace:
Valor:
Problema:
n)
Código:
Enlace:
Valor:
3
Draw Mountains
DRAWM
www.spoj.pl/problems/DRAWM/
5 puntos
Triple Fat Ladies
EIGHTS
www.spoj.pl/problems/EIGHTS/
5 puntos
Bullshit Bingo
BINGO
www.spoj.pl/problems/BINGO/
10 puntos
Count On Cantor
CANTON
www.spoj.pl/problems/CANTON/
10 puntos
Cylinder
CYLINDER
www.spoj.pl/problems/CYLINDER/
10 puntos
Java vs C++
JAVAC
www.spoj.pl/problems/JAVAC/
10 puntos
Uncle Jack
UJ
www.spoj.pl/problems/UJ/
Java: 5 puntos, C/C++: 10 puntos
¾Donde consigo más información?
En la web hay montones de tutoriales para aprender Java, C y C++. Sin embargo, las referencias
obligadas son el API para Java: docs.oracle.com/javase/6/docs/api y la referencia de C++:
en.cppreference.com/w, que tiene la documentación para todas las clases y elementos del lenguaje.
Sobre los problemas, es preferible intentar resolverlos por cuenta propia. Sin embargo, está
disponible el foro de SPOJ para resolver dudas puntuales sobre los mismos o sobre el juez en sí:
www.spoj.pl/forum.
Mi dirección de correo electrónico es rmonascal@ldc.usb.ve. Cualquier cosa, estoy a la orden
para dudas o sugerencias con estas guías. También tengo un blog sobre el tema, pueden visitarlo
aquí: throwingcodes.blogspot.com. ½Mucho éxito!
Ricardo Monascal / 2012
3