A. 0 va 1 lik satr

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga \(0\) va \(1\) dan tashkil topgan \(S\) satr beriladi. \(S\) satrning qisim satri deb \(S_i+S_{i+1}+...+S_j(0\leq i\leq j\leq|S|-1)\) ko'rinishidagi satrga aytiladi.

Sizning vazifangiz \(S\) satrning \(0\) lar soni \(1\) lar soniga teng qisim satrilari ichida eng uzun qisim satrni uzunligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida \(S(1\leq |S|\leq 10^5)\) satr beriladi. Satr faqatgina \(0\) va \(1\) dan tashkil topgan.

Chiquvchi ma'lumotlar:

Agar birortaham bunday qisim satr mavjud bo'lmasa \(0\) ni aks holda \(0\) lar soni \(1\) lar soniga teng eng uzun qisim satr uzunligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	0000101	4
2	11111	0

B. Massiv va almashtirish

Xotira: 64 MB, Vaqt: 1000 ms

Masala

\(N\) ta elementdan tashkil topga \(a\) massiv berilgan. Massiv elementlari \(1\) dan \(N\) gacha sonlarning biror primutatsiyasidir. Sizga qo'shimcha \(0\) va \(1\) dan tashkil topgan \(S\) satr ham beriladi. Agar \(S_i(1\leq i \leq N-1)\) ning qiymati \(1\) ga teng bo'lsa \(a_i-\)element bilan \(a_{i+1} -\)elementlarning o'rnini almashtirishingiz mumkun(0 marotaba yoki istalgancha), aks holda o'zgartirishning imkoni yo'q.

Sizning vazifangiz ushbu massivning elementlarini o'sish tartibida tartiblashning iloji bormi yo'qmi tekshirishdan iborar.

Kiruvchi ma'lumotlar:

Birinchi satrda \(N(1\leq N\leq 200000)\) massiv elementlari soni.
Ikkinchi satrda \(N\) ta son \(a_i(1\leq a_i \leq N)\), \(1\) dan \(N\) gacha sonlar primutatsiyasi.
Uchunchi satrda \(S(|S|=N-1)\) \(0\) va \(1\) dan iborat satr beriladi.

Chiquvchi ma'lumotlar:

Agar massivni elementlarini o'sish bo'yicha tartiblashning iloji bo'lsa "Yes" so'zini, aks holda "No" so'zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 2 1 3 4 101	Yes
2	4 2 1 3 4 011	No

C. Jasurning sovg'asi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Jasur yangi yil uchun singlisiga qizil, yashil va ko'k rangli lampalardan gulchambar yasadi \(i-\)lampa \(s_i\)('R', 'G' va 'B' - gulchambardagi lampalarning ranglarini) ifodalaydi. Singlisi ushbu gulchambar oddiy bo'lishini hoxlamaydi. Uning aytishicha \(s_i=s_j\) va \(|i-j|\) mod \(3=0\) bo'lsa ushbu gulchambar ajoyib hisoblanadi.

sample-images

Endi Jasur ushbu gulchambar lampalarini shunday bo'yab chiqmoqchiki bo'yashdan so'ng gulchambar uning singlisi hoxlaganidek gulchambar bo'lishi kerak.
Sizning vazifangiz Jasur eng kamida nechta lampani bo'yash orqali singlisi hoxlaganidek gulchambarga keltirish kerak ekanligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida \(s(1\leq |s|\leq 200000)\) satr beriladi. Ushbu satr 'R', 'G' va 'B' belgilardan tashkil topgan bo'lib, gulchambarning lampa ranglarini ifodalaydi mos ravishda qizil, yashil va ko'k.

Chiquvchi ma'lumotlar:

Jasur gulchambarni singilisi hoxlaganidek ko'rinishiga keltirishi uchun minimal bo'yash kerak bo'lgan lampalar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	BGGG	2
2	RGB	0

D. Massiv va progressiya

Xotira: 16 MB, Vaqt: 3000 ms

Masala

Sizga \(n\) ta elementli \(a\) massiv va \(q\) ta so'rov beriladi har bir so'rovda \(l\), \(r\) va \(d\) sonlari beriladi. Sizning vazifangiz har bir so'rovda massivning \([l, r](a_l=a_l+d, a_{l+1}=a_{l+1}+2d,...,a_{r}=a_r+(r-l+1)*d)\) oralig'idagi elementlariga arifmetik progressiyaning elementlarini qo'shish talab etiladi.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida \(n(1\leq n\leq 10^6)\) natural son massiv elementlari soni.
Ikkinchi satrda \(n\) ta butun son \(a_i(-10^5\leq a_i\leq 10^5)\) massiv elementlari beriladi.
Uchinchi satrda \(q(1\leq q\leq 10^6)\) natural son so'rovlar soni beriladi va kiyingi \(q\) ta satrda \(l_i,r_i,d_i(1\leq l_i\leq r_i\leq n, -10^5\leq d_i\leq 10^5)\) butun sonlar beriladi.

Chiquvchi ma'lumotlar:

Barcha so'rovlarni bajarib bo'lganingizdan so'ng hosil bo'lgan massivni chop eting. Massiv elementlarini bitta satrda probil bilan ajratilgan holda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 10 20 3 1 2 6 1 1 15 1 2 -1	30 30
2	5 1 2 3 4 -5 3 5 5 10 1 5 4 2 3 -1	5 9 13 20 25

E. Santa Claus

Xotira: 32 MB, Vaqt: 3000 ms

Masala

Yangi yilda Santa Claus bolakaylarga har yilgidan o'zgacha sovg'a ulashish istagida bolakaylarga xar xil turdagi kitoblarni sovg'a qilmoqchi.
Santa Clous ning \(1\) dan \(n\) gacha raqamlangan kitob javoni bor \(i-\)javonda \(S_i\) ta kitob ma'vjud. Barcha kitoblar Santaning chang'isiga sig'maydi shuning uchun u quyidagi qonuniyat asosida kitoblarni ma'lum qismini navbat bilan ajratib olib tarqatishga qaror qildi.

Har safar Santa Clous yo'lga chiqishidan oldin kitoblarni quyidagicha yig'ib oladi:

Santa \(i-\)javondan\((S_i>1)\) \(1\) ta kitob oladi;
\(i\) ning yangi qiymati uchun \(i=i+S_i\) ni tanlaydi;
Ushbu jarayon \(n < i\) bo'lguncha davom etadi.

Sizning vazifangiz Santa Clousning barcha javonlarida 1 tadan kitob qolishi uchun eng kamida nechchi marotaba sovg'alarni tarqatishi uchun junab ketishini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida \(t(1\leq t\leq 500)\) testlar soni beriladi;
Kiyingi satrlarda testlar beriladi har bir testning birinchi satrida \(n(1\leq n\leq 5000)\) Santaning javonlari soni va kiyingi satrda \(n\) tadan son \(S_i(1\leq S_i\leq 10^9)\) \(i-\)javonda nechta kitob borligini anglatadi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida satrlarda Santa Clous kamida nechchi marotaba sovg'alarni ulashgani yo'lga chiqishini chop eting.

Izoh:

\(1-\)testda: Javonda \([4,2,2,2]\) kitoblar joylashgan.
Santa \(i=2\) ikkinchi javondan kitob olishni boshlaydi va kiyingi kitobni \(i+S_i=4-\)javondan oladi. Javondagi kitoblar \([4,1,2,1]\).
Kiyingi qadamlarda
[4, 1, 2, 1]  \(1-\)javondan;
[3, 1, 2, 1]  \(1-\)javondan;
[2, 1, 2, 1] \(1\) va \(3\)  javonlardan oladi. Nateja [1, 1, 1, 1] jami bo'lib 4 marotaba.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 4 2 2 2 2 1 1 4 4 3 2 1	4 0 5

F. Azimjonning roboti

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Azimjon bir nuqtadan ikkinchi nuqtaga olib boruvchi yo'llar ichida eng qisqa yo'ldan harakatlanaoladigan robot yaratdi. Robot ikki o'lchamli koordinata sestemasida harakat qiladi va harakati mobaynida yo'l xaritasini chizib boradi.

Koordinatalar sestimasida judaham ko'p to'siqlar mavjud, ammo robot to'siq yo'q koordinatalarda harakatlanadi. Robotning judaham ko'p chizgan yo'l xaritalari ma'vjud bo'lib ushbu xaritalardan biri sizga beriladi. Sizning vazifangiz robot eng qisqa yo'ldan harakatlanganmi yoki yo'qmi tekshirishdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida \(s(1\leq |s|\leq 100)\) robot harakat xaritasi beriladi. Robot dastlab \((x, y)\) koordinatada joylashgan bo'lsa kiyingi ko'chish koordinatasi \((x,y+1), (x, y-1), (x+1, y)\) va \((x-1, y)\) nuqtalardan biri bo'lishi mumkun va bu nuqtalarni mos ravishda quyidagi \(R, L, U, D\) to'rtta belgi asosida yozib boradi.

Chiquvchi ma'lumotlar:

Agar Azimjonning roboti bir nuqtadan ikkinchi nuqtaga eng qisqa yo'ldan harakatlangan bo'lsa OK so'zini, aks holda WR so'zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	LLU	OK
2	LLURD	WR

G. Labirintdagi sichqon

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga \(n\) soni va \(n\times n\) o`lchamli faqat \(0\) va \(1\) lardan tashkil topgan matritsa beriladi. Sichqon matritsaning \((1, 1)\) nuqtasidan \((n, n)\) nuqtasiga borishi kerak. Matritsadagi \(1\) bu yo`l bor degani \(0\) esa yo`l yo'q degani. Shichqon labirintdan chiqib ketishi uchun unga yo`l ko`rsating \(U\)-yuqoriga, \(D\)-pastga, \(L\)-chapda, \(R\)-o'ngda. Shichqonga labirintdan chiqishiga ko`maklashing.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n(1\leq n\leq 5)\) natural son.
Ikkinchi qatorda \(0\) va \(1\) dan tashkil topgan \(n\times n\) matritsa kiritiladi

Chiquvchi ma'lumotlar:

Agar sichqonning labirintdan chiqish yo`llari bir nechta bo'lsa leksikografik jihatdan o'sish tartibida bitta satirda probil bilan ajratilgan holda chop eting, agar yo'l ma'vjud bo'lmasa \(-1\) ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 1 0 0 1 1 0 1 1	RDDR RDRD
2	3 1 1 0 0 1 0 1 0 1	-1

H. Factorial and Gcd

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga ikkita \(a\) va \(b\) sonlari beriladi. Sizning vazifangiz \(gcd(a!, b!)\) ni hisoblashdan iborat.

Bu yerda \(n!=1*2*..*n\) va \(gcd(a,b)\) ikki sonning eng katta umumiy bo'luvchisini hisoblaydi.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita \(a,b(1\leq a,b\leq 10^9,min(a,b)\leq12)\) natural sonlari beriladi.

Chiquvchi ma'lumotlar:

Yagona satrda masalaning javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3	6

I. Ikki do'st va konfetlar #1

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ali va Vali do'stlar bugun bayram bo'lganligi uchun bir birini hursand qilmoqchi. Alida \(a\) ta konfet, Valida \(b\) ta konfet bor.

Ali o'zidagi konfetlardan do'sti Valiga 1 ta konfet beradi Vali esa konfetlaridan Aliga 2 ta konfet beradi, Ali Valiga 3 ta konfet beradi va bu ish navbat bilan takrorlanadi har gal konfetlar soni bittaga orttirilib do'stiga beriladi(do'stlar bir birlaridan olgan konfetlarini o'zlaring konfetlariga qo'shmaydi).

Sizning vazifangiz ikki do'stdan qay birning navbati kelganda do'stiga yetarlicha konfet beraolmasligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita \(a,b(1\leq a,b\leq 10^9)\) natural sonlari beriladi.

Chiquvchi ma'lumotlar:

Ikki('Ali' va 'Vali') do'stdan qay birining navbati kelganda yetarlicha konfet beraolmasa usha do'stning ismini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 1	Vali
2	5 7	Ali

J. Ikki do'st va konfetlar #2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Ali va Vali do'stlar bugun bayram bo'lganligi uchun bir birini hursand qilmoqchi. Alida \(a\) ta konfet, Valida \(b\) ta konfet bor.

Ali o'zidagi konfetlardan do'sti Valiga 1 ta konfet beradi Vali esa konfetlaridan Aliga 2 ta konfet beradi, Ali Valiga 3 ta konfet beradi va bu ish navbat bilan takrorlanadi har gal konfetlar soni bittaga orttirilib do'stiga beriladi(do'stlar bir birlaridan olgan konfetlarini o'zlaring konfetlariga qo'shib oladi).

Sizning vazifangiz ikki do'stdan qay birning navbati kelganda do'stiga yetarlicha konfet beraolmasligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita \(a,b(1\leq a,b\leq 10^5)\) natural sonlari beriladi.

Chiquvchi ma'lumotlar:

Ikki('Ali' va 'Vali') do'stdan qay birining navbati kelganda yetarlicha konfet beraolmasa usha do'stning ismini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 1	Ali
2	4 3	Vali

K. Massivga son qo'shish

Xotira: 16 MB, Vaqt: 3000 ms

Masala

Sizga \(n\) ta elementli \(a\) massiv va \(q\) ta so'rov beriladi har bir so'rovda \(l\), \(r\) va \(x\) sonlari beriladi. Sizning vazifangiz har bir so'rovda massivning \([l, r](a_i=a_i+x, l\leq i\leq r)\) oralig'idagi elementlariga \(x\) sonini qo'shish talab etiladi.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida \(n(1\leq n\leq 10^6)\) natural son massiv elementlari soni.
Ikkinchi satrda \(n\) ta butun son \(a_i(-10^9\leq a_i\leq 10^9)\) massiv elementlari beriladi.
Uchinchi satrda \(q(1\leq q\leq 10^6)\) natural son so'rovlar soni beriladi va kiyingi \(q\) ta satrda \(l_i,r_i,x_i(1\leq l_i\leq r_i\leq n, -10^9\leq x_i\leq 10^9)\) butun sonlar beriladi.

Chiquvchi ma'lumotlar:

Barcha so'rovlarni bajarib bo'lganingizdan so'ng hosil bo'lgan massivni chop eting. Massiv elementlarini bitta satrda probil bilan ajratilgan holda chop eting .

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 100 3 1 1 10 1 1 -3 1 1 20	127
2	2 0 0 5 1 1 100 1 2 -100 2 2 10 1 1 20 1 2 -30	-10 -120