A. Teng juftlik

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga ikkita butun son $a$ va $b$ berilgan.

Bir urinishda siz 1 dan 10 gacha bo'lgan bitta butun $k$ sonni tanlashingiz va uni $a$ ga qo'shishingiz yoki $a$ dan ayirishingiz mumkin. Boshqacha qilib aytganda, siz $k∈[1;10]$ butun sonni tanlaysiz va $a:=a+k$ yoki $a:=a−k$ bajarasiz. Har urinishda $k$ ning turli qiymatlaridan foydalanishingiz mumkin.

Sizning vazifangiz $a$ ni $b$ ga teng qilish uchun zarur bo'lgan minimal urinishlar sonini topishdir.

Kiruvchi ma'lumotlar:

Yagona qatorda ikkita butun son $a$ va $b$ beriladi $(1≤a,b≤10^9)$

Chiquvchi ma'lumotlar:

$a$ ni $b$ ga teng qilish uchun ketadigan minimal urinishlar sonini chiqarib bering.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 5	0
2	13 42	3

B. Bo'sh massiv

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizga faqat 0 va 1 lardan tashkil topgan massiv beriladi. Siz quyidagi amalni istalgancha bajara olasiz.

Massivning istalgan kamaymaydigan tartibdagi prefixni tanlab uni o'chirish.

Sizning vazifangiz shu massivni iloji boricha kam amal bajarish orqali bo'sh holatga keltirish

Kiruvchi ma'lumotlar:

Birinchi qatorda testlar sonini ifodalovchi $T$ soni kiritiladi. $(1 ≤ T ≤ 20000)$
Har bir testning birinchi qatorida $N$ - massivdagi elementlar soni. $(1 ≤ N ≤ 200000)$
Har bir testning ikkinchi qatorida faqat 0 yoki 1 dan iborat $N$ ta son kiritiladi.
$N$ ning barcha testlardagi yig'indisi 200000 dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir test uchun massivni o'chirish uchun ketadigan minimal amallar sonini chiqaring

Misollar:

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

C. Oraliqdagi EKUB

Xotira: 64 MB, Vaqt: 1000 ms

Masala

$\text{EKUB(a,b)}$ deb $a$ va $b$ qoldiqsiz bo’linadigan eng katta songa aytiladi. $\text{EKUB}$ ni hisoblashning bir nechta algoritmlari bor. Masalan Yevklid algoritmi.

Bu masalada sizga oraliq $l$ va $r$ beriladi. siz shunday eng katta son $d$ ni topishingiz kerakki, shu oraliqdagi hamma sonlar $(l,l+1,l+2 … r-1, r)$ $d$ ga qoldiqsiz bo’linsin.

Kiruvchi ma'lumotlar:

Yagona qatorda $l$ va $r$ beriladi. $(1 ≤ l ≤ r ≤ 10^{100})$

Chiquvchi ma'lumotlar:

Yagona qatorda shu oraliqdagi barcha sonlarning EKUBini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2	1
2	2 2	2

D. Quvnoq "zoo"

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Berilgan so'z "zoo" ga o'xshash bo'ladi agar undagi 'z' lar soni 'o' lar sonidan aynan 2 marta kam bo'lsa.

Misol uchun "zzzoooooo" va "zzoooo" so'zlari "zoo" ga o'xshash ammo "zzooo" kabi so'zlar o'xshash emas.

