Planificando el acueducto
Tarraco (hoy Tarragona) fue una de las principales ciudades de la Hispania romana. El conjunto arqueológico que ha llegado a nuestros días es hoy Patromonio de la Humanidad según la Unesco.
Para conseguir un suministro adecuado de agua, los romanos construyeron, en el siglo I a.C., un acueducto de 25 km que la traía desde el río Francolí. La construcción no fue sencilla. Tuvieron que salvar un gran desnivel, cosa que consiguieron gracias al que hoy se conoce como Puente del Diablo o acueducto de Ferreres, una arquería de 217 metros de largo y 27 de altura máxima. Para garantizar que el agua fluyera de forma natural, crearon en él un desnivel de 40 centímetros, lo que permitía que fuese la gravedad la que se encargara del transporte.
En los acueductos es importante que el origen, de donde se recoge el agua, esté más alto que el destino, hacia donde va, siguiendo una pendiente que no puede ser muy pronunciada si la longitud del acueducto es larga. La precisión de los ingenieros romanos para conseguirlo es digna de elogio.
Ben Ibidi Binchi, un arqueólogo experimental, está intentando imitarles pero a lo más que llega es a una pendiente en la que desciende un centímetro por metro. Quiere crear un acueducto entre dos lugares y sabe la altura del terreno en cada metro del camino. Ahora necesita saber la altura de la construcción que tendrá que hacer en cada uno de esos puntos de manera que el acueducto tenga como mínimo siempre la altura del terreno y de un punto al siguiente la altura descienda exactamente un centímetro.
Entrada
Cada caso de prueba comienza con un número 2 ≤ n ≤ 1.000 con la distancia, en metros, entre el punto origen y destino del acueducto que queremos construir.
A continuación aparecen n números, menores o iguales que 109. Cada uno indica la altura en un punto del camino, medida en centímetros. El primer valor hace referencia a la altura en el origen (donde está el agua) y el último la altura en el destino. Entre dos valores la distancia es de un metro.
La entrada termina con un 0.
Salida
Por cada caso de prueba el programa escribirá la altura a la que hay que colocar el canal con respecto al suelo en cada uno de los puntos del camino de modo que el canal siempre esté por encima del terreno y descienda un centímetro de un punto al siguiente.
Se permite que el canal de agua esté directamente sobre el suelo (altura 0), elevar el agua en el origen o dejarla alta en el destino si eso permite que, una vez canalizada, el agua fluya por gravedad descendiendo un centímetro por metro.
Entrada de ejemplo
3 10 9 8 4 100 90 80 90 4 100 90 110 100 4 82 70 60 81 0
Salida de ejemplo
0 0 0 0 9 18 7 12 21 0 9 2 13 22 0