Los paseos de María en bicicleta
Traducción: Angel Alvarez (DIT, UPM)
aalvarez@dit.upm.es
Introducción
Este es el Problema B, segundo de los ocho que fueron planteados a los cincuenta equipos de todo el mundo que participaron en la fase final del Concurso ACM de Programación Internacional para Estudiantes 1997. El primero de ellos fue publicado en el número anterior de Novática y los restantes se irán publicando en próximos números. Como ya decíamos en el número 127, recomendamos a los docentes de la asignatura de Programación que intenten resolverlos con sus alumnos y a los programadores de profesión o afición que los utilicen para revisar sus conocimientos y habilidades. Creen sus propios datos de prueba y pónganse manos a la obra.
Problema B: Los paseos de María en bicicleta
A María le gusta pasear en bicicleta, pero como la bella ciudad en la que vive ha crecido bastante últimamente, a menudo utiliza el autobús municipal para hacer parte de sus recorridos. María tiene una bicicleta plegable con la que monta en el autobús y hace la primera parte de sus viajes. Cuando el autobús llega a una parte agradable de la ciudad, María se baja y continúa en bicicleta siguiendo la ruta del autobús. Y sigue así hasta que, bien llega a su destino, o bien la zona se vuelve desagradable para andar en bicicleta, en cuyo caso monta de nuevo en el autobús con la bicicleta para acabar su viaje.
A lo largo de varios años de hacer lo mismo, María ha acumulado la suficiente experiencia como para poder evaluar los distintos tramos de cada ruta de autobús en base a su "agradabilidad". Los valores positivos indican tramos que le gustan a María para andar en bicicleta y los negativos, por el contrario, aquéllos que no le gustan. María tiene la intención de, en cada ruta, decidir cuándo dejar el autobús y empezar a andar en bicicleta, así como cuándo montarse de nuevo en el autobús para acabar el viaje, de tal manera que la suma de los valores de agradabilidad de los tramos (consecutivos) recorridos en bicicleta, sea máxima. Esto significa que, algunas veces, estará dispuesta a recorrer en bicicleta tramos de una ruta que no sean agradables, con tal de así poder llegar después a otros tramos que no sólo sí lo sean, sino que además lo sean en suficiente medida como para compensar los anteriores. Y puede que una ruta sea tan mala que no le interese hacer ninguna parte de la misma en bicicleta, o que por el contrario sea tan agradable que la haga toda ella en bicicleta sin tomar el autobús.
Como hay muchas rutas de autobús diferentes, cada una con varias paradas en las que se puede subir o abandonar el autobús, María decide utilizar un programa informático para encontrar la parte de cada ruta que resulta más agradable para andar en bicicleta.
Datos de Entrada
El fichero de datos de entrada tiene la descripción de varias rutas de autobús. La primera línea del fichero es un valor entero b que representa el número de descripciones de rutas que hay en el mismo. El identificador de cada ruta r es el número de orden de su descripción en el fichero de datos de entrada, siendo 1 £ r £ b. Cada descripción de ruta de autobús comienza con una línea que tiene sólo un número, las paradas que hay en la misma: un entero s, tal que
2 £ s £ 20.000. La línea con el número de paradas va seguida de s - 1 líneas, cada una de ellas, llamémosla i (1 £ i < s), con un valor entero ni que representa lo agradable (o desagradable, si es un valor negativo) que María considera el tramo de la ruta entre las paradas i e i + 1.
Datos de Salida
Para cada ruta del fichero de datos de entrada, el programa ha de imprimir los índices i y j que señalan la primera y última parada del tramo de la ruta que tiene mayor grado de agradabilidad para ser recorrido en bicicleta, es decir, el que da la mayor suma m = ni + n i + 1 + ... + n j - 1. Si existe más de un tramo con el mismo valor m, se elegirá el que tenga la mayor longitud para recorrer en bicicleta, es decir, aquél con mayor j - i. Y para romper empates entre los tramos que tengan la misma m y la misma longitud j - 1, se elegirá aquél de ellos que tenga menor i. Para cada ruta r del fichero de datos de entrada, ha de imprimirse una línea que diga:
El tramo más agradable de la ruta r está entre las paradas i y j.
Sin embargo, si la suma máxima no es positiva, el programa debe de escribir:
La ruta r no tiene ningún tramo agradable.
Datos de entrada de ejemplo Datos de salida de ejemplo
3 El tramo más agradable de la ruta 1 está entre las pa- radas 2 y 3
3 El tramo más agradable de la ruta 2 está entre las pa- radas 3 y 9
-1 La ruta 3 no tiene ningún tramo agradable
6
10
4
-5
4
-3
4
4
-4
4
-5
4
-2
-3
-4
|
|
|
|
|