Programacion, ACM ICPC, UVa Online Judge

Archivo para septiembre, 2012

UVa Online Judge – 10268 – 498-bis

El link del problema es el siguiente:
10268 – 498-bis

El problema es de tipo Ad hoc y requiere conocimientos básicos de calculo.
Lo que nos dan es la descripcion de un polinomio y hay que calcular su derivada y evaluar la derivada con un valor “x”.
El calculo de la derivada viene explicado en la descripción del problema y solo hay que recordar que tiene 1 grado menos que el polinomio original.

Codigo en C++

Anuncios

UVa Online Judge – 1203 – Argus

El link del problema es el siguiente:
1203 – Argus

El problema es Ad Hoc.
Lo que nos dan es un conjunto de tareas, que cada lapso de tiempo se repiten nuevamente.
Conociendo el identificador de la tarea (que es único), hay que decir en que orden se ejecutarían las siguientes “k” tareas.
Si hay empate en el momento en el que se ejecutan las tareas, entonces se desempata por el identificador mas bajo.

Para esto, lo mas sencillo es utilizar una cola de prioridad y utilizando parejas(pair<int,int>).
Podemos modificar la cola de prioridad o meter los valores pero multiplicados por menos uno.
Al sacar el elemento de la cola, imprimimos el identificador y lo introducimos nuevamente a la cola aumentando el tiempo.
Repetir el proceso “k” veces para obtener la solución.

Codigo en C++

UVa Online Judge – 893 – Y3K Problem

El link del problema es el siguiente:
893 – Y3K Problem

El problema es de tipo Ad hoc y se puede resolver fácilmente con Java utilizando la clase Calendar.
El problema nos da una fecha y una cantidad de días después de la fecha dada, y hay que calcular la fecha resultante.

Como dije se puede hacer muy fácil en Java utilizando Calendar.
Al leer, primero es el numero de días que avanzaremos, y después la fecha.
Con el método “set” de Calendar colocamos la fecha actual y utilizando el método “add” con el valor DAY_OF_MONTH, agregamos la cantidad de días que el caso especifico.

La parte importante seria esta:
Calendar c;
c.set(year,month-1,day);
c.add(DAY_OF_MONTH,plus);

E imprimir en el formato indicado.

Codigo en Java

UVa Online Judge – 11371 – Number Theory for Newbies

El link del problema es el siguiente:
11371 – Number Theory for Newbies

El problema es de tipo Ad hoc.
Lo que nos dan es un numero n, y lo que nos piden es encontrar una forma de re ordenar el numero de tal manera que su diferencia sea máxima y la diferencia sea múltiplo de 9.
El numero máximo que nos dan tiene a lo mas 10 dígitos (2000000000), por lo tanto, podemos sacar todas las permutaciónes utilizando next_permutation.
Al ir obteniendo las permutaciónes podemos ir obteniendo modulo 9 de cada numero, e ir guardando el máximo y el mínimo de entre los números que tengan el mismo modulo.
La explicación es que si dos números tienen el mismo modulo los podemos representar de la forma
A = 9*q1 + r
B = 9*q2 + r

Donde q es un entero.
y cuando hagamos la diferencia entre ellos tendremos
A-B = 9*q1 +r – 9*q2 -r = 9*q1 – 9*q2 = 9*(q1 – q2)

Por lo tanto, si tienen el mismo residuo, la diferencia es un múltiplo de 9.
Uva vez realizas todas las permutaciónes, elegimos entre los que almacenamos el que nos maximice la diferencia.
Solo hay que tener en cuenta algo al ir generando las permutaciónes, y es que hay que cuidar que no tenga ceros a la izquierda, ya que si los tiene, no se tiene que considerar.

Codigo en C++

UVa Online Judge – 11988 – Broken Keyboard (a.k.a. Beiju Text)

El link del problema es el siguiente:
11988 – Broken Keyboard (a.k.a. Beiju Text)

El problema es Ad Hoc.
Lo que nos dicen es que cada vez que encontremos un corchete que abre, tenemos que posicionarnos al principio de la cadena y cuando encontremos un corchete que cierra, hay que posicionarse al final de la cadena.
Este problema se pueden utilizar listas, y simplemente al encontrar un corchete que abre posicionar el iterador al principio de la lista y cuando encontramos un corchete que cierra nos posicionamos al final de la lista, y para cualquier otro caracter que no sea corchete, insertamos en la lista.

Código en C++