A. Yuklar
Xotira: 64 MB, Vaqt: 1000 msSunnat online xaridlarni yoqtiradi. Yaqin \(10^9\)kun ichida pochta markaziga Sunnatning nomiga \(n\) ta yuk kelishi kerak. Keling keyingi \(10^9\)kunlarni raqamlaylik: 1-kun, 2-kun, ..., \(10^9\)-kun. \(i\)-yuk pochta markaziga \(l_i\)-kun keladi, va bu yukni pochta markazidan olib ketish uchun oxirgi kun \(r_i\)-kundir. Bu degani, Sunnat usbhu yukni \(x\)-kun olib ketoladi, agarda \(l_i \leq x \leq r_i\) sharti bajarilsa. Sunnat pochta markaziga bir marta kelganida uyiga eng ko'pi bilan \(k\) tagacha yuk olib ketoladi. E'tibor bering, Sunnat bir kun davomida pochta markaziga bir necha marta borib kelishi mumkin. Sunnat minimal necha marta pochto markaziga borgan holda, barcha yuklarini uyiga olib keta oladi.
Birinchi qatorda bitat butun son - \(T(1 \leq T \leq 3000)\) testlar soni kiritiladi.
Har bitta test uchun birinchi qatorda \(n\) va \(k(1 \leq k \leq n \leq 100000)\) kiritiladi. Keyingi \(n\) ta qatorning har bitida ikkita butun son \(l_i\) va \(r_i(1 \leq l_i \leq r_i \leq 10^9)\) kiritiladi.
Barcha testlar kesimida \(n\) larning summasi \(10^6\) dan oshmasligi kafolatlanadi.
Har bitta test uchun alohida qatoda, Sunnat pochta markazida eng kamida necha marta borishi kerakligini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 6 2 3 8 6 7 4 7 2 4 1 3 2 4 |
3 |
| 2 |
1 4 2 1 3 2 4 6 7 4 7 |
2 |
B. Noto'g'ri yig'indi
Xotira: 512 MB, Vaqt: 3000 msSobirjonda uzunligi \(n\) ga teng \(arr\) butun sonlar massivi bor. Sobirjon shunday ikkita \(i,j(i \neq j)\) sonlar olmoqchiki, \(arr[i] + arr[j]\) yig'indi maksimal bo'lsin.
Ammo muammo shundaki, Sobirjon qo'shish amalini xato bajaradi. U sonlarni qo'shganda xona ko'chisini inobatga olmaydi. Ya'ni qaysidir xonalar uchun, shu xonalardagi raqamlar yig'indisi 9 dan oshsa ham, 1 ni yodda saqlamaydi, keyingi razryadga ta'sir qildirmaydi. Aniq misollar bilan tushuntirgan quyroq.
5 + 5 = 0; 23+17 = 30; 354 + 168 = 412; 55 + 55 = 0; 9+11 = 10;
1000023 + 1070099 = 2070012; 12 + 7 = 19; 9 + 7 = 6; 124 + 123 = 247;
Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 10)\) testlar soni kiritiladi.
Keyin har bir test uchun alohida, birinchi qatorda butun son - \(n(1 \leq n \leq 2 * 10^5)\) kitiriladi. Keyingi qatorda \(n\) ta butun son, \(arr\) massivi elementlar kiritiladi. Sonlar \(0..10^9\) oralig'ida ekanligi kafolatlanadi.
Barcha testlar kesimida \(n\) larning summasi \(10^6\) dan oshmasligi kafolatlanadi.
Har bir test uchun alohida qatorda, uchta butun son chiqaring:
maksimal \(arr[i] + arr[j]\) yig'indini, \(i\) va \(j\) ni. To'g'ri keluvchi \((i, j)\) lar juftligi bir nechta bo'lsa, oldin \(i\) ni minimallashtirishga harakat qiling, so'ngra \(j\) ni minimallashtirishting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 3 12 9 7 2 55 55 4 155 55 955 555 |
19 1 3 0 1 2 900 2 3 |
C. Codeforces EDU
Xotira: 32 MB, Vaqt: 1000 msCodeforcesning EDU bo'limida juda qiziqarli mavzularga oid darslar va mashq uchun masalalar mavjud.
Shu mavzulardan birini ochib, Yakuniy Natijalar bo'limiga kirsak, quyidagiga o'xshash rasmni ko'ramiz:
E'tibor bersangiz, 1-qism mashg'ulotda 3 ta masala bo'lgan; A, B va C. 2-qism mashg'ulotda 3 ta masala bo'gan: A, B, C va D. Hamda umumiy natijalar jadvalida, bu masalalar aynan shu ketma-ketlikda berilgan.
Sizga umumiy natijalardagi masalalar ketma ketligi beriladi, sizning vazifangiz mashg'ulot necha qismga bo'linganligini topishdir.
Yagona qatorda bitta satr, yakuniy natijalardagi masalalarning harflari ketma ketligi.
Satrning uzunligi \(10^5\) dan oshmaydi.
Mashg'ulot necha qismga bo'linganligini toping.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
ABCABAABCDEFABC |
5 |
| 2 |
ABCABCDABCDEABCDE |
4 |
D. ReLU
Xotira: 512 MB, Vaqt: 3000 msUzunligi \(n\) ga teng ikkita \(A\) va \(B\) massivi bor. Massivlar hozir 0 lar bilan to'ldirilgan.
Sizga jami \(Q\) ta 3 xil turgagi so'rov beriladi, siz ularni bajarishingiz lozim.
- \(1 \ l \ r \ c\): barcha \(l \leq i \leq r\) uchun oldin \(a[i] \leftarrow a[i] + c\) qiling, so'ngra \(b[i] \leftarrow max(b[i], a[i])\)qiling.
- \(2 \ l \ r \ d\): barcha \(l \leq i \leq r\) uchun oldin \(a[i] \leftarrow max(a[i], d)\) qiling, so'ngra \(b[i] \leftarrow max(b[i], a[i])\)qiling.
- \(3 \ l \ r\): ekranga yangi qatordan \(max(b[l], b[l+1], \dots b[r])\) ni chiqaring.
Birinchi qatorda ikkita butun son, \(n\) va \(q(1 \leq n,q \leq 5 * 10^5)\) kiritiladi.
Keyingi \(q\) ta qatorning har birida so'rovlar masala shartida ko'rsatilgan formatda kiritiladi. Bunda \(1 \leq l \leq r \leq n\), \(c \leq |10^6|\) va \(d \leq |10^{12}|\).
Har bir qatordan alohida 3-turdagi so'rovlarning natijasini chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
13 10 1 1 2 2 3 3 4 2 1 11 1 3 7 12 1 1 6 -100 2 2 6 100 3 3 13 3 6 10 2 2 7 144 3 4 8 |
0 1 100 100 144 |
E. 3 ta har xil belgi
Xotira: 32 MB, Vaqt: 1000 msRavshanjonda ajoyib satr bor. Satrning ajoyibligi shundaki, u 3 xil harfdan tashkil topgan va har bir harf aynan 3 martadan bu satrda qatnashgan. U satrdagi belgilarning barchasini o'chirmoqchi. Ravshanjon bir o'chirishda, ketma-ket bir kelgan bir xil belgilarni o'chira oladi. Agar u bir urinishda ketma ket 3 ta harfni o'chira olsa, xursandligi 1 ga ortadi.
Masalan abbacbcca satrida Ravshanjon quyidagicha ish tutadi: abbacbcca ni o'chiradi. Ammo bunda uning xursandligi oshmaydi. Keyingi safar aacbcca ni ochiradi va bunda ham xursandligi ortmaydi. Keyingi safar aaccca ni o'chiradi va xursandligini 1 ga oshiradi. Eng oxirida aaa ni o'chiradi va xursandligini yana 1 ga oshiradi.
Natijada Ravshanjon xursandligini 2 birlikka ga oshirdi.
Ravshanjon erishishi mumkin bo'lgan maksimal xursandlikni toping.
Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 100)\) testlar soni kiritiladi.
Har bir test uchun alohida qatorda uzunligi 9 ga teng bitta satr beriladi. Satr ingliz alifbosining 3 ta kichik harflaridan iborat va har bir harf satrda 3 marta ishtirok etgan.
Har bir test uchun alohida qatorda Ravshanjonning xursandchiligi maksimal necha marta oshishini toping.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 hhhlllkkk sssrrtrtt ababccacb abcabcabc pqrrprqqp |
3 2 2 1 2 |
F. Bir o'lchovli labirint
Xotira: 32 MB, Vaqt: 1000 msDilshod xonalari \(1\) dan \(n\) gacha raqamlangan bir o'lchovli labirintda adashib qoldi. Hozirda u labirintning \(k\)-xonasida turibdi va labirindan chiqish uchun \(1\)-yoki \(n\)-xonalardan biriga borishi kerak . Dilshod o'z istagi bilan yura olmaydi, shuning uchun ham turgan xonasining belgisilga qarab yuradi.
- \(L\) belgili xonada turgan bo'lsa hozirgi turgan xonasidan qo'shni chap xonaga o'ta oladi.
- \(R\) belgili xonada turgan bo'lsa hozirgi turgan xonasidan qo'shni o'ng xonaga o'ta oladi.
Harakat qilishni boshlashdan oldin, Dilshod istalgan xonalarining belgilarini almashtira oladi. U minimal nechta almashtirishlar yordamida labirintdan chiqib keta oladi?
Birinchi qatorda bitta butun son - \(T\) testlar soni kiritiladi.
Keyingi qatordan boshlab har bir test uchun alohida, birinchi qatorda \(n(1 \leq n \leq 2 * 10^5)\)labirintdagi xonalar soni va \(k(1 < k < n)\) hozirda Dilshod turgan xonaning tartib raqami kiritiladi. Ikkinchi qatorda esa bitta satr, labirintdagi xonalarning belgilar kiritiladi.
Barcha testlar kesimida \(n\)larning yig'indisi \(10^6\) dan oshmaydi.
Har bir test uchun alohida qatorda, DIlshod minimal nechta o'zgartirishlar yordamida labirintdan chiqib ketishini toping.
1-testda, Dilshod labirintning 3-xonasid turibdi. 1 ta belgini o'zgartirish yordamida labirintni RLLRLR ko'rinishiga olib keladi.
So'ng quyidagicha harakat qiladi: RLLRLR → RLLRLR → RLLRL
1-raqamli xonaga kelib bo'lgach, Labirintdan chiqib ketadi.
2-testda faqat chapga yurgan holda labirintdan chiqib ketadi.
3-testda esa Dilshod oldin satrni LRLRRRRL ga o'zgartiradi.
So'ng quyidagicha harakat qiladi: LRLRRRRL → LRLRRRRL → LRLRRRRL → LRLRRRRL → LRLRRRRL. Oxirgi xonaga kelgach, labirintdan chiqib ketadi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 6 3 RLRRLR 4 2 LLRR 8 4 LRLRRLLL |
1 0 2 |