Avanzado

Problemas de nivel nacional.
Problema

El Viajero

Enviado por jesus el 1 de Enero de 2008 - 01:00.

Un viajero decide tomar un paseo en su propio automóvil, recorriendo un camino "circular" que pasa por $n$ ciudades; es decir, sin importar en la ciudad que inicie, regresará a ésta después de pasar por las otras.

La distancia total del recorrido es de $K$ kilómetros. Por otro lado, cada ciudad (digamos la ciudad $i$, con $i$ entre $1$ y $n$) tiene un máximo de gasolina que puede vender por usuario y con dicha gasolina se puede avanzar alguna cierta cantidad de kilómetros ($K_i$ kilómetros para la ciudad i).

Supongamos que el total de gasolina que se puede obtener en las distintas ciudades es apenas suficiente para realizar todo el recorrido, es decir, $K_1 + K_2 + ... + K_n = K$.

Distribuir contenido