Задача 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.