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 – 1225 – Digit Counting

El link del problema es el siguiente:
1225 – Digit Counting

El problema es de tipo Ad Hoc.
El problema nos pide que dado un numero N (1<=N<=10000) digamos cuantos dígitos hay [0-9] entre 1 y ese N.
Dado que el N, no es demasiado grande, se puede memorizar.
La forma mas sencilla es utilizar un vector de vectores.

vector<vector<int> > sol;

Y como nos podremos dar cuenta la solución para el numero N esta dado por lo dígitos que forman a N mas la respuesta de N-1.

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 – 12364 – In Braille

El link del problema es el siguiente:
12364 – In Braille

El problema es de tipo Ad Hoc.
Lo que nos pide el problema es convertir de braile a un numero y de numero a braile, dependiendo de la entrada que nos proporcionen.
Una forma sencilla es utilizar mapas de vectores que tengan asociado un numero:

map<vector<string>,int> braile; //Para pasar de braile a numero
Y para pasar de numero a braile, se puede utilizar un vector de vectores de string:
vector<vector<string> > entero; //Para pasar de entero a braile
Donde el indice es el que nos indica el numero y el contenido es la forma en braile asociada.

Codigo en C++

UVa Online Judge – 11678 – Cards’ Exchange

El link del problema es el siguiente:
11678 – Cards’ Exchange

En el problema nos describen que tenemos 2 conjuntos de cartas, y queremos ver el máximo numero de intercambios que se pueden realizar.
El problema es de tipo Ad Hoc.

La forma en la que yo aborde el problema es utilizando conjuntos.
Tenemos que cada conjunto de cartas puede tener repetidos, así que los eliminamos y la forma mas sencilla es utilizando un Set.
Una vez tenemos los dos conjuntos ya sin cartas repetidas, podemos obtener que cartas pertenecen a los dos conjuntos, esto se veria como una operacion de Interseccion en conjuntos.
Y por ultimo, una vez conocido el numero de cartas que comparten los dos conjuntos la solución esta dado por el mínimo de las diferencias del numero de cartas que tiene cada jugador menos el numero de cartas que comparten en común.

Ejemplo:

1 1 2 3 5 7 8 8 9 15  //j1
2 2 2 3 4 6 10 11 11  //j2

Set del J1
1 2 3 5 7 8 9 15   tamaño = 8
Set del J2
2 3 4 6 10 11    tamaño = 6
Cartas en común (union)
2 3

Como se nota, el numero de cartas en común son 2, por lo tanto a lo mas pueden intercambiar (8-2) o (6-2), y de ahí hay que tomar el mínimo, en este caso 4.

 

Codigo en C++