A. Birinchi ishonch
Xotira: 262 MB, Vaqt: 1000 msBir yil oldin kanalga ilk xabarlar joylanayotgan paytda hali hech kim katta sarlavhalar haqida o'ylamagan edi. Avval bitta o'quvchi viloyatda yaxshi natija ko'rsatdi, keyin yana bittasi. Vaqt o'tib, saralash bosqichlari, respublika natijalari va xalqaro medallar ham shu kundalik yozuvlar qatoriga qo'shildi.
Ismoilmirzo har bir natijani oddiy son bilan belgilab borgan. \(i\)-xabarga yozilgan son \(a_i\) bo'lsin. Agar \(a_i\) o'zidan oldingi barcha sonlardan qat'iy katta bo'lsa, \(i\)-xabar yangi bosqich deyiladi. Xususan, birinchi xabar har doim yangi bosqich hisoblanadi.
Lekin ishonch bitta katta sakrashdan emas, ketma-ket ko'rinib turgan o'sishdan paydo bo'ladi. Shuning uchun yangi bosqichlarning faqat ayrimlari ishonch belgisi deb sanaladi:
- birinchi yangi bosqich har doim ishonch belgisi;
- keyingi har bir yangi bosqich \(a_i\) faqat \(a_i - q \le k\) bo'lsa ishonch belgisi sanaladi. Bu yerda \(q\) - undan oldingi eng so'nggi yangi bosqichdagi son.
E'tibor bering: agar yangi bosqich \(a_i - q > k\) bo'lgani uchun ishonch belgisi sanalmasa ham, u yangi bosqichligicha qoladi; keyingi taqqoslashlarda \(q\) o'rnini aynan u egallaydi.
Berilgan xabarlar ichida nechta ishonch belgisi borligini toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 1 \le k \le 10^9)\).
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).
Ishonch belgilarining sonini chiqaring.
Birinchi namunada yangi bosqichlar \(2\), \(4\), \(10\), \(12\), \(16\). \(2\) birinchi yangi bosqich bo'lgani uchun sanaladi. \(4-2=2\), \(12-10=2\) va \(16-12=4\) qiymatlarining har biri \(k=5\) dan oshmaydi, demak ular ishonch belgisi. \(10-4=6 > 5\) bo'lgani uchun \(10\) ishonch belgisi emas, lekin keyingi taqqoslash aynan \(10\) bilan olib boriladi.
Ikkinchi namunada \(10\) birinchi yangi bosqich. \(15-10=5 > 3\) bo'lgani uchun \(15\) sanalmaydi, lekin yangi bosqich bo'lib qoladi. \(16-15=1 \le 3\), shuning uchun \(16\) ishonch belgisi. Jami \(2\) ta.
Uchinchi namunada bitta xabar bor va u birinchi yangi bosqich sifatida ishonch belgisi hisoblanadi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
6 5 2 4 10 12 16 15 |
4 |
| 2 |
4 3 10 9 15 16 |
2 |
| 3 |
1 100 7 |
1 |
B. Upsolve qarzi
Xotira: 262 MB, Vaqt: 1000 msBirinchi natijalardan keyin akademiyada bitta qoida sekin-asta odatga aylandi: contest tugashi bilan hammasi tugab qolmaydi. Yechilmay qolgan masala keyingi darsgacha "qarz" bo'lib turadi. Tahlilda eng avval eng eski qarz ochiladi, chunki eski xato qolib ketsa, yangi mavzu ham mustahkam bo'lmaydi.
Bir o'quvchining \(n\) kunlik yozuvi berilgan. Har bir kun bitta belgi bilan ifodalangan:
X- shu kuni bitta yangi xato paydo bo'ldi;U- shu kuni bitta upsolve qilindi;-- shu kuni yangi xato ham, upsolve ham bo'lmadi.
Har bir U belgisi hali yopilmagan xatolarning eng eskisini, ya'ni eng oldin paydo bo'lganini yopadi. Agar shu paytda yopilmagan xato bo'lmasa, bu U hech narsani o'zgartirmaydi.
Agar \(i\)-kunda paydo bo'lgan xato \(j\)-kunda yopilsa va \(j - i \le k\) bo'lsa, bu xato vaqtida yopilgan hisoblanadi. Umuman yopilmagan xato vaqtida yopilgan hisoblanmaydi.
Vaqtida yopilgan xatolar sonini toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le k \le n)\).
Ikkinchi qatorda uzunligi \(n\) ga teng \(s\) satri beriladi. Har bir belgi X, U yoki - bo'ladi.
Vaqtida yopilgan xatolar sonini chiqaring.
Birinchi namunada \(1\)-kundagi xato \(4\)-kunda, \(3\)-kundagi xato \(5\)-kunda, \(6\)-kundagi xato \(7\)-kunda yopiladi. Farqlar mos ravishda \(3\), \(2\) va \(1\); uchalasi ham \(k=3\) dan oshmaydi.
Ikkinchi namunada \(1\)-kundagi xato \(4\)-kunda, \(2\)-kundagi xato \(5\)-kunda yopiladi. Ikkala farq ham \(3\) ga teng, bu \(k=1\) dan katta.
Uchinchi namunada \(1\)-kundagi xato \(2\)-kunda yopiladi (farq \(1 \le 2\)). \(3\)-kundagi xato \(6\)-kunda yopiladi (farq \(3 > 2\)), \(4\)-kundagi xato esa umuman yopilmaydi. Demak, javob \(1\).
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
7 3 X-XUUXU |
3 |
| 2 |
5 1 XX-UU |
0 |
| 3 |
6 2 XUXX-U |
1 |
C. O'sish zanjiri 1
Xotira: 262 MB, Vaqt: 2000 msBir necha oy o'tgach, dars xonasidagi doskada faqat oxirgi contest natijasi emas, haftalar bo'yicha o'sish ham ko'rina boshladi. Ustoz uchun bitta omadli kun yetarli emas edi: o'quvchilar ketma-ket haftalarda avvalgidan kuchliroq ishlay olishyaptimi, bu narsa ham juda muhim edi.
\(n\) ta ketma-ket haftadagi natijalar \(a_1, a_2, \ldots, a_n\) berilgan. Siz biror uzluksiz kesma \(a_l, a_{l+1}, \ldots, a_r\) ni tanlaysiz. Kesmadagi har bir natijani o'z joyida qoldirish yoki istalgan kattaroq butun songa oshirish mumkin; kamaytirish mumkin emas.
Tuzatishdan keyin kesma qat'iy o'suvchi bo'lishi kerak: yangi qiymatlar \(b_l, b_{l+1}, \ldots, b_r\) bo'lsa, \(b_l < b_{l+1} < \cdots < b_r\) bo'lsin. Bitta natijadan iborat kesma har doim qat'iy o'suvchi hisoblanadi.
Barcha oshirishlar yig'indisi, ya'ni \((b_l - a_l) + (b_{l+1} - a_{l+1}) + \cdots + (b_r - a_r)\), \(k\) dan oshmasligi kerak.
Shu shartlarda mumkin bo'lgan eng uzun kesma uzunligi \(r - l + 1\) ni toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 4000,\ 0 \le k \le 10^{18})\).
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).
Eng uzun mos kesma uzunligini chiqaring.
Birinchi namunada \(2\)-haftadan \(4\)-haftagacha bo'lgan kesma \(1, 2, 1\). Oxirgi qiymatni \(3\) ga oshirsak, kesma \(1, 2, 3\) bo'ladi va jami \(2\) birlik oshirish sarflanadi. Bu \(k=3\) dan oshmaydi.
Ikkinchi namunada oshirishga umuman ruxsat yo'q \((k=0)\). Masalan, \(1, 2\) yoki \(2, 3\) kesmalari uzunligi \(2\) bo'lgan qat'iy o'suvchi kesmalardir; uzunligi \(3\) bo'lgan mos kesma esa yo'q.
Uchinchi namunada oxirgi uchta qiymatni \(1, 2, 3\) ko'rinishiga keltirish mumkin; buning uchun jami \(3\) birlik oshirish yetadi. To'rttala qiymatni qat'iy o'suvchi qilish uchun esa birinchi \(5\) dan keyingi uchta qiymat kamida \(6, 7, 8\) bo'lishi kerak. Bu \(18\) birlik oshirish talab qiladi va \(k=10\) dan katta.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 3 3 1 2 1 2 |
3 |
| 2 |
4 0 1 2 2 3 |
2 |
| 3 |
4 10 5 1 1 1 |
3 |
D. Qo'shimcha tahlil
Xotira: 262 MB, Vaqt: 2000 msUpsolve daftaridagi qarzlar birma-bir yopila boshlagach, akademiyada yana bir odat shakllandi: bir xil xato ko'pchilikda takrorlansa, uni har bir o'quvchiga alohida tushuntirish o'rniga umumiy tahlilda parchalab ko'rish kerak edi. Guruhlar ko'paygan sari bunday tahlillar ham bitta uzun dars emas, qisqa tahlil bloklari ko'rinishida rejalashtirila boshlandi.
\(n\) kunlik jarayon berilgan. Hali tushuntirilmagan xatolar sonini qarz deb ataymiz. Dastlab qarz \(0\) ga teng. Har bir \(i\)-kun quyidagi tartibda o'tadi:
- Avval \(a_i\) ta yangi xato aniqlanadi va qarz shuncha oshadi.
- Keyin odatiy dars davomida ko'pi bilan \(b_i\) ta xato tushuntiriladi. Agar qarz \(b_i\) dan kam bo'lsa, faqat mavjud xatolar yopiladi.
- Agar shundan keyin qarz \(k\) dan oshsa, o'sha kuni qo'shimcha tahlil bloklari o'tkaziladi. Bitta blok ko'pi bilan \(p\) ta mavjud xatoni yopadi. Bir kunda bir nechta blok o'tkazish mumkin.
Qo'shimcha tahlil bloklari faqat qarz \(k\) dan oshgan kunlarda o'tkaziladi. Qarz \(k\) dan oshmay qolishi bilan o'sha kun uchun tahlil tugaydi. Masalan, bitta blokdan keyin qarz \(k\) dan oshmay qolsa, shu kuni ikkinchi blok o'tkazilmaydi.
Har bir kun oxirida qarz \(k\) dan oshmasligi kerak. Butun \(n\) kun davomida jami ko'pi bilan \(m\) ta qo'shimcha tahlil bloki o'tkazish mumkin.
Shartlarni bajarish mumkin bo'lgan eng kichik manfiy bo'lmagan butun \(p\) ni toping. Agar tahlil bloklari qanchalik kuchli bo'lishidan qat'i nazar, \(m\) ta blok yetmasa, -1 chiqaring.
Birinchi qatorda uchta butun son \(n\), \(m\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le m \le n,\ 0 \le k \le 10^{18})\).
Keyingi \(n\) qatorda ikkitadan butun son \(a_i\) va \(b_i\) beriladi \((0 \le a_i,b_i \le 10^9)\).
Eng kichik mos \(p\) ni chiqaring. Agar bunday \(p\) mavjud bo'lmasa, -1 chiqaring.
Birinchi namunada \(p=3\) bo'lsa, \(2\)-kuni odatiy darsdan keyingi qarz \(4\) ga teng bo'ladi. Bitta qo'shimcha blokdan so'ng u \(1\) ga tushadi. \(4\)-kuni qarz \(5\) ga yetadi va yana bitta blokdan so'ng \(2\) bo'lib qoladi. Jami \(2\) ta blok ishlatiladi. \(p=2\) bo'lsa, \(4\)-kuni qarzni \(3\) dan oshirmaslik uchun o'sha kunning o'zida \(2\) ta blok kerak bo'ladi; oldingi blok bilan birga jami \(3\) ta blok chiqadi.
Ikkinchi namunada \(1\)-kunda ham, \(2\)-kunda ham kamida bittadan qo'shimcha blok kerak. Ruxsat etilgan bloklar soni esa faqat \(1\) ta, shuning uchun javob -1.
Uchinchi namunada odatiy darslarning o'zi qarzni hech qachon \(5\) dan oshirmaydi. Shu sababli \(p=0\) yetarli.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 2 3 3 1 4 2 0 1 5 0 1 3 |
3 |
| 2 |
3 1 1 5 0 5 0 0 10 |
-1 |
| 3 |
3 0 5 2 0 2 1 1 4 |
0 |
E. Yo'l xaritasi
Xotira: 262 MB, Vaqt: 2000 msYilning ikkinchi yarmida akademiyadagi mashg'ulotlar oddiy dars bo'lib qolmadi. O'quvchilar uchun to'liq yo'l xaritasi tuzildi: qaysi darsdan keyin qaysi kontestga kirish, qaysi kontestdan keyin qaysi tahlilni ko'rish kerakligi oldindan belgilab qo'yilardi. Bu tartib buzilsa, o'quvchi ko'p material ko'radi, lekin ularni kerakli paytda bog'lay olmaydi.
\(n\) ta modul bor. Har bir modulning turi D, K yoki T:
D- dars;K- contest;T- tahlil.
Shuningdek, \(m\) ta yo'naltirilgan o'tish berilgan. Har bir o'tish \(u \to v\) ko'rinishida va doim \(u < v\), ya'ni yo'l xaritasida orqaga qaytish yo'q.
Yo'l deb har bir qo'shni juftligi berilgan o'tishlar bilan bog'langan modullar ketma-ketligi \(v_1 \to v_2 \to \cdots \to v_t\) ga aytamiz. Bitta moduldan iborat ketma-ketlik \((t=1)\) ham yo'l hisoblanadi.
Yo'l yaxshi deyiladi, agar undagi ketma-ket kelgan har ikki modulning turi turlicha bo'lsa. Yo'l boshlanishidan oldin ustoz shu yo'ldagi ko'pi bilan bitta modulning turini istalgan boshqa turga almashtirib berishi mumkin. Masalan, bitta D modulini K yoki T qilish mumkin.
Eng uzun yaxshi yo'l nechta moduldan iborat bo'lishi mumkin?
Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le m \le 2 \cdot 10^5)\).
Ikkinchi qatorda uzunligi \(n\) ga teng \(s\) satri beriladi. Har bir belgi D, K yoki T bo'ladi va mos modulning turini bildiradi.
Keyingi \(m\) qatorda ikkitadan butun son \(u\) va \(v\) beriladi \((1 \le u < v \le n)\). Bu \(u\)-moduldan \(v\)-modulga o'tish mumkinligini bildiradi.
Ko'pi bilan bitta modul turini almashtirishdan keyin olinishi mumkin bo'lgan eng uzun yaxshi yo'ldagi modullar sonini chiqaring.
Birinchi namunada \(2 \to 3 \to 4 \to 5\) yo'lini olish mumkin. Bu yo'ldagi turlar D, K, T, T. Oxirgi modulning turi D ga almashtirilsa, turlar D, K, T, D bo'ladi va har bir qo'shni juftlikda turlar farqli bo'ladi. Demak, \(4\) ta moduldan iborat yaxshi yo'l bor.
Ikkinchi namunada, masalan, \(1 \to 2 \to 3\) yo'lini olib, \(2\)-modulning turini K ga almashtirish mumkin. Shunda turlar D, K, D bo'ladi. \(4\) ta modulli yo'lda esa bitta almashtirish yetmaydi.
Uchinchi namunada hech qanday o'tish yo'q, shuning uchun har qanday yo'l bitta moduldan iborat.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 4 DDKTT 1 2 2 3 3 4 4 5 |
4 |
| 2 |
4 3 DDDD 1 2 2 3 3 4 |
3 |
| 3 |
3 0 DKT |
1 |
F. O'sish zanjiri 2
Xotira: 262 MB, Vaqt: 2000 msBir necha oy o'tgach, dars xonasidagi doskada faqat oxirgi kontest natijasi emas, haftalar bo'yicha o'sish ham ko'rina boshladi. Ustoz uchun bitta omadli kun yetarli emas edi: o'quvchi ketma-ket haftalarda avvalgidan kuchliroq ishlay olyaptimi, u aynan shuni kuzatardi.
\(n\) ta ketma-ket haftadagi natijalar \(a_1, a_2, \ldots, a_n\) berilgan. Siz biror uzluksiz kesma \(a_l, a_{l+1}, \ldots, a_r\) ni tanlaysiz. Kesmadagi har bir natijani o'z joyida qoldirish yoki istalgan kattaroq butun songa oshirish mumkin; kamaytirish mumkin emas.
Tuzatishdan keyin kesma qat'iy o'suvchi bo'lishi kerak: yangi qiymatlar \(b_l, b_{l+1}, \ldots, b_r\) bo'lsa, \(b_l < b_{l+1} < \cdots < b_r\) bo'lsin. Bitta natijadan iborat kesma har doim qat'iy o'suvchi hisoblanadi.
Barcha oshirishlar yig'indisi, ya'ni \((b_l - a_l) + (b_{l+1} - a_{l+1}) + \cdots + (b_r - a_r)\), \(k\) dan oshmasligi kerak.
Shu shartlarda mumkin bo'lgan eng uzun kesma uzunligi \(r - l + 1\) ni toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le k \le 10^{18})\).
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).
Eng uzun mos kesma uzunligini chiqaring.
Birinchi namunada \(2\)-haftadan \(4\)-haftagacha bo'lgan kesma \(1, 2, 1\). Oxirgi qiymatni \(3\) ga oshirsak, kesma \(1, 2, 3\) bo'ladi va jami \(2\) birlik oshirish sarflanadi. Bu \(k=3\) dan oshmaydi.
Ikkinchi namunada oshirishga umuman ruxsat yo'q \((k=0)\). Masalan, \(1, 2\) yoki \(2, 3\) kesmalari uzunligi \(2\) bo'lgan qat'iy o'suvchi kesmalardir; uzunligi \(3\) bo'lgan mos kesma esa yo'q.
Uchinchi namunada oxirgi uchta qiymatni \(1, 2, 3\) ko'rinishiga keltirish mumkin; buning uchun jami \(3\) birlik oshirish yetadi. To'rttala qiymatni qat'iy o'suvchi qilish uchun esa birinchi \(5\) dan keyingi uchta qiymat kamida \(6, 7, 8\) bo'lishi kerak. Bu \(18\) birlik oshirish talab qiladi va \(k=10\) dan katta.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 3 3 1 2 1 2 |
3 |
| 2 |
4 0 1 2 2 3 |
2 |
| 3 |
4 10 5 1 1 1 |
3 |
G. Kubok yo'li
Xotira: 262 MB, Vaqt: 3000 msNihoyat, "1 Yil Kubogi" kuni keldi. Auditoriyadagi katta doskaga akademiyaning bir yillik yo'li daraxt ko'rinishida chizildi: bir joyda birinchi dars, bir joyda ichki duel, boshqa joyda tahlildan keyingi upsolve, yana bir joyda xalqaro medalga olib borgan mashqlar.
Har bir tugun bitta shunday lahzani bildiradi. Daraxt \(1\)-tugundan ildizlangan. Agar \(u\) tugun \(v\) tugunning ajdodi bo'lsa yoki \(u = v\) bo'lsa, \(u\) dan \(v\) gacha daraxt bo'ylab olingan yo'l o'quv yo'li deyiladi. Demak, bitta tugunning o'zi ham o'quv yo'li hisoblanadi.
Akademiyada \(m\) ta asosiy ko'nikma ajratilgan. Ularni \(0\) dan \(m-1\) gacha raqamlaymiz. Har bir tugunga \(x_i\) soni yozilgan. Bu sonning ikkilik yozuvi \(m\) ta ko'nikma haqida ma'lumot beradi: agar ikkilik yozuvdagi \(j\)-o'rin \(1\) bo'lsa, shu lahzada \(j\)-ko'nikma ishlatilgan; \(0\) bo'lsa, ishlatilmagan. O'rinlar o'ngdan chapga qarab \(0\) dan sanaladi. Bunday sonni ko'nikma kodi deb ataymiz.
Masalan, \(m=3\) bo'lsa, \(5\) soni ikkilikda \(101\). Bu \(0\)- va \(2\)-ko'nikmalar ishlatilganini, \(1\)-ko'nikma ishlatilmaganini bildiradi.
Bir nechta ko'nikma kodini birlashtirish quyidagicha bajariladi: har bir ko'nikma tanlangan kodlar ichida toq marta uchrasa, natijada shu o'rin \(1\), juft marta uchrasa \(0\) bo'ladi. Bu amal odatda XOR deb ataladi.
O'quv yo'lidagi istalgan tugunlar to'plamini (bo'sh to'plamni ham) tanlab, ularning ko'nikma kodlarini shu usulda birlashtirish mumkin. Bo'sh to'plam tanlansa, natija \(0\) bo'ladi.
O'quv yo'li to'liq deyiladi, agar shu yo'ldagi tugunlardan foydalanib \(0\) dan \(2^m - 1\) gacha bo'lgan barcha ko'nikma kodlarini hosil qilish mumkin bo'lsa.
To'liq o'quv yo'llari sonini toping.
Birinchi qatorda ikkita butun son \(n\) va \(m\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 1 \le m \le 20)\).
Ikkinchi qatorda \(n\) ta butun son \(x_1, x_2, \ldots, x_n\) beriladi \((0 \le x_i < 2^m)\). Bu sonlar tugunlardagi ko'nikma kodlari.
Keyingi \(n-1\) qatorda daraxt qirralari beriladi. Har bir qatorda ikkitadan butun son \(u\) va \(v\) yoziladi \((1 \le u,v \le n,\ u \ne v)\).
To'liq o'quv yo'llari sonini chiqaring.
Birinchi namunada \(m=2\), demak barcha kodlar \(0, 1, 2, 3\) bo'lishi kerak. \(1 \to 2\) yo'lida kodlar \(1\) va \(2\): hech narsa tanlanmasa \(0\), faqat \(1\) tanlansa \(1\), faqat \(2\) tanlansa \(2\), ikkalasi tanlansa \(3\) hosil bo'ladi. Demak, bu yo'l to'liq. Xuddi shunday, \(1 \to 2 \to 3\) va \(2 \to 3\) yo'llari ham to'liq. Jami \(3\) ta.
Ikkinchi namunada \(1 \to 2\) yo'lidagi kodlardan faqat \(0\) va \(1\) ni, \(1 \to 3\) yo'lidagi kodlardan esa faqat \(0\) va \(2\) ni hosil qilish mumkin. To'liq yo'l yo'q.
Uchinchi namunada \(m=1\), kerakli kodlar \(0\) va \(1\). \(2\)- yoki \(3\)-tugunni o'z ichiga olgan har bir o'quv yo'lida \(1\) kodi bor, shuning uchun ularning har biri to'liq: \(1 \to 2\), \(2\), \(1 \to 3\), \(3\). Jami \(4\) ta.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 2 1 2 3 1 2 2 3 |
3 |
| 2 |
3 2 0 1 2 1 2 1 3 |
0 |
| 3 |
3 1 0 1 1 1 2 1 3 |
4 |