Рус Uzb Eng

C27N. Jack monsterlarga qarshi
Ограничение по времени: 2 cекунды
Ограничение по памяти: 64 мегабайт

Jack bir kun labiritdan chiqish yo’lini izlab bir chuqurga tushib ketti. Bu chuqur atrofida monsterlar o’z kursilarida o’tirar edilar. Ular Jackni ko’rgan zaxotiyoq uni yo’q qilmoqchi bo’ldilar. Lekin Jackning qo’lida BFG – 9000 nomli quroli bor edi. Uning quroli faqatgina 3 ta ketma-ket kelgan kursiga o’q ota oladi. O’q otilgandan so’ng kursilardagi monsterlar o’ladi, lekin qolgan monsterlar Jackga qarata o’z sehrlarini ishlatib zarar yetqazadilar. Monsterlar chuqurda aylana shaklida turishibdi, Jack esa chuqurning o’rtasida, har bir monsterning bir marta otgadagi zarari damage[i] orqali belgilangan, shunda sizning vazifangiz Jackga yetkazilgan minimal zararni topishingiz kerak.
Masalan: 7 ta monster va ularning zararlari 3, 4, 2, 2, 1, 4, 1 bo’lsin.

Ko’rib turganingizdek, monsterlar berilgan tartibda ketma-ket va aylana shaklida joylashgan, ya’ni 1 -> 2, 2 -> 3, …, 6 ->7, 7 -> 1. Rasmda ularning yetkazadigan zararlari belgilangan. Endi Jack quyidagicha ish tutsa unga monsterlar eng kam miqdorda zarar yetkaza oladi. 1- safar Jack, 1- ,2-, 3- monsterlarga qarata o’q otadi va qolgan monsterlardan jami 8 birlik zarar oladi. 2 – safar u 4-, 5-, 6- monsterlaga qarata o’q otadi va qolgan bitta monster yani 7-si unga 1 birlik zarar yetkazadi, oxirida esa 7- monsterni yo’q qiladi va Jackga minimal 9 birlik zarar yetkaziladi.

Входные данные:
Birinchi qatorda monsterlar soni N beriladi (3 <= N <= 20). Ikkinchi qatorda esa N ta monsterlarning damage lari berilgan. i- son i-monsterning yetkazadigan zarari.

Выходные данные:
Bitta qatorda Jackning minimal oladigan zararini chiqaring.

Пример ввода Пример вывода
7
3 4 2 2 1 4 1
8
4 5 6 5 4 5 6 5
9


33
Область:
Источник задачи: Adham & Sunnat

Отправить решение на проверку

Design by TUIT © 2012-2018 TUIT Online Judge. All rights reserved.