Masala #JME1SFXQPE
Stul
Bir qatorga n ta stul joylashtirilgan, ularning raqamlari chapdan o‘ngga 1 dan n gacha berilgan. Ba’zi stullar odamlar bilan band (har bir stulda maksimal bitta odam), qolganlari bo‘sh. Band bo‘lgan stullar soni n/2 dan oshmaydi.
Ba’zi sabablar bilan odamlarni boshqa stullarga o‘tkazmoqchisiz. Agar ш-stul band bo‘lsa va о-stul bo‘sh bo‘lsa, siz ш-stuldagi odamni о-stulga o‘tkazishingiz mumkin. i-stuldan j-stulga o‘tish vaqti |i−j| daqiqa davom etadi. Bu operatsiyani istalgan soniyada bajarish mumkin, lekin ular ketma-ket bajarilishi kerak, ya’ni avvalgi odam o‘z stuliga o‘tgandan keyin keyingisini harakatlantirishingiz mumkin.
Siz xohlaysizki, boshlang‘ichda band bo‘lgan barcha stullar bo‘sh bo‘lsin. Buni amalga oshirish uchun minimal vaqt qancha bo‘ladi?
Birinchi qatorga bitta butun son n(2 ≤ n ≤ 5000) kiritilgan — stullar soni.
Ikkinchi qatorga n ta butun son \(a_1\), \(a_2\), . . . \(a_n\)kiritilgan (0 ≤ \(a_i\) ≤ 1).
Bitta butun son chiqaring — minimal vaqt, shu shartni bajarish uchun: boshlang‘ichda band bo‘lgan barcha stullar bo‘sh bo‘lishi kerak. Band stullar soni \(n/2\) dan oshmaydi.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
6 1 1 1 0 0 0 |
9 |
Birinchi misolda quyidagi harakatlar ketma-ketligi mumkin:
- 1-stuldagi odamni 2-stulga o‘tkazish — 1 daqiqa;
- 7-stuldagi odamni 6-stulga o‘tkazish — 1 daqiqa;
- 4-stuldagi odamni 5-stulga o‘tkazish — 1 daqiqa.
Ikkinchi misolda quyidagi harakatlar ketma-ketligi mumkin:
- 1-stuldagi odamni 4-stulga o‘tkazish — 3 daqiqa;
- 2-stuldagi odamni 6-stulga o‘tkazish — 4 daqiqa;
- 4-stuldagi odamni 5-stulga o‘tkazish — 1 daqiqa;
- 3-stuldagi odamni 4-stulga o‘tkazish — 1 daqiqa.
Telegram kanalimizga obuna bo'ling