Submit | All submissions | Best solutions | Back to list |
AE3A - Drilling |
Byteman is the person in charge of a team that is looking for crude oil reservoirs. He has made two boreholes: he found crude oil in point A and found out that there is no crude oil in point B. It is known that the oil reservoir occupies a connected fragment of segment AB with one end at point A. Now Byteman has to check, how far, along the segment connecting points A and B, does the oil reservoir reach. It is not that simple, however, because in some locations one can drill faster than in other locations. Moreover, Byteman’s team is rather small, so they can drill in at most one location at a time. Byteman’s boss would like him to predetermine when he will be able to identify the boundary of the oil reservoir.
Byteman has asked you for help. He has divided the segment connecting points A and B into n+1 segments of equal length. If we assume that point A has coordinate 0, and point B coordinate n + 1, then there are n points with coordinates 1, 2 ... n between them. It is enough to find the farthest from A of these points in which some crude oil occurs. Byteman has informed you about the amounts of time necessary for making boreholes in these points — they are equal to t1, t2 ... tn respectively. You should create such a plan of drilling, that the time necessary to identify the oil reservoir’s boundary is shortest possible, assuming the worst-case scenario.
Input
The first line of the standard input contains a single positive integer n (1 ≤ n ≤ 2000). The second line contains n positive integers t1, t2 ... tn separated by single spaces (1 ≤ ti ≤ 106).
Output
Your program should write a single integer to the standard output—the smallest amount of time that Byteman has to spend (assuming the worst-case scenario) drilling in search of oil, to be sure that he will identify the reservoir’s boundary.
Example
For the input data:
4 8 24 12 6
the correct result is:
42
Explanation of the example.
Assume that Byteman makes the first borehole at point 1, what takes him time 8. It can then turn out that he finds crude oil there and he will have to check, how far to the right does the reservoir reach. He will need two more boreholes, making which requires 36 units of time in the worst case. Therefore, in this case Byteman will spend in total 44 units of time drilling.
It turns out that it is better to start at point 2. If there is no crude oil there, it is sufficient to check point 1. However, in the worst case Byteman will have to make two more boreholes in points 3 and 4 and end his work in total time equal to 42.
Added by: | Race with time |
Date: | 2009-05-03 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Algorithmic Engagements 2009 |
hide comments
2019-04-16 09:23:00
such fun, much interesting problem |
|
2014-08-17 19:55:50 Daga
Can anyone explain the problem |
|
2013-07-20 07:45:56 Atul Vaibhav
getting WA! whats the output for: 20 12 65 98 7 4 21 35 15 98 26 45 32 84 25 2 65 12 20 39 87 |
|
2009-08-17 06:36:46 Lox
The time limit is so strict that it's hard to optimize an O(N^2) approach and I had to use an O(N^3) approach with weird optimization :( |
|
2009-06-07 21:17:54 Alfonso2 Peterssen
I have an O(n^3) worst case(optimized of course), but it is as fast as an O(n^2). Time limit too strict... |
|
2009-06-04 11:17:54 nik
Problem statement isn't complete. Poor translation. |
|
2009-06-04 05:18:54 Mark Gordon
Maybe the time limit is too strict? I have a fairly reasonable O(N^2) solution that is timing out. Whew, finally got it accepted. However I still feel like the time limit is pretty mean. Last edit: 2009-06-04 05:41:00 |