Dandy Wagon
Aunque hoy nos parezca impensable, durante las primeras décadas del siglo XIX los trenes eran movidos gracias a caballos que tiraban de los vagones. El cálculo aproximado era un caballo por cada cuatro vagones.
El Ferrocarril de Stockton y Darlington inaugurado en 1825 fue el primero abierto al público en utilizar locomotoras de vapor pero la fiabilidad que tenían hizo que no se abandonara por completo el uso de caballos, habitual en otras rutas. Eso sí, la fiabilidad de los caballos frente a las locomotoras tenía su contrapartida: los caballos se cansaban y las locomotoras no. Y con el éxito que tuvo la línea, a los animales se les exigía cada vez más viajes y con más carga.
Para mejorar su rendimiento, George Stephenson, un ingeniero inglés apodado "el padre de los ferrocarriles" al que, entre otras cosas, debemos el ancho de vía estándar de 1435 milímetros, inventó los llamados dandy wagons (también llamados cart wagons): unos vagones utilizados para transportar a los propios caballos de tiro cuando el tren atravesaba una zona con cuestas abajo. Durante esos tramos no solo los caballos podían descansar mientras el convoy se movía por efecto de la gravedad, sino que la velocidad que podía alcanzar éste no estaba limitada por la de los caballos pudiendo así ir más rápido.
Como es lógico, la efectividad de estos vagones dependía de la longitud del trayecto en el que los caballos podían descansar antes de tener que volver a ser enganchados en la cabecera para retomar su trabajo de tiro.
Para averiguar, dada una ruta, en qué partes se puede hacer uso de los dandy wagons, se divide el trayecto en secciones y se calcula para cada sección cuánto se incrementa (o decrementa) la velocidad del tren si se mueve por efecto de la gravedad o de la inercia. Después hay que analizar esos datos para encontrar los tramos contiguos más grandes en los que el tren puede avanzar por efecto de la gravedad.
Entrada
La entrada está compuesta por distintos casos de prueba, cada uno ocupando dos líneas.
La primera línea del caso contiene un número N con la cantidad de secciones en las que se ha dividido el trayecto (hasta 300.000). La segunda línea tiene N números con el incremento de velocidad del tren si se deja libre durante la sección completa. Un valor positivo significa que al final del tramo la velocidad habrá aumentado esa cantidad debido a una pendiente descendiente. Un valor negativo indica, por el contrario, que la velocidad disminuye en esa cantidad (por una cuesta arriba). Un 0 indica un terreno plano en el que la velocidad no cambia.
Tras el último caso de prueba viene una línea con un cero que no debe procesarse.
Salida
Por cada caso de prueba se escribirá una línea con el número máximo de secciones consecutivas en las que los caballos de tiro pueden descansar.
Para que el tren recorra un tramo sin ayuda de los caballos, éstos deben estar subidos al dandy wagon y el tren deberá alcanzar el punto final de la sección aprovechando la suma de la velocidad que tuviera al empezar el tramo y la que haya ganado en él. Esa suma no podrá hacerse negativa.
Ten en cuenta que cuando los caballos tiran del tren éste no gana ni pierde velocidad por la pendiente del terreno y se desplaza a la velocidad marcada por los animales. Además, los caballos solo pueden engancharse al tren (para empezar a tirar) o desengancharse (para subirse al dandy wagon a descansar) al principio de una sección. Si los caballos no están tirando del tren y se sabe que no superará el tramo siguiente con la inercia, habrá que detenerlo completamente al inicio de esa sección para enganchar los caballos. Del mismo modo, si al principio de una sección se decide subir a los caballos al dandy wagom el tren comenzará esa sección completamente parado y su avance estará en manos de la pendiente descendiente del tramo.
Entrada de ejemplo
4 1 2 3 0 4 -3 -2 -1 0 4 3 3 -4 -4 7 1 -1 0 2 -2 3 -3 0
Salida de ejemplo
4 0 3 4
Notas
El primer caso de prueba del ejemplo es completamente cuesta abajo (en todas las secciones el tren gana velocidad) salvo el último al que se llega con inercia, por lo que los caballos pueden usar su dandy wagon durante todo el trayecto. El segundo caso es prácticamente el inverso y los caballos deben tirar del tren todo el tiempo.
En el tercer caso de prueba el tren coge inercia durante las dos primeras secciones lo que le permite superar la tercera sección a pesar de ser cuesta arriba, pero no la cuarta que tendrá que ser superada gracias a los caballos.
En el último caso las secciones cuesta abajo proporcionan la inercia justa para superar las secciones cuesta arriba. Para la sección plana (0) debe utilizarse la fuerza motriz, pues se llega a ella sin inercia.