Programacion, ACM ICPC, UVa Online Judge

Entradas etiquetadas como ‘UVa Online Judge’

UVa Online Judge – 12363 – Hedge Mazes

El link del problema es el siguiente:
12363 – Hedge Mazes

El problema es de Grafos.
En el problema, nos dan la descripción de un grafo, que son las conexiones entre sus nodos y un numero Q de consultas. Cada consulta esta compuesta de 2 números u,v que representan un nodo origen y un nodo destino y para cada una de las consultas, hay que responder de manera eficiente si solo existe un camino entre esos 2 nodos.
Si es que llega a existir un solo camino entre esos nodos, imprimimos una Y, en caso contrario, imprimimos una N.

Cuando digo de manera eficiente, me refiero a que las consultas se deben de hacer lo mas rápido posible.

La solución consiste en hacer uso de los puentes del grafo.
Un puente es una arista en el grafo que si es removida, el grafo se desconecta.
Si nos ponemos a pensar en este hecho, eso quiere decir que al pasar por el puente, solo existe ese camino único para ir de un nodo A a un nodo B.

Por lo tanto, tenemos que si dos nodos están conectados solamente por puentes, quiere decir que la ruta es única.
Así que la solución, es, una vez generados los puentes, podemos usar conjuntos disjuntos para obtener cuales elementos están en el mismo conjunto, y si están en el mismo conjunto, es que existe solo 1 camino entre ellos.

Código en C++

UVa Online Judge – 10880 – Colin and Ryan

El link del problema es el siguiente:
10880 – Colin and Ryan

El problema es de Teoría de números.
Lo que el problema dice es que tenemos una cantidad de galletas C y nos sobraron R galletas.
En la fiesta había G invitados y cada uno se comió Q galletas.
Y básicamente conociendo solamente cuantas galletas había y cuantas sobraron, hay que decir cuantas galletas se comió cada invitado.
El numero de invitados máximo puede ser C para que cada uno se comiera una galleta y mínimo 1, que implica que el único invitado se comió todas.
Para cada caso de entrada nosotros tenemos que decir todas las posibles soluciones.

Para el problema, tenemos 2 casos base.
Si la cantidad de galletas es igual al numero de galletas que sobraron, por lo tanto, cada invitado se comió 0 galletas.
Cuando el numero de galletas no es igual al numero de galletas que sobraron se puede hacer el siguiente razonamiento:

C = G*Q + R
C-R = G*Q
Q = C-R / G

Por lo tanto, como se puede observar, G es un divisor de C-R.
Así que la solución consiste en encontrar a los divisores de C-R.
Una vez calculados los divisores chacemos cuales de todos cumplen con la condición:

C%divisor[i] == R

Si la condición se cumple, entonces es una posible solución.
Hay que tener en cuenta que en algunos casos no hay solución.

Código en C++

UVa Online Judge – 11824 – A Minimum Land Price

El link del problema es el siguiente:
11824 – A Minimum Land Price

El problema es de tipo Greedy, y requiere un ordenamiento.
En cada caso, nosotros tenemos un conjunto de números, y hay que hacer que la sumatoria siguiente se minimice.
Para minimizarla, hay que leer todos los datos y ordenarlos de mayor a menor.
Esto se debe a que al ir elevando a la potencia i, el numero crece mas rápidamente  entonces, es conveniente elevar a los números mas grandes a una potencia pequeña.
Si en medio del proceso, el numero excede 5,000,000, imprimir “Too expensive”, de lo contrario, imprimir el valor obtenido.

Código en C++

UVa Online Judge – 11039 – Building designing

El link del problema es el siguiente:
11039 – Building designing

El problema es de tipo Greedy.
Nos dicen que tenemos que formar el edificio mas alto que se pueda, con la condición que siempre hay que ir alternando los colores y que el piso de abajo tiene que ser mayor al piso que se coloca arriba.
Un color es representado como positivo y otro como negativo y el tamaño de cada piso es el valor absoluto del numero.

Una solución es guardar los valores en 2 arreglos, uno para los números positivos y otro para los números negativos y ordenarlos.
Una vez ordenados, tomamos el elemento mas grande de los 2, ya sea o positivo y negativo.
Y por ultimo, hay que ir alternando, ya que si el piso de abajo es positivo, el siguiente tiene que ser negativo, así que hay que encontrar el numero mas pequeño que le sigue al numero del piso anterior.
Este proceso se hace igual al revés, si el ultimo es negativo, hay que tomar el siguiente positivo y buscar el siguiente numero menor al valor del piso anterior.
El resultado es el numero máximo de pisos que pudimos encadenar.

Código en C++

UVa Online Judge – 11703 – sqrt log sin

El link del problema es el siguiente:
11703 – sqrt log sin

El problema es de tipo Ad Hoc.
En el problema nos dan una formula, que tiene un valor inicial X0=1.
Lo único que hay que realizar es memorización y realizar las consultas en la posición dada.

Código en C++

UVa Online Judge – 11621 – Small Factors

El link del problema es el siguiente:
11621 – Small Factors

El problema es de tipo Ad Hoc.
En el problema, nos dan un conjunto que sus elementos están compuestos solo por números cuya descomposición prima sea 2 o 3.
La forma mas sencilla de resolverlo es generar todos los posibles números. Esto se puede hacer con ciclos.
Una vez generados todos los números los ordenamos y para poder buscar la respuesta rápidamente, hay que utilizar búsqueda binaria.
Pero debido a que el problema nos pide el siguiente mayor o igual, es recomendable restarle 1 al numero que nos dan en la entrada y utilizar upper_bound para realizar la busqueda.

Codigo en C++

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++

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++

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.