Llevaba tiempo sin escribir en el blog gracias al comienzo de clases. Hoy quiero escribir un tutorial acerca de los problemas usados en el maratón USB10_C1 (el primer calentamiento para los maratones ACM-ICPC 2010 de la Universidad Simón Bolívar) el cual fué llevado a cabo en SPOJ.
TEST:
Éste fué el problema más sencillo del maratón, fué resuelto por todas las personas que participaron en el concurso.
La solución es muy simple, sólo hay que leer enteros hasta que aparezca el número 42 en la entrada.
Aquí les coloco una solución en C++ del problema:
# include <iostream>
using namespace std;
int main()
{
int n;
while(cin >> n && n != 42) {
cout << n << endl;
}
return 0;
}
ADDREV:
Éste es otro problema que fué resuelto por todas las personas que participaron en el maratón. Sin embargo, es un poco más difícil que TEST ya que requiere de más implementación. Aquí les dejo la solución del problema, sin embargo, no colocaré código para que puedan practicar haciéndolo :-).
Leer cada par de enteros. Revertir cada uno. Sumarlos usando, por ejemplo, el método de adición que aprendimos en primaria. Revertir el resultado. Eliminar los 0s al principio del resultado.
Tenga en mente algunos casos especiales que pueden surgir en los pasos dichos anteriormente, como los siguientes:
1.- Se acabaron los dígitos de un número y hay un acarreo de una operación pasada.
2.- Al eliminar los 0s del resultado tenga en mente que tiene que quedar un dígitos al menos.
Nota: Los ejemplos no son ejemplos de lo que recibirá el programa y lo que debería arrojar, son sólo ejemplos para mostrar algunos casos intermedios.
CISTFILL:
Este problema ya no resulta ser tan fácil como los anteriores. La solución a este problema puede ser obtenida usando Búsqueda, ahora veamos que tipo de búsqueda hay que realizar. Tenemos que buscar una altura a la cual se puedan llenar las cisternas con cierta cantidad de líquido. Lo primero que se nos puede ocurrir es buscar sobre todas las alturas posibles, pero veamos cuantas alturas tenemos que verificar. El punto más alto de una cisterna es su altura base + su propia altura, y si vemos las restricciones tenemos que la altura base puede ser a lo sumo 10^6 y que su propia altura puede ser 40000 (se dice que 1 <= h*w*d <= 40000, si w = d = 1 entonces 1 <= h <= 40000), es decir, que en total la máxima altura que se puede alcanzar es 1040000, pero también tenemos que tener dos dígitos de precisión, por lo que para cada altura tenemos que revisar 100 números más (desde *,00 hasta *,99), lo cual hace un total de 104000000 alturas y eso es aproximadamente 10^8 alturas. Anteriormente hablamos de revisar alturas, ¿a qué me refieron con ello? Me refiero con ello a que tenemos que ver que volumen de líquido hay en las cisternas a cierta altura, es decir, que para cierta altura tenemos que ver cuales cisternas no están por encima de esa altura y calcular el volumen de líquido que hay en cada una de ellas y sumarlas para obtener la cantidad total de líquido en el sistema; a esta última operación la llamaremos f (altura, cisternas). Ahora, por cada altura (aproximadamente 10^8) tenemos que revisar todas las cisternas (1 <= n <= 50000) para ver cuáles no están por encima de dicha altura. Esas son muchísimas operaciones que tenemos que hacer. Por lo tanto, si escogemos realizar búsqueda lineal seguramente obtendremos Time Limit Exceeded.
Hasta ahora nuestros esfuerzos se han vistos frustrados, pero, si observan detalladamente la función f (altura, cisternas) pueden ver que la función es monótona no decreciente, es decir, f (altura1, cisternas) <= f (altura2, cisternas) con altura1 <= altura2. Eso ocurre porque en altura2 tenemos las cisternas de altura1 más las que aparezcan desde altura1 hasta altura2 (que pueden ser ninguna), por lo tanto, tendremos al menos la misma cantidad de volumen de líquido que en altura1. Pero, ¿qué hago con saber que la función es no decreciente? Pues elemental mi querido Watson, usar búsqueda binaria con respecto a la altura.
function f(altura, cisternas)
Retorna el volumen de agua en las cisternas a esa altura
funcion busquedaBinaria(volumen, cisternas)
ini <- 0
fin <- 1040001 # Máximo de alturas que tenemos que revisar + 1
Mientras ini + 1 != fin # Mientras haya un intervalo [a, b) válido
med <- (ini + fin) / 2 # Los cálculos se hacen con reales porque la altura tiene que tener dos dígitos decimales.
si f(med) > volumen # El volumen excede lo que buscamos, tenemos que bajar la altura
fin <- med
sino # Tenemos que subir la altura
ini <- med
retornar ini
Ahora este algoritmo tiene complejidad O(N * lg (104000001)) con N el número de cisternas, el cual es suficiente para obtener un accepted en el problema. Ah ya se me olvidaba, para revisar si hay un overflow, solo calculen la cantidad total de líquido que pueden contener todas las cisternas y revisen si es mayor a la cantidad dada.
ACT:
Este problema me trajo sorpresas en el maratón, pues pensé que más gente lo resolvería. Algunas personas intentaron simular el problema, lo cual no está mal, pero toma un poco de tiempo. Sin embargo, hay observaciones muy interesantes acerca de este problema:
- La secuencia de caracteres representa un juego válido, es decir, un juego completo con un ganador o dicho de otra manera, lo contrario a un juego que no ha terminado o un juego que fué continuado a pesar de tener un ganador.
- Un jugador que anota un punto puede ganar un game, un set o un match, de acuerdo a sus cantidades de games y sets acumulados, es decir, que cada vez que un jugador anota un punto hay que verificar si ganó un game, set o match.
# include <iostream>
# include <string>
using namespace std;
int main()
{
int t, n;
string juego;
cin >> t;
while(t--) {
cin >> n >> juego;
cout << *(juego.end() - 1) << endl; // o juego[juego.size() - 1], como les parezca mejor.
}
return 0;
}
Recuerde que juegos.end() devuelve un apuntador al final de la cadena (a la derecha del último caracter). Al escribir juegos.end() - 1, obtenemos un apuntador al último caracter de la cadena, y usando *(juegos.end() - 1) podemos leer el caracter al cual se estaba apuntando.
TOANDFRO:
Éste fué otro problema fácil del maratón, pues había que hacer exactamente lo que se decía en el enunciado. Se recibía una cadena y el número de columnas que se iban a utilizar. Se comienza a transcribir la cadena en una matriz de c columnas (con c dado en la entrada). Se comienza en la fila 0 de la matriz y se procede de la siguiente manera hasta que no hayan mas caracteres por analizar: si la fila es par se copian los siguientes c caracteres de la cadena de izquierda a derecha, si la fila es impar se copian de derecha a izquierda, luego vamos a la siguiente fila.
Aquí coloco el enlace a la siguiente parte del tutorial: Tutorial USB_C1 Parte II
Saludos a todos.