Sizning vazifangiz berilgan so'z "zoo" ga o'xshashmi yoki yo'qmi, shuni aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qator: bir nechta 'z' bilan boshlanib, bir nechta 'o' bilan tugaydigan so‘z.
(So'zning uzunligi 50 ta belgidan oshmaydi.)

Chiquvchi ma'lumotlar:

Agar so'z "zoo" ga o'xshash bo'lsa Yes aks holda No yozuvini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	zzzoooooo	Yes

E. Anvar va uning bank hisobi

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Anvar juda aqlli bola. U hatto o'zining bank hisobiga ega. Bank hisobining holati butun sondir. Bank hisobining holati manfiy son bo'lishi ham mumkin. Bu hisob egasi bankdan qarzdorligini bildiradi.

Anvar yaqinda tug'ilgan kunini o'tkazdi, shuning uchun u juda ko'p sovg'alar oldi. Ulardan biri o'z bank hisob varag'ining holatidan oxirgi yoki oxirgi raqamni bir martadan ko'p bo'lmagan holda o'chirish imkoniyatidir. Misol uchun, agar Anvarning bankdagi hisobining holati -123 bo'lsa, Anvar oxirgi raqamni o'chirib tashlab, hisobidagi balansini -12 ga tenglashtirishi mumkin, shuningdek, oxirgi raqamdan oldingi raqamni olib tashlashi va hisob balansi -13 ga teng bo'lishi ham mumkin.

Anvar matematikada unchalik yaxshi emas va shuning uchun u sizdan bank hisobini maksimal darajada oshirishga yordam berishingizni so'raydi. Bank sovg'asi yordamida olinishi mumkin bo'lgan bank hisobining maksimal miqdorini toping.

Kiruvchi ma'lumotlar:

Yagona qatorda $n (10 ≤ |n| ≤ 10^9)$ butun soni mavjud - Anvarning bank hisobi holati.

Chiquvchi ma'lumotlar:

Bitta qatorda butun sonni chop eting - Anvar olishi mumkin bo'lgan bank hisobining maksimal holati.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2230	2230
2	-123	-12
3	-10	0

F. Eng katta antipalindrom

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Agar satr chapdan o'ngga va o'ngdan chapga bir xil o'qilsa, palindrom hisoblanadi. Masalan, “kek”, “abacaba”, “r” va “papicipap” satrlari palindrom, “abb” va “iq” satrlar esa palindrom emas.
Satrning qism-satri deb satrning ichidan qirqib olingan satrga aytiladi. Misol uchun “kek” satrining qism-satrlari quyidagilar hisoblanadi:
“k”, “e”, “ke”, “ek” va “kek”, lekin “kk” qism-satr hisoblanmaydi.
Nodir palindrom so’zlarni yoqtirmaydi. Shuning uchun u barcha palindrom so’zlarni shu so’zning iloji boricha uzun bo’lgan va palindom bo'lmagan qism-satriga o’zgartirmoqchi. U bu ishni qilish uchun sizning yordamingizga muhtoj.

Kiruvchi ma'lumotlar:

Birinchi qatorda boʻsh boʻlmagan $s$ satri uzunligi koʻpi bilan 50 ta belgidan iborat boʻlib, faqat inglizcha kichik harflardan iborat.

Chiquvchi ma'lumotlar:

Agar $s$ ichida palindrom bo'lmagan shunday qism-satr mavjud bo'lsa, bunday qism-satrning maksimal uzunligini chop eting. Aks holda 0 ni chop eting.

Izoh:

"mew" palindrom emas, shuning uchun uning palindrom bo'lmagan eng uzun qism-satri "mew" satrining o'zi. Shunday qilib, birinchi misol uchun javob 3.

“uffuw" satri "wuffuw" satrining eng uzun palindrom bo'lmagan qism-satrlaridan biri (uzunligi 5) bo'lib, ikkinchi misol uchun javob 5 ga teng. (shuningdek, “wuffu” satri ham shunday qism-satr hisoblanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	mew	3
2	wuffuw	5
3	qqqqqqqq	0

G. Ajoyib topshiriq

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizda quyidagi son bor. $S = 1234567891011121314151617…$

Sizning vazifangiz uchbu sonning $k$ -raqamini chiqarib berishdan iborat.

(indekslash 1 dan boshlanadi)

Kiruvchi ma'lumotlar:

Yagona qatorda $k (1 ≤ k ≤ 1000)$ butun soni mavjud – chiqarib berilishi kerak bo’lgan raqamning pozitsiyasi.

Chiquvchi ma'lumotlar:

Yagona qatorda $S$ sonning $k$ -raqamni chiqarib bering.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3	3
2	11	0

H. Xonalar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga binoning xaritasi berilgan, sizning vazifangiz undagi xonalar sonini sanash. Bino $n×m$ ko’rinishida va har bir kletka yoki polni yoki devorni anglatadi. Siz yuqoriga, pastga, o’ngga va chapda yurishingiz mumkin.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga ikkita son - $n$ va $m$ beriladi. $(1 ≤ n, m ≤ 1000)$

Keyingi $n$ ta qatorning har birida $m$ ta belgi mavjud: '.' - polni, '#' - devorni anglatadi.

Chiquvchi ma'lumotlar:

Faqatgina bitta son - binodagi xonalar sonini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 8 ######## #..#...# ####.#.# #..#...# ########	3

I. Qorovul

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Ali maktabda qorovul bo’lib ishlaydi. U hamma o’quvchilar uyga ketgandan so’ng barcha svetlarni o’chirib qo’yishi kerak. Maktabda $k$ ta lampochka bor. Shu bilan birga lampochkalarni o’chirish uchun ishlatadigan $p$ ta tugma bor. Har bir tugma ma’lum bir miqdordagi lampochkalarni o’chira oladi. Buni qarangki, hamma tugmani bosgandan so’ng ham barcha lampochkalar o’chmasligi mumkin ekan. Ali tugmalarni bosgandan so’ng hamma lampochkalarni o’chira oladimi yo’qmi, shuni bilmoqchi. Bunda sizning yordamingizga muhtoj.

Kiruvchi ma'lumotlar:

Birinchi qatorda $p$ va $k (1 ≤ k, p ≤ 100)$ butun sonlar mavjud — mos ravishda tugmalar soni va lampochkalar soni.

Keyingi $p$ qatorning har birida $x_i (0 ≤ x_i ≤ k)$ - $i-$ tugma orqali o'chirsa bo'ladigan lampochkalar soni, so'ngra $x_i$ ta son $y_{i,j} (1 ≤ y_{i,j} ≤ k)$ - bu lampochkalarning raqamlari mavjud.

Chiquvchi ma'lumotlar:

Bitta qatorda agar Ali hamma lampochkalarni o’chira olsa “YES” aks holda “NO” yozuvini chop eting. (hamma harflari kattada bo’lishi shart)

Izoh:

Birinchi misolda hammasini o’chira oladi. 2-sida 3-lampochka yoniq qoladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 2 1 4 3 1 3 1 1 2	YES
2	3 3 1 1 1 2 1 1	NO

J. Doiraviy surish

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga $n$ butun soni berilgan. Shu bilan birga sizga $m$ soni va $c$ yo’nalish ( $L$ – chapga yoki $R$ – o’ngga).

Siz $n$ sonining bitlarini $c$ yo’nalishga $m$ marta doiraviy surilgandan keyingi hosil bo’lgan sonni toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga $t$ – testlar soni beriladi $(1 ≤ t ≤ 10^4)$

Keyingi $t$ ta qatorning har birida sizga uchta son – $n, m$ va $c$ beriladi. $(1 ≤ n ≤ 65535, 1 ≤ m ≤ 15)$

Chiquvchi ma'lumotlar:

$t$ ta testning har biri uchun javobni alohida qatorlarda chiqaring.

Izoh:

Bu misolda $n$ sifatida kiritilgan har qanday son ikkilik ifodalanishda 16 bitlik son sifatida ifodalanadi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 7881 5 L 7881 3 R	55587 9177

K. Darajalar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

O’yinda jami $n$ ta daraja bor. O'yin $m$ ta teleporter bilan bog'langan va sizning vazifangiz 1-darajadan $n$ -darajaga o'tishdir. O'yin shunday yaratilganki, asosiy grafikda yo'naltirilgan sikllar yo'q. O'yinni necha xil usul bilan yakunlashingiz mumkin?

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga ikkita son $n (1 \le n \le 10^5)$ - darajalar soni, va $m (0 \le m \le2*10^5)$ - teleportlar soni berilgan.

Keyingi $m$ ta qatorning har birida sizga ikkita son - $a$ va $b$ beriladi. Bu esa $a$ va $b$ darajalar orasida teleport bor ekanini anglatadi. $(1 ≤ a,b ≤ n; a \ne b)$

Chiquvchi ma'lumotlar:

Faqatgina bitta son - 1 - darajadan $n$ - darajaga necha hil usulda borish mumkinligi. Javob o'ta katta son bo'lib ketishi mumkinligini hisobga olib javobni $10^9+7$ ga qoldiq sifatida chiqaring.

Misollar:

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

L. Maksimal summa

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi $n$ ga teng bo’lgan $a$ massiv berilgan. Sizning vazifangiz quyidagi operatsiya bir marta bajarilgach erishish mumkin bo’lgan maksimal qism-massiv yig’indisini topishdir.

Massivdan qandaydir qism-massiv tanlab undagi barcha elementlarni qiymatini 0 ga aylantiring.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga $t$ – testlar soni beriladi. $(1 ≤ t ≤ 2*10^4)$ . Keyingi $t$ ta qatorning har birida sizda:

Birinchi qatorida sizga $n$ – massiv uzunligi beriladi. $(1 ≤ n ≤ 5*10^5)$
Ikkinchi qatorda sizga $n$ ta son – massiv elementlari beriladi. Massiv elementari $10^9$ dan oshmaydi.

Chiquvchi ma'lumotlar:

$t$ ta qatorning har biriga faqatgina bitta son – erishish mumkin bo’lgan qism-massivning maksimal summani chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 4 -1 4 -1 2	6

M. Birinchi kichik

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi $n$ ga teng bo’lgan massiv berilgan. Sizning vazifangiz massivning har bir elementi uchun o’zidan chapdagi birinchi kichik elementning indeksini chiqarish.

Kiruvchi ma'lumotlar:

Birinchi qatorda $n$ – massiv uzunligi beriladi $(1 ≤ n ≤ 2*10^5)$

Ikkinchi qatorda sizga $n$ ta son – massiv elementlari beriladi. Massiv elementlari $10^9$ dan oshmaydi.

Chiquvchi ma'lumotlar:

$n$ ta son chiqaring: har bir element uchun o’zidan chapdagi birinchi kichik element indeksi. Agar bunday element mavjud bo’lmasa bu indeksga 0 chiqaring.

Misollar:

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

N. Xonadonlar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Jami $n$ ta arizachi va $m$ ta xonadon mavjud. Sizning vazifangiz imkon qadar ko'proq arizachilar xonadonlarga ega bo'lishlari uchun xonadonalarni taqsimlashdir.

Har bir murojaatchining xonadon kattaligi bo’yicha o’z xohishlari bor. Har bir arizachi agar xonadon o’z xohishiga faqatgina o’z xohishiga yetarlicha yaqin bo’lgan xonadonlarnigina oladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda sizga uchta son - $n$ - arizachilar soni, $m$ - xonadonlar soni va $k$ - ruxsat etilgan maksimal farq. $(1 ≤ n,m ≤ 2*10^5), (0 ≤ k ≤ 10^9)$

Ikkinchi qatorda sizga $n$ ta son - har bir arizachining xonadon kattaligi bo'yicha xohishi.
Agar uning xohishi $X$ bo'lsa, u $x - k$ va $x + k$ oralig'idagi xonadonlarni qabul qila oladi. $(1 ≤ X ≤ 10^9)$
Keyingi qatorda sizga $m$ ta son - xonadonlar kattaliklari berilgan.
$1 \le \text{arizachining xoxishidagi xonadon kattaligi} \le 10^9$
$1 \le \text{xonadonlar kattaligi} \le 10^9$

Chiquvchi ma'lumotlar:

Faqatgina bitta son - arizachilarga berish mumkin bo'lgan maksimal xonadonlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 5 60 45 80 60 30 60 75	2

O. Teng elementlar

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizga $n$ ta natural sondan iborat $a$ massiv berilgan. Sizning vazifangiz massivning barcha elementlari qiymatini bir xil songa olib kelish (ya’ni, barcha elementlarni teng qilish). Buning uchun siz har bir amalda quyidagi ikki operatsiyadan birini bajarishga ruxsat etilgan:

Massivning ixtiyoriy elementini tanlab uning qiymatini 1 ga kamaytirish mumkin, agarda qiymat 1 ga kamayganidan so’ng massiv elementi qiymati 0 bo’lsa u o’z – o’zidan massiv tarkibidan chiqib ketadi (chunki massiv o’zida faqat natural sonlarni qabul qilar edi).
Massivning ixtiyoriy elementini tanlab uning qiymatini 1 ga oshirish mumkin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta natural son, $n (1≤n≤10^3)$ soni kiritiladi. Ikkinchi qatorda bo’sh joy bilan ajratilgan holda $a$ massiv elementlari kiritiladi $(0 < a_i \le 10^9)$

Chiquvchi ma'lumotlar:

Chiqish faylida faqatgina bitta son - massivning barcha elementlarini teng qilish uchun kerak bo'ladigan eng kam amallar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2 2 3	1