A. Pozitsiyalar soni

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ali 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Ali jami bo'lib nechchi xil pozitsiyalarga siljish mumkunligini chop eting.

Izoh:

Birinchi testda Ali $[-2; 2]$ oralig'inng istalgan butun nuqtasiga siljishi mumkun shuning uchun jami pozitsiyalar soni $5$ .

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 LRLR	5

B. Ikki quyon

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Robocontest 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.

Sample-images

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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

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.

Misollar:

#	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 ms

Masala

Jasur 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Agar Jasur hoxlaganidek gulchambar yasashning imkoni bo'lsa 'yes' so'zini aks holda 'no' so'zini chop eting.

Misollar:

#	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 ms

Masala

Baytlandiya 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?

Kiruvchi ma'lumotlar:

Barcha testlarda ? belgisi beriladi, testlar soni 200 ta dan oshmaydi.

Chiquvchi ma'lumotlar:

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.

Misollar:


Mee
Pee
Pee
Mee
Pee

#	INPUT.TXT	OUTPUT.TXT
1	?	Mee
2	?	Pee
3	?	Pee
4	?	Mee
5	?	Pee

E. Maksimal segmentlar yig'indisi

Xotira: 512 MB, Vaqt: 3000 ms

Masala

Qulmamat 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Yagona satrda masalani javobini $-$ massiv elementlari tartibini o'zgartirganingizdan so'ng so'rovlarga javoblarning maksimal yig'indisini chop eting.

Izoh:

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.

Misollar:

#	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 ms

Masala

Azimjon 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir monsterning umumiy kuchlarini bitta satrda chop eting.

Misollar:

#	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 ms

Masala

Azimjon 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

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.

Izoh:

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.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 99 1 0 100	Next level 200
2	3 1 99 1 1 100	Game over