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

USU Championship 2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Yekaterinburg Subway

Time limit: 1.0 second
Memory limit: 64 MB
There is only one branch-line of Yekaterinburg subway. But what a branch-line! Each station is an architectural masterpiece. It is no wonder that all the guests of our city try to have time to observe our subway in detail. And, as usual, the tourists try to manage in the minimal possible time – they have much to see! In an effort to make Yekaterinburg more attractive the city administration decided to work out a program that would calculate the optimal, in respect to the time, route passing all the stations. Of course, the turn of speech “the city administration decided to work out a program” doesn’t represent the facts exactly – the administration decided and this is your team who is to work it out.
The subway contains one branch-line. The trains run here with a definite interval that is evaluated by the integer number of minutes, intervals between the stations are known as well (they are evaluated by the integer number of minutes, too). You may assume that train stops at each station are instant. A tourist leaves a train instantly and it takes one second to board a train. A tourist needs 58 seconds to admire at a station. At the end of the sight seeing a tourist is to return to the starting station of his trip. He has already seen the station in the very beginning and so you are not to add the time of seeing it to the total trip time. A tourist may start his observation any time he likes, so the total trip time is to be counted out from the moment that he enters the train at the departure station.


The first line contains the number of stations N (1 ≤ N ≤ 16). The stations are numbered from 1 to N. The second line consists of N − 1 nonnegative number of minutes that doesn’t exceed 105—the time that a train runs from the first station to the second. From the second to the third, and so on (surely a train runs from the i-th to (i+1)st station and from the (i+1)st to the ith the same time). The third line contains the number of station that is the initial point of the trip. The fourth consists of three numbers: an interval between the trains, the departure time of the first train from the first station and the departure time of the first train from the N-th station;. all the numbers are nonnegative integers and measure minutes. The interval between the trains is nonzero and doesn’t exceed 105, and the departure time from the terminal stations doesn’t exceed the interval.


should contain the duration of the shortest possible observation of all the stations in minutes.


5 7
4 0 1
Problem Author: Leonid Volkov (prepared Leonid Volkov and Alexander Somov)
Problem Source: Ural State University championship, October 25, 2003
To submit the solution for this problem go to the Problem set: 1267. Yekaterinburg Subway