Задача Wie
Байтазар - руководитель бригады, которая ищет нефть. Известно, что месторождение нефти представляет собой отрезок с одним концом в точке А и другим внутри отрезка AB. Команда выяснила, что в точке A нефть есть, а в точке В - нет. Теперь Байтазару нужно узнать вторую границу месторождения (где именно внутри отрезка AB граница месторождения).
Поскольку в разных точках грунт состоит из разных пород, время бурения одной скважины зависит от места. Бригада Байтазара небольшая, поэтому они не могут бурить в разных местах одновременно. Босс Байтазара желает знать, когда бригада будет в состоянии определить границы месторождения. Байтазар попросил вас о помощи. Он разделил отрезок, соединяющий точки А и В, на отрезки равной длины. Точка A имеет координату 0, точка B координату N+1, а между ними есть N точек с координатами 1, 2,. . . , N. Байтазар сообщил вам количество времени, необходимое для бурения скважин в этих точках - оно равно t1, t2. . ., tN соответственно. Вы должны создать такой план бурения, что время, необходимое для определения дальней от точки A границы нефтяного месторождения, минимально (предполагая наихудший сценарий).
Технические условия. Программа читает с клавиатуры сначала натуральное число N (1 <= N <= 200), затем N натуральных чисел t1, t2. . ., tN, разделенных пробелами (1<= ti<=106). Ваша программа выводит на экран одно целое число - минимальное количество времени, которое придётся потратить Байтазару (предполагая наихудший сценарий), чтобы определить границы месторождения.
Пример
Ввод:
4 8 24 12 6
Вывод:
42
Объяснение примера. Предположим, что Байтазар бурит первую скважину в точке 1, что требует времени 8. Если окажется, что нефть там есть, ему может понадобиться пробурить скважины и в точке 2, и в точке 3. Если он пробурит только в точке 3, может оказаться, что там нефти нет и надо проверить, есть ли она в точке 2. Если он пробурит только в точке 2, может оказаться, что там нефть есть, и надо проверить точку 3. Таким образом, бурение скважин может занять 8+24+12=44 единиц времени. Оказывается, лучше начать бурения с точки 2. Если окажется, что нефти там нет, надо проверить точку 1, получим затраты времени 24+8=32. Если окажется, что нефть там есть, будет гарантированно достаточно пробурить в точках 3 и 4, получив суммарные затраты времени 24+12+6=42.