A. Pozitsiyalar soni
Xotira: 16 MB, Vaqt: 1000 msAli va Vali bugun o'yin o'ynashga qaror qildi. Ushbu o'yinning bosh qahramoni Ali bo'lib u dastlab \(x = 0\) nuqtada joylashgan. Vali tomonidan Aliga \(n\) ta ikki turga mansub buyurq beriladi.
- \(L\) - chap pozitsiyaga siljish \(x=x-1\)
- \(R\) - o'ng pozitsiyaga siljish \(x=x+1\)
Ali bazi buyurqlarni bajarishni istamaydi(\(0\) yoki bir nechta). Misol uchun Vali \(LRLR\) buyurqlar ketma ketligini aytsa Ali quyidagi pozitsiyalarga siljishi mumkun(tagi chizilgan buyruqlarni Ali bajargan).
- LRLR - Ali chapga o'nga chapga o'nga va pozitsiyasi \(x=0\).
- LRLR - Ali hech bir buyruqni bajarmaydi va pozitsiyasi \(x=0\).
- LRLR - Ali chapga va yana chapga sijiydi va pozitsiyasi \(x=-2\).
Agar Ali barcha turli xil pozitsiyalarga yurib ko'rmoqchi bo'lsa jami bo'lib nechchi xil pozitsiyalarga o'tishi mumkun ekanligini hisoblang.
Birinchi satrda \(n(1\leq n\leq 10^5)\) buyruqlar soni va kiyingi satrda \(L\) va \(R\) dan tashkil topgan \(n\) ta belgidan tashkil topgan buyruq beriladi.
Ali jami bo'lib nechchi xil pozitsiyalarga siljish mumkunligini chop eting.
Birinchi testda Ali \([-2; 2]\) oralig'inng istalgan butun nuqtasiga siljishi mumkun shuning uchun jami pozitsiyalar soni \(5\).
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
4 LRLR |
5 |
B. Ikki quyon
Xotira: 16 MB, Vaqt: 1000 msRobocontest roundlaridan charchagan Adizbek parkda dam olishga qaror qildi. U skamekaga o'tirishi bilan yaqin atrofda ikki quyon bir biri tomonga sakrab kelayotganini ko'rdi.
Bu ikki quyonning joylashuvi gorizontal chiziqning butun koordinatalarida edi. Dastlab birinchi quyon \(x\) koordinatada bo'lsa ikkinchi quyon \(y\) koordinatada joylashgan\((x. Har soniyada quyonlar bir biri tomonga aniq bir marotaba sakraydi. Birinchisi \(a\) uzunlikka sakrasa ikkinchisi \(b\) uzunlikka sakraydi.
Adizbek hayron bo'ldi va bu ikki quyon bir vaqtning o'zida bitta butun koordinatada uchrashadimi, agar uchrashsa bu qancha soniya vaqtni oladi?
Adizbekga bu ikki quyon bir nuqtada uchrashishi uchun ketadigan soniyani hisoblashda yordam bering.
Kirish faylining dastlabki satrida testlar soni \(t(1\leq t\leq 1000)\) beriladi. Kiyingi \(t\) ta satrda \(x,y,a,b(0\leq x sonlari beriladi.
Har bir test uchun bitta butun sonni chop eting - ikki quyon bitta nuqtada uchrashishi uchun ketadigan soniyalar soni.
Agar buning iloji bo'lmasa -1 ni chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
5 0 10 2 3 0 10 3 3 900000000 1000000000 1 9999999 1 2 1 1 1 3 1 1 |
2 -1 10 -1 1 |
C. Jasurning sovg'asi #2
Xotira: 16 MB, Vaqt: 1000 msJasur singlisiga qizil, yashil va ko'k lampalardan('R', 'G' va 'B' - mos ravishda gulchambardagi lampalarning ranglari) gulchambar yasamoqchi ushbu gulchambarda bir xil rangli ikkita lampa ketma ket joylashib qolishini istamaydi(yodingizda saqlang gulchambarning boshi va oxirdagi lampa ranglari bir xil bo'lishi mumkun).
Masalan Jasurda \(3\) ta qizil \(3\) ta ko'k \(3\) ta yashil rangli lampa mavjud bo'lsa RGBRBGBGR ko'rinishi yasash mumkun.
Jasur sizga o'zdagi qizil yashil va ko'k lampalarning har biridan qancha miqdorda borligini aytadi sizning vazifangiz ushbu lampalarning barchasini ishlatgan holda u hoxlaganidek gulchambar yasash mumkunmi tekshirish.
Jasur ushbu sovg'asi bilan singlisini husand qilishni istaydi.
Kirish faylining dastlabki satrida \(t(1\leq t\leq 10^5)\) testlar soni beriladi. Kiyingi \(t\) ta satrda \(r, g, b(0\leq r,g,b\leq10^9)\) butun sonlar mos ravishda qizil, yashil va ko'k rangli lampalar soni.
Agar Jasur hoxlaganidek gulchambar yasashning imkoni bo'lsa 'yes' so'zini aks holda 'no' so'zini chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
3 3 3 3 1 10 2 2 1 1 |
yes no yes |
D. Pee and Mee
Xotira: 16 MB, Vaqt: 1000 msBaytlandiya mamlakatida Pee va Mee isimli ikki do'st yashaydi. Ular noodataviy dastur kodlarini yozishga judaham qiziqadi. Kunlarning birida ular shunday kod yozishdiki kodni \(i-\)bor ishga tushirganda \(i\) tub son bo'lsa 'Pee' so'zini aks holda 'Mee' so'zini chop etadi\((1\leq i\leq 200)\).
Sizga ham ushbu topshirib beriladi, siz bu ikki do'st yozgan dasturni siz ham yozaolasizmi?
Barcha testlarda ? belgisi beriladi, testlar soni 200 ta dan oshmaydi.
Siz yozgan kodni robocontest tizimi tekshirib kuradi \(i-\)bor ishga tushirganida agar \(i\) tub son bo'lsa 'Pee' so'zini aks holda 'Mee' so'zini chop etishi kerak.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
? |
Mee |
2 |
? |
Pee |
3 |
? |
Pee |
4 |
? |
Mee |
5 |
? |
Pee |
E. Maksimal segmentlar yig'indisi
Xotira: 512 MB, Vaqt: 3000 msQulmamat massivdagi so'rovlar haqidagi masalalarni juda yaxshi ko'radi.
Bir kun u juda mashhur masalaga duch keldi. \(n\) ta elementli \(a\) massiv beriladi va \(q\) ta \(l_i,r_i(1\leq l_i\leq r_i\leq n)\) so'rovlar mavjud. Har bir so'rovda massivning \(l_i-\) elementidan \(r_i-\) elementigacha bo'lgan barcha sonlarning yig'indisini hisoblash talab etiladi.
Bunday vazifa Qulmamatga juda zerikarli tuyildi. U surovlarga javob berishidan oldin massiv elementlarini aralashtirib, barcha so'rovlarga javoblar yig'indisi maksimal darajaga keltirishga qaror qildi. Sizning vazifangiz ushbu maksimal miqdorni hisoblashdan iborat.
Birinchi satrda ikkita \(n(1\leq n\leq 2000000)\) va \(q(1\leq q\leq 2000000)\) butun sonlar. Kiyingi satrda \(n\) ta \(a_i(-10^9\leq a_i\leq 10^9)\) massiv elementlari beriladi va kiyingi \(q\) satrda \(l_i,r_i(1\leq l_i\leq r_i\leq n)\) so'rovlari beriladi.
Yagona satrda masalani javobini \(-\) massiv elementlari tartibini o'zgartirganingizdan so'ng so'rovlarga javoblarning maksimal yig'indisini chop eting.
Birinchi testda [2, 3, 5] massivni [2, 5, 3] ko'rinishiga keltirsangiz so'rovlar \(a_{[1..2]}=2+5=7\) va \(a_{[2..3]}=5+3=8\) yig'indisi 15 ga teng.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
3 2 2 3 5 1 2 2 3 |
15 |
F. Crazy monster game #1
Xotira: 512 MB, Vaqt: 1000 msAzimjon crazy monster game o'yinini o'ynashni yoqtiradi. Ushbu o'ynda \(n\) ta monster ga qarshi jang olib borish kerak bo'ladi(monsterlar bitta chiziqda joylashgan).
Azimjon monsterlar ustidan g'alaba qozonishi uchun dastlab har bir monsterning umumiy kuchini aniqlab olishi kerak.
\(i-\)monsterning kuchi \(s_i\) ga teng, umumiy kuchi esa \(i-\)monsterdan ko'pi bilan \(r\) masofadagi monsterlar kuchlari yig'indisiga teng.
Sizning vazifangiz har bir monster uchun umumiy kuchini aniqlashdan iborat.
Kirish faylining dastlabkis satrida \(n, r(1\leq n\leq 10^6, 0\leq r\leq n)\) butun sonlar. Kiyingi satrda \(n\) son \(s_i(1\leq s_i\leq 10^9)\) monsterlar kuchlari beriladi.
Har bir monsterning umumiy kuchlarini bitta satrda chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
4 1 1 1 1 1 |
2 3 3 2 |
G. Crazy monster game #2
Xotira: 64 MB, Vaqt: 1000 msAzimjon crazy monster game o'yinini o'ynashni yoqtiradi. Ushbu o'ynda \(n\) ta monster ga qarshi jang olib borish kerak bo'ladi(monsterlar bitta chiziqda joylashgan).
Azimjon monsterlar ustidan g'alaba qozonishi uchun dastlab har bir monsterning umumiy kuchini aniqlab olishi kerak. \(i-\)monsterning kuchi \(s_i\) ga teng, umumiy kuchi esa \(i-\)monsterdan ko'pi bilan \(r\) masofadagi monsterlar kuchlari yig'indisiga teng.
Har bir monsterni umumiy kuchini aniqlab bo'lgach Azimjon jang qilishga hozirlanadi va Azimjonning dastlabki kuchi \(h\) ga teng. Agar \(i-\)monsterning umumiy kuchidan Azimjonning kuchi kam bo'lmasa \(i-\)monster ustidan g'alaba qozonadi(Azimjon istalgan monster bilan jangga kirishi mumkun deb qaralsin va u bir vaqtda bir nechta monsterlar bilan jang qilmaydi) va \(s_i\) bonusga ega bo'ladi, uning kuchi \(h=h+s_i\) ga ortadi. Aks holda mag'lubiyatga uchraydi.
Bu o'yinda Azimjon g'alaba qozonadimi buni aniqlashda unga yordam bering.
Kirish faylining dastlabkis satrida \(n, r, h(1\leq n\leq 10^6, 0\leq r\leq n,0\leq h\leq 10^9)\) butun sonlar. Kiyingi satrda \(n\) son \(s_i(1\leq s_i\leq 10^9)\) monsterlar kuchlari beriladi.
Agar o'yinda Azimjon g'alaba qozonsa "Next level" so'zini va jami to'plagan achkosini bitta satrda probil bilan ajratilgan holda chop eting. Aks holda "Game over" so'zini chop eting.
Birinchi testda monsterlar kuchlari \([1,0,100]\) ga teng bo'lsa umumiy kuchlari \([1,101,100]\) ga teng. Azimjon dastlab birinchi monster bilan janga kiradi\((1\leq99)\) va uni mag'lubiyatga uchratib 1 bonsuga ega bo'ladi \(99+1\). Endi u uchinchi monster bilan jang qiladi\((100\leq100)\) va 100 bonusga ega bo'ladi \(100+100\). Nihoyat oxirgi monsterni mag'lubiyatga \((101\leq200)\) uchratadi \(200+0\). Jami bonuslari \(200\).
Ikkinchi testda monsterlar kuchlari \([1,1,100]\) ga teng bo'lsa umumiy kuchlari \([2,102,101]\) ga teng. Azimjon birinchi monster bilan jang qiladi\((2\leq 99)\) va uni mag'lubiyatga uchratib 1 bonusga ega bp'ladi \(99+1\). Endi uning kuchi \(100\) ga teng ammo qolgan ikki monster umumiy kuchlaridan kichik bo'lganligi uchun o'yinda mag'lubiyatga uchraydi.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
3 1 99 1 0 100 |
Next level 200 |
2 |
3 1 99 1 1 100 |
Game over |