Masala #HD1MWGK6P2
Buttons
Axror juda qiyin qulfni ochishga harakat qilmoqda. Qulfda \(n\) ta tugma bor va uni ochish uchun siz qulfni ochish uchun tugmalarni ma'lum tartibda bosishingiz kerak. Ba'zi tugmachalarni bosganingizda, u qulfda bosilganda qoladi (ya'ni siz to'g'ri taxmin qildingiz va ketma-ketlikda keyingi tugmani bosgansiz) yoki barcha bosilgan tugmalar dastlabki holatiga qaytadi. Barcha tugmalar birdaniga qulfga bosilganda, qulf ochiladi.
Uchta tugmachali misolni ko'rib chiqing. Aytaylik, ochilish ketma-ketligi: {2, 3, 1}. Agar siz avval 1 yoki 3 tugmalarni bossangiz, tugmalar darhol ochiladi. Agar siz 2-tugmani birinchi bossangiz, u bosilganda qoladi. Agar siz 2 dan keyin 1 ni bossangiz, barcha tugmalar bosilmaydi. Agar siz 2 dan keyin 3 ni bossangiz, 3 va 2 tugmalari bosilganda qoladi. Ikkita tugma bosilgach, qulfni ochish uchun 1-tugmani bosishingiz kifoya.
Axror ochilish ketma-ketligini bilmaydi. Ammo u haqiqatan ham aqlli va u eng maqbul tarzda harakat qiladi. Eng yomon stsenariyda qulfni ochish uchun u tugmani necha marta bosishi kerakligini hisoblang.
Bitta satr \(n (1 ≤ n ≤ 2000)\) butun sonini o'z ichiga oladi - bu qulfdagi tugmalar soni.
Manao eng yomon stsenariyda tugmani necha marta bosishi kerakligini bitta qatorda chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
2 |
3 |
| 2 |
3 |
7 |
Birinchi sinov namunasini ko'rib chiqing. Axror birinchi bosishda muvaffaqiyatsiz bo'lishi va noto'g'ri tugmani bosishi mumkin. Bunday holda, u ikkinchi surish bilan to'g'risini taxmin qila oladi. Va uning uchinchi bosilishi ikkinchi o'ng tugmani bosadi. Shunday qilib, eng yomon stsenariyda unga faqat 3 ta surish kerak bo'ladi
Telegram kanalimizga obuna bo'ling