ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Transsib

Time limit: 0.5 second
Memory limit: 64 MB
The route of the Moscow–Vladivostok “Rossiya” passenger train is considered to be the main route of the Trans-Siberian Railway. Its itinerary includes Nizhny Novgorod, Kirov, Perm, and Yekaterinburg. The train goes from Moscow to Yekaterinburg in 25 h 41 min. The “Ural” train follows the southern line of the Trans-Siberian Railway through Kazan and completes the journey in 25 h 25 min. It is impossible to go by train from Moscow to Yekaterinburg in a shorter time.
Problem illustration
This is the scheme of the railroads between Moscow (M) and Yekaterinburg (Y). It is seen that the routes of the trains “Rossiya” (the upper line in the scheme) and “Ural” (the lower line) are crossed by major rivers: Volga, Vyatka, and Kama. The former train crosses them at Nizhny Novgorod (1), Kotelnich (2), and Perm (3), respectively. The latter train crosses the rivers in 35 km west of Kazan (4), in Vyatskie Polyany (5), and in Sarapul (6). The scheme also shows direct lines connecting some of these cities.
In addition to passenger trains, there are also goods trains following these railroads. They can take one of the four routes:
  1. Moscow – Nizhny Novgorod – Kotelnich – Sarapul – Yekaterinburg
  2. Moscow – Kazan – Vyatskie Polyany – Sarapul – Yekaterinburg
  3. Moscow – Kazan – Kotelnich – Perm – Yekaterinburg
  4. Moscow – Nizhny Novgorod – Vyatskie Polyany – Perm – Yekaterinburg
Minister of Railway Transport wants to organize the goods train service in such a way that the freight flow from Moscow to Yekaterinburg be as much as possible. He knows that the bridges across the rivers shown in the scheme are the “bottlenecks” for the trains. For each bridge, the carrying capacity is known, i.e., the amount of freight that can be taken through the bridge in a day. Help the minister solve the problem.


The only input line contains the carrying capacities of the bridges in Nizhny Novgorod, in Kotelnich, in Perm, near Kazan, in Vyatskie Polyany, and in Sarapul. These are integers in the range from 1 to 109.


Find the daily amount of freight sent from Moscow along each of the routes specified above so that the total freight flow from Moscow to Yekaterinburg be maximal. Output these four numbers accurate to 10−3, separating them with a space. If the problem has several solutions, output any of them.


70 30 60 100 20 50
20.000 10.000 10.000 10.000
Problem Author: Alexander Ipatov
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010
To submit the solution for this problem go to the Problem set: 1764. Transsib