UVa 839, Not so Mobile, describe un móvil con una línea
Wl Dl Wr Dr por barra: pesos y distancias al punto de donde cuelga. Un peso
0 dice que de ese extremo cuelga otro móvil, descrito en las líneas
siguientes. El enunciado está en
https://vjudge.net/problem/UVA-839.
La barra está en equilibrio si Wl·Dl = Wr·Dr y lo que cuelga de ella también
lo está. Una llamada a movil() lee una línea y devuelve el peso
del submóvil y si está en equilibrio.
1. La entrada
Se acepta el formato del juez, con el número de
casos y la línea en blanco, o solo las líneas de cuatro enteros. El
móvil al azar tiene hasta cuatro niveles de barras y a veces no está
en equilibrio.
2. Avance llamada por llamada
la línea de la llamada actual
devolvió sí
devolvió no
submóvil sin leer, o línea leída cuando ya se sabía que la respuesta es NO
Pila de llamadas, el tope arriba
(profundidad 0)
Un submóvil ya
devolvió no, así que la respuesta del caso es NO. La función lee esta línea
de todas formas: si se saltara el resto del submóvil, la siguiente lectura
tomaría una línea que no le corresponde.
peso devuelto:¿en equilibrio?
línea
Wl Dl Wr Dr
Wl·Dl
Wr·Dr
peso devuelto
equilibrio
Lo que cuesta
Hubo llamadas para
líneas, y pasos entre
lecturas y retornos. Cada llamada lee una línea y nada más: una llamada por
barra del móvil. Fuera de sus llamadas recursivas, una llamada hace un
trabajo constante, una lectura, dos productos y una suma, así que el costo
es T(L) = c·L para un móvil de L líneas, Θ(L). Ese es también el mínimo,
porque el juez obliga a leer toda la entrada.
El parámetro no es un número: es el submóvil, es
decir, el bloque de líneas que lo describe, que la llamada consume de la
entrada. La propiedad que hace funcionar la recursión es que un
submóvil pesa lo mismo que la suma de sus objetos y está en equilibrio si
lo están sus dos lados y Wl·Dl = Wr·Dr con esos pesos; por eso la llamada
devuelve dos cosas. La trampa está en la entrada: el submóvil ocupa
las líneas siguientes, y una función que devuelve NO apenas lo detecta deja
líneas sin leer que el siguiente caso toma como suyas. Además hay una línea
en blanco antes de cada caso y la salida separa dos casos con una línea en
blanco, sin una al final: leer_linea() salta las líneas
vacías.