A. Qatnashmagan son
Xotira: 512 MB, Vaqt: 1000 msA massivda 1 dan N gacha bo'lgan sonlardan N-1 ta son beriladi. 1 dan N gacha sonlardan massivda qatnashmaganini toping.
Birinchi qatorda N natural son beriladi. \((1≤N≤5*10^6)\)
Ikkinchi qatorda N-1 ta elementdan iborat sonlar beriladi. \((1≤A_i≤N\)
Masala javobini chop eting.
ESLATMA:
sys yoki boshqa kutubxonalardan foydalanmang!
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
8 4 1 3 5 2 8 6 |
7 |
| 2 |
5 2 4 5 1 |
3 |
B. Squats
Xotira: 32 MB, Vaqt: 1000 msSardorning hamsterlari ko'p va u ularni mashq qildiradi. Bugun \(n\) ta hamster (n juft) mashq qilish uchun keldi. Hamsterlar saf tortdilar va har bir hamster o'tirdi yoki o'rnidan turdi.
Boshqa mashq uchun Sardor o'rnidan turishi uchun aniq \(n / 2\) hamster kerak va o'tirish uchun boshqa hamsterlar kerak. Bir daqiqada Sardorning hamsterlaro o'tirishi yoki turishi mumkin. Agar u optimal tarzda harakat qilsa, unga qancha daqiqa kerak bo'ladi?
Birinchi qatorda \(n (2 ≤ n ≤ 200; n juft)\) butun son mavjud. Keyingi qatorda bo'sh joysiz \(n\) ta belgi mavjud. Bu belgilar hamsterlarning holatini tasvirlaydi: agar qatordagi \(i\)-chi hamster tik turgan bo'lsa, \(i\)-belgi \("X"\) ga, agar u o'tirgan bo'lsa, \("x"\) ga teng.
Birinchi qatorda bitta butun sonni chop eting - minimal talab qilinadigan daqiqalar soni. Ikkinchi qatorda, Sardor kerakli o'zgarishlarni amalga oshirgandan so'ng, hamsterlarning holatini tavsiflovchi ipni chop eting. Agar bir nechta optimal pozitsiyalar mavjud bo'lsa, ulardan birini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 xxXx |
1 XxXx |
| 2 |
2 XX |
1 xX |
| 3 |
6 xXXxXx |
0 xXXxXx |
C. Buttons
Xotira: 32 MB, Vaqt: 1000 msAxror 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.
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
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 |
3 |
| 2 |
3 |
7 |
D. Belgilar
Xotira: 32 MB, Vaqt: 1000 msMetropolislar olimpiadasida \(b\) o'g'il va \(g\) qiz qatnashmoqda. Kechqurun stol o'yinlari bo'yicha turnir bo'lib o'tadi va \(n\( ishtirokchi taklifni qabul qildi. Ular orasida nechta o‘g‘il-qiz borligini tashkilotchilar bilmaydi.
Tashkilotchilar qizlar uchun qizil, o‘g‘il bolalar uchun ko‘k nishonlarni tayyorlamoqda.
Sardor \(n+1\) ta ko'krak nishonlarini tayyorladi. \(i\)-chi (bu erda \(i\) 0 dan n gacha, shu jumladan) palubada \(i\) koʻk nishonlar va \(n−i\) qizil nishonlar mavjud. Har qanday palubadagi nishonlarning umumiy soni aynan \(n\) ga teng.
Sardor olishi kerak bo'lgan ushbu \(n+1\) palubalarning minimal sonini aniqlang, shunda turnir ishtirokchilari orasida qancha qiz va o'g'il bo'lishidan qat'i nazar, mos pastki bo'ladi.
Birinchi qatorda o'g'il bolalar soni bo'lgan \(b (1≤b≤300)\) butun soni mavjud.
Ikkinchi qatorda qizlar soni \(g(1≤g≤300)\) butun soni mavjud.
Uchinchi qatorda \(n(1≤n≤b+g)\) butun son, stol o‘yinlari turniri ishtirokchilari soni mavjud.
Yagona butun sonni, Sardor olishi mumkin bo'lgan eng kam nishonlar sonini chiqaring.
Birinchi misolda \(4\) ta palubaning har biri olinishi kerak: (0 ko'k, 3 qizil), (1 ko'k, 2 qizil), (2 ko'k, 1 qizil), (3 ko'k, 0 qizil).
Ikkinchi misolda \(4\) ta paluba olinishi kerak: (2 ko'k, 3 qizil), (3 ko'k, 2 qizil), (4 ko'k, 1 qizil), (5 ko'k, 0 qizil). Qoziqlar (0 ko'k, 5 qizil) va (1 ko'k, 4 qizil) foydalanish mumkin emas.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 6 3 |
4 |
| 2 |
5 3 5 |
4 |
E. Teshiklar
Xotira: 32 MB, Vaqt: 1000 msKichkina Shakhriyor juda ko'p o'ynashni yaxshi ko'radi. Eng muhimi, u "Teshiklar" o'yinini o'ynashni yaxshi ko'radi. Bu quyidagi qoidalarga ega bir kishi uchun o'yin:
Bitta qatorda joylashgan va \(1\) dan \(N\) gacha bo'lgan raqamlar bilan chapdan o'ngga raqamlangan \(N\) ta teshik bor. Har bir teshik o'z kuchiga ega (teshik raqami \(i , a_i\) quvvatiga ega). Agar siz to'pni \(i\) teshigiga tashlasangiz, u darhol \(i + a_i\) teshigiga sakraydi, keyin undan sakrab chiqadi va hokazo. Agar bunday raqam bilan teshik bo'lmasa, to'p shunchaki qatordan sakrab chiqadi. Har bir \(M\) harakatda o'yinchi ikkita harakatdan birini bajarishi mumkin:
- Teshikning kuchini \(a\) qiymatiga o'rnating \(b\).
- To'pni \(a\) teshigiga tashlang va to'p qatordan sakrashdan oldin qancha sakrab chiqqanini hisoblang, shuningdek, qatordan chiqishdan oldin qaysi teshikdan sakrab chiqqanini ham yozing.
Shakhriyor matematikada yaxshi emas, shuning uchun siz allaqachon taxmin qilganingizdek, barcha hisob-kitoblarni bajarishingiz kerak.
Birinchi qatorda ikkita butun \(N\) va \(M (1 ≤ N ≤ 10^5, 1 ≤ M≤ 10^5)\) mavjud — qatordagi teshiklar soni va harakatlar soni. Ikkinchi qatorda \(N\) dan oshmaydigan \(N\) musbat sonlar mavjud - teshik quvvatining boshlang'ich qiymatlari. Quyidagi \(M\) qatorlar Shakhriyor tomonidan qilingan harakatlarni tasvirlaydi. Ushbu qatorlarning har biri ikkita turdan biri bo'lishi mumkin:
- \(0 a b\)
- \(1 b\)
\(0\) turi \(a\) teshikning quvvatini \(b\) ga o'rnatish kerakligini bildiradi va \(1\) turi \(a\)-teshikka to'p tashlashni talab qiladi. \(a\) va \(b\) raqamlari \(N\) dan oshmaydigan musbat butun sonlardir.
\(1\)-turdagi har bir harakat uchun alohida qatorga bo'sh joy bilan ajratilgan ikkita raqamni chiqaring - qatordan chiqishdan oldin to'p tashrif buyurgan so'nggi teshik soni va u qilgan sakrashlar soni.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
8 5 1 1 1 1 1 2 8 2 1 1 0 1 3 1 1 0 3 4 1 2 |
8 7 8 5 7 3 |