Parcial 1 de Competitiva
abr0
El Parcial 1 de Programación Competitiva se tomará el día Jueves 17 de Mayo de 2012 a las 16:00, entran todos los temas vistos hasta esta semana (incluídos).
A estudiar!!!
Problema C: Numeros reciclados
abr1
Problema
Alguna vez te sentiste frustrado con la televisión porque siempre estás viendo las mismas cosas, recicladas una y otra vez? Bien, personalmente no me preocupa la televisión, pero siento lo mismo con números.
Digamos que una par de enteros positivos distintos (n, m) es reciclado si puedes obtener m moviendo algunos dígitos desde la parte de atrás de n al frente sin cambiar su orden. Por ejemplo, ( 12345, 34512 ) es un par reciclado ya que puedes obtener 34512 moviendo 345 desde el final de 12345 al principio. Observar que n y m deben tener el mismo número de dígitos (excluyendo ceros a la izquierda) para poder ser un par reciclado.
Dados los enteros A y B con el mismo número de dígitos, cuántos pares reciclados distintos ( n,m ) hay con A ? n < m ? B?
Entrada
La primer línea de la entrada nos dá el número de casos de prueba, T. Luego vienen T casos de prueba. Cada caso de prueba consiste de una línea simple que contiene los enteros A y B.
Salida
Para cada caso de prueba, muestre una línea conteniendo ”Case #x: y”, donde x es el número del caso de prueba (comenzando desde 1), e y es el número de pares reciclados (n, m) con A ? n < m ? B.
Límites
1 ? T ? 50.
A y B tienen el mismo número de dígitos.
Conjunto de datos pequeño:
1 <= A <= B <= 1000.
Conjunto de datos grande:
1 <= A <= B <= 2000000.
Ejemplo
Entrada:
4
1 9
10 40
100 500
1111 2222
Salida:
Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287
Problema B: Bailando con los empleados de Google
abr2
Problema
Ud. está mirando un show donde los Googlers (empleados de Google) bailan, y luego una terna de jueces les asigna una terna de puntajes. Cada terna de puntajes consiste de tres puntajes enteros de 0 a 10 incluídos. Los jueces tienen estándares similares, así que sorprende si una terna de puntajes tiene 2 puntajes con una diferencia de 2. Ninguna terna de puntajes contiene puntajes con una diferencia mayor que 2.
For ejemplo: (8, 8, 8 ) y (7, 8, 7 ) no llaman la atención, pero (6, 7, 8 ) y (6, 8, 8 ) llaman la atención. (7, 6, 9 ) nunca sucederá.
El total de puntos para un Googler es la suma de los tres puntajes en la terna de puntos de dicho Googler. El mejor resultado para un Googler es el máximo de los tres puntajes en su terna de puntos. Dado el total de puntos para cada Googler, y el número de ternas de puntajes que llaman la atención, cuál es el número máximo de Googlers que pueden tener como mejor resultado al menos p?
Por ejemplo, suponga que hay 6 Googlers, y ellos tienen los siguientes puntajes totales: 29, 20, 8, 18, 18, 21.
Ud. recuerda que había 2 ternas de puntajes que llamaban la atención, y quiere saber cuantos Googlers podrían tener un mejor resultado de 8 o superior.
Con esos puntos totales, y sabiendo que 2 de las 3 ternas llamaban la atención, las ternas de puntajes podrían haber sido:
10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*)
Los casos marcados con un (*) son los casos que llaman la atención. Esto nos dá 3 Googlers que tienen al menos un puntaje de 8 o superior. No hay ninguna serie de ternas de puntajes que podrían darnos un número mayor que 3, así que la respuesta es 3.
Entrada
La primer línea de la entrada nos dá el número de casos de prueba, T. Luego vienen T casos. Cada caso de prueba consiste de una línea simple con enteros separados por espacios simples. El primer entero será N, el número de Googlers, y el segundo entero será S, el número de ternas de puntajes que llaman la atención. El tercer entero será p, como se describe arriba. Luego vendrán N enteros ti: el puntaje total de los Googlers.
Salida
Para cada caso de prueba, muestre una línea conteniendo “Case #x: y”, donde x es el número del caso de prueba (comenzando desde 1) e y es el número máximo de Googlers que podrían tener un mejor resultado mayor o igual que p.
Límites:
1 <= T <= 100.
0 <= S <= N.
0 <= p <= 10.
0 <= ti <= 30.
Habrá al menos S puntajes totales entre 2 y 28 incluídos.
Conjunto de datos pequeño:
1 <= N <= 3.
Conjunto de datos grande:
1 <= N <= 100.
Ejemplo:
Entrada
4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21
Salida:
Case #1: 3
Case #2: 2
Case #3: 1
Case #4: 3
Problema A – Qualification Round Google Code Jam 2012
abr0
Problema A: Hablando lenguas diferentes
Aquí en Google hemos llegado al mejor lenguaje posible, llamado Googlerese. Para traducir texto a Googlerese, tomamos cualquier mensaje y reemplazamos cada letra en lenguaje Inglés con otra letra en lenguaje Inglés. Este mapeo es “uno a uno y sobre”, lo que significa que la misma letra de entrada será siempre reemplazada con la misma letra de salida, y diferentes letras de entrada serán siempre reemplazadas con diferentes letras de salida. Una letra puede ser reemplazada por sí misma. Los espacios quedan como están.
Por ejemplo (y aquí hay una pista!), nuestro increíble algoritmo de traducción incluye los siguientes tres mapeos: ‘a’ -> ‘y’, ‘o’ -> ‘e’, y ‘z’ -> ‘q’. Esto significa que”a zoo” se convertirá en “y qee”.
Googlerese está basado en el mejor mapeo posible de reemplazo, y nunca lo cambiaremos. Siempre será el mismo. En cada caso de prueba. No te diremos el resto de nuestro mapeo porque eso haría el problema demasiado fácil, pero aquí hay algunos ejemplos que pueden ser de ayuda.
Dado un texto en Googlereese, puedes traducirlo de vuelta a texto normal?
Resolviendo el problema
Generalmente, los problemas de la Google Code Jam tienen una “Small Input” y una “Large Input”. Este problema tiene sólo una Small Input. Si la resuelves, el problema está resuelto.
Entrada
La primera línea de la entrada tiene el número de casos de prueba, T. Luego vienen T casos de prueba, uno por línea.
Cada línea consiste de un string G en Googlerese, hecho de una o más palabras conteniendo letras en ‘a’ – ‘z’. Habrá exactamente un espacio (‘ ‘) entre palabras consecutivas y no hay espacios al comienzo o al final de cualquier línea.
Salida
Para cada caso de prueba, imprima una línea conteniendo “Case #X: S” donde X es el número del caso de prueba y S es el string que se convierte en G en Googlerese.
Límites
1 ? T ? 30.
G contiene como máximo 100 caracteres.
El texto no se garantiza que sea válido en Inglés.
Ejemplo:
Input
3
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv
Output
Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up
La ronda de calificacion de la Google Code Jam ya comenzo!
abr0
Acá va una traducción a castellano (de Argentina), del mail que envió el Google Code Jam al comienzo de la competencia:
La ronda de calificación de la Google Code Jam dura 25 horas, y se necesitan al menos 20 puntos para superarla. Se supone que 25 horas son suficientes para resolver los problemas, pero igualmente hay que dedicarle algunas horas para trabajar sobre ellos.
Se puede usar cualquier lenguaje de programación para competir, con unas pocas excepciones que se encuentran en el FAQ. En ediciones pasadas, algunos de los participantes han usado lenguajes de programación diferentes para resolver cada problema y tipo de entrada. Aunque Google lo encuentra interesante, no se ganan puntos extras por resolver los problemas en diferentes lenguajes de programación.
Recordar que cuando se envía una solución a un conjunto de entrada/salida Large, Google no le dirá si es correcta hasta el final de la competencia. Así que aunque parezca que ya ha conseguido 20 puntos, lo mejor es considerar resolver otro problema.
Ud. debe ir a http://csta eode.google.com/codejam al comienzo o durante la competencia, para poder competir. Por cualquier problema o pregunta, se puede preguntar usando el link “Ask a Question” o enviando un email a codejam@google.com.
Buena suerte y nos vemos en la tabla de puntajes!
Saludos
-The Code Jam Team
Semana 5
abr0
Hola a todos:
Martes 10/4: Presentación 4 (Complejidad) en la clase de teoría y presentación TP 1.
Miércoles 11/4: Lab. 5 (opcional), grupo ACM de Programación Competitiva.
Jueves 12/4: NO HAY CLASES
Viernes 13/4: Último día entrega solución problema a resolver.
Viernes 13/4 – 20 hs: Competencia Google Code Jam.
Los esperamos!
Semana 4
abr0
Hola a todos:
Martes 3/4: 2da. clase de STL.
Miércoles 4/4: último día para entrega actividad de traducción.
Jueves feriado, Felices Pascuas! (se viene la presentación del TP1)
A no relajarse!!!
Semana 3
mar0
Hola a todos:
Martes 27/3: Presentación 3 (STL) en la clase de teoría.
Miércoles 28/3: Lab. 5 (opcional), grupo ACM de Programación Competitiva.
Jueves 29/3: Guía 3 de práctica y entrega problema 1 individual.
No falten!
Semana 2
mar0
Hola a todos:
Martes 20/3: Presentación 2 en clase de teoría y se reparte la tarea de traducción.
Jueves 22/3: Guía de Práctica N°2 en clase de práctica.
Los esperamos!!!
Bienvenidos a Competitiva 2012
feb0
Hola!
Bienvenidos al sitio de Programación Competitiva, materia electiva del área Programación, 3er. año, 1er. cuatrimestre, de la carrera de Ingenieria en Sistemas de Información.
En este sitio encontrarás toda la información y los recursos que necesitás para el cursado de Programación Competitiva.
Esperamos que sea una experiencia enriquecedora para todos (alumnos y docentes), y que logremos cumplir con los objetivos de la asignatura.
Saludos
La Cátedra