A. Bog`bon Samir

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Samir bog`idagi daraxtlarn sug`ormoqchi. U bitta daraxtga \(a_i\) ta chelakda suv quyishi kerak va uni bog`ida \(n\) ta daraxt bor. U faqat birdaniga 2 ta chelakda suv tashil oladi va qo`lida nechta chelak bo`lsa ham hammasini bitta daraxtga quyishga majbur. U hamma daraxtlarni to`liq sug`orishi uchun nechta energiya sarflashi kerak. Bitta energiyada 2 ta chelak suv quyishi mumkin va bitta energiyani hammasini bitta daraxtga ishlatadi!!!

Kiruvchi ma'lumotlar:

n -> daraxtlar soni

a massiv n ta elementdan iborat

Chiquvchi ma'lumotlar:

nechta energiya sarflashi kerakligi

Misollar:

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

B. TQQ

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Muhammadsiddiq va Nusrat shahar aylanishayotgan edi. ular to'satdan pul topib olishdi, juda katta miqdorda edi, pul juda ko'p bo'lganligi sababli ular tortishib qolishdi.
Keyin Nusrat "tosh, qaychi, qog'oz" o'yini yechim bolishi aytdi va do'sti bunga rozi bo'ldi faqat quyidagi shartlar bilan:

Faqat 3 marta o'ynashadi
3 ta o'yin natijalarida ko'proq g'alaba qozongan o'yinchi hamma pulni oladi
agar ikkala o‘yinchining g‘alabalari soni teng bo‘lsa, pul teng bo‘linadi

Shu tariqa ular o'yin o'ynashni boshladi
Sizning vazifangiz esa oxirida pullarning egasi kim bo'lishini aniqlash

"Tosh qaychi qog'oz" o'yini qoidalari

Har bir o‘yinda ikki o‘yinchi bir vaqtning o‘zida quyidagi uchta variantdan bittasini tanlaydi:
Tosh
Qaychi
Qog‘oz

G‘alaba qoidalari:
Tosh qaychini yutadi
Qaychi qog‘ozni yutadi
Qog‘oz toshni yutadi

Kiruvchi ma'lumotlar:

Kirish qismida 3 ta qatordan iborat ma’lumot beriladi.
Har bir qatorda bitta satr beriladi.

Satr quyidagi qiymatlardan bittasiga teng bo‘ladi:

Muhammadsiddiq
Nusrat
durang

Berilgan satrlar lotin alifbosida yozilgan bo‘lib, katta-kichik harflarda bo'ladi

Chiquvchi ma'lumotlar:

Chiqish qismida agar Muhammadsiddiq yutsa "Muhammadsiddiq", Nusrat yutsa "Nusrat", durang bo'lsa "durang" chop etilsin

Izoh:

Agar ikkala o‘yinchi bir xil tanlov qilsa, o‘yin durang hisoblanadi va hech kim yutgan deb hisoblanmaydi.
Agar 3 ta o‘yinning natijalarida 1-marta Muhammadsiddiq yutsa, 2-marta “durang” bo‘lsa bu holatda durang yakuniy natija hisoblanmaydi, chunki Muhammadsiddiq 1 ta g‘alabaga ega, Nusrat esa 0 ta.
Shuning uchun Muhammadsiddiq pulni oladi.

Yakuniy natija faqat quyidagi holatda “durang” bo‘ladi:
Har ikkala o‘yinchi ham bir xil miqdorda g‘alaba qozonsa (masalan, 1 tadan g‘alaba va qolgani durang, yoki 3 ta durang orqali)

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	Nusrat Muhammadsiddiq Nusrat	Nusrat

C. Fan Olimpiadasi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

FOM(Fan Olimpiadalari Markazi) haqida eshitgan bo'lsangiz kerak. U har yili O'zbekiston maktablari o'rtasida asosiy fan olimpiadasini o'tkazadi. ular shu paytgacha testlarda har bir o'quvchiga test, yozma ish, masala kabi sinovlar berib kelgan. Lekin 2026-2027-o'quv yiliga boshqacha rejalar tuzib qo'ydi, reja bo'yicha saralashdan o'tgan o'quvchilarning:

o'quvchilarni jamoa tartibida shakllantirish
har bitta jamoada 2 ta ishtirokchi bo'lishi
bir kishilik jamoa bo'lmasligi

talablari qo'yildi. Bu \(K\) talablarni qanoatlantiradigan jamoalarni necha xil usulda tuzish mumkinligi esa sizga topshirildi

Kiruvchi ma'lumotlar:

Kirish qismida birinchi qatorda ikkita butun son \(N(1\leq N \leq 10^5)\) - massiv uzunligi va \(K(1\leq K \leq 10^9)\) - so'ralgan talab beriladi

Keyingi qatorda \(N\) uzunlikdagi \(arr(1\leq arr \leq 10^9)\) massiv beriladi

Chiquvchi ma'lumotlar:

Chiqish qismida talabni nechta juftlik qanoatirishi mumkinligini chop eting

Misollar:

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

D. Joyini topdi

Xotira: 96 MB, Vaqt: 1000 ms

Masala

Bu masalamiz ham Nusrat haqida bo`lishi mumkin edi lekin Nusrat hozir juda juda uzoqlarda. Lekin bizga judayam yaqin bo`kgan bir joyda Muhammadrizo yashaydi. U raqamlar bilan o`ynashni yaxshi ko`radi va sal avval akasining massividan tasodifiy bir elementni olib o`ynayotgandi. Akasi har doim massivlarini tartiblab yuradi. Lekin endi u elementni joyini topolmayapti qayerga qo`yish kerakligini topolmayapti. Unga sizning yordamingiz kerak iltimos unga yordam bering.

Kiruvchi ma'lumotlar:

\(N\) -> Muhammadrizoning akasining massivining uzunligi \(1 \leq N \leq 10^{9}\)

keyingi qatorda N - 1 ta son ya`ni massiv

uchinchi qatorda Muhammadrizo olib qo`ygan son

Chiquvchi ma'lumotlar:

elementni indexini topishingiz kerak

Izoh:

agar yo`qolgan son bilan teng elementlar mavjud bo`lsa u eng birinchisini olgan deb hisoblang

Misollar:

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

E. Qora katakcha

Xotira: 32 MB, Vaqt: 1000 ms

Masala

NxM shakldagi shaxmat doskasi oq va qora kataklardan iborat. Chap pastki burchagi qora rangda bo'lsa, ushbu shaxmat katakchasida nechta qora katak mavjud.

Kiruvchi ma'lumotlar:

N va M natural son beriladi. (1≤N,M≤10 **3)

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 1	1

F. Yagona Segmentlarni Birlashtirish!

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Vazifa

Sizda n ta raqamdan iborat a massiv bor. Imkoniyatingiz bor — har bir yurishda faqat ikki qo‘shni elementni tanlab, ulardan yagona element yasaysiz. Ularning o‘rniga yig‘indilarini yozasiz!

Masalan, [1, 2, 3, 4] dan 2 va 3 ni birlashtirsangiz, [1, 5, 4] bo‘ladi.

Vazifa — massivingizda bo'lgan sonlarni birlashtirib borib, oxirida hamma elementlar bir xil son bo‘lishi uchun eng kam nechta operatsiya kerakligini aniqlang. Agar hech qachon barcha sonlarni bir xilga aylantirib bo‘lmasa, -1 chiqaring.

Topshiriqni bajaring — kim birinchi yakka-katta son yasaydi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) — massiv uzunligi.
Ikkinchi qatorda \(n\) ta butun son \(a[i]\).

Cheklovlar

\(1 \le n \le 2 \times 10^5\)
\(1 \le a[i] \le 10^9\)

Chiquvchi ma'lumotlar:

Minimal operatsiyalar sonini chiqaring. Agar imkonsiz bo‘lsa, -1.

Misollar:

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

G. Sirli Oynalar: Eng Kichik Maksimum!

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, sizda \(n\) ta sirli sandiqchalardan iborat bir qatorda sandiqlar bor. Har bir sandiqda biror butun son yashiringan va ular \(a\) massivida joylashgan.

Sizga bog‘cha sirini ochadigan maxsus vosita beriladi: oynaga faqat uzinligi \(k\) bo‘lgan ketma-ket \(k\) ta sandiqni qaratish mumkin.

Har bir marta oynani sandiqlarga tutganda (ya’ni, har bir uzunligi \(k\) bo‘lgan oraliq uchun), o‘sha sandiqlardagi eng katta son ko‘rinadi. Endi mana shu eng katta sonlar ichidan eng kichigini toping!
Ya’ni, barcha imkoniy oynalarning maksimumlari ichida eng kichik qiymat qaysi?

Rasmiy:
\(\min\limits_{1 \le l \le n-k+1}\left( \max(a_l, a_{l+1}, \dots, a_{l+k-1}) \right)\)

Kiruvchi ma'lumotlar:

Dastlab birinchi qatorda \(n\) va \(k\) beriladi.
Keyingi qatorda \(n\) ta butun son — sandiqlardagi sonlar.

Cheklovlar

\(1 \le k \le n \le 2 \times 10^5\)
\(1 \le a[i] \le 10^9\)

Chiquvchi ma'lumotlar:

Yagona chiqish: hamma uzunligi \(k\) bo‘lgan oynalar maksimumlari ichidagi minimum qiymat.

Misollar:

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

H. Bir Marta Almashtirish

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Alisher yangi kod yozishni yaxshi ko‘radi. Bir kuni u kichik lotin harflaridan iborat bo‘ilgan, uzunligi \(n\) ga teng bir satr — s bilan o‘ynay boshladi.

U o‘z oldiga quyidagi qiziqarli vazifani qo‘ydi: faqat bitta marta istalgan ikkita belgining o‘rnini almashtirib, satrni leksikografik jihatdan eng kichik holatga keltirish.

Alisherga bu muammoni hal qilishda yordam bering! Eng kichik bo‘lishi mumkin bo‘lgan natija satrini chiqaruvchi dastur tuzing.

Kiruvchi ma'lumotlar:

Bitta satr s.

Cheklovlar

\(1 \leq |s| \leq 2 \times 10^5\)

Chiquvchi ma'lumotlar:

Ko‘pi bilan bitta swapdan keyingi eng kichik satr.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	cbad	abcd

I. K-th One

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, siz maxfiy agent ekansiz va sizdagi kodlar ketma-ketligi faqat 0 va 1 lardan iborat! Ammo ehtiyot bo‘ling: kodlar sizga qarshi ishlaydi va vaqti-vaqti bilan o‘zgarib turadi.
Sizga agentlik tomonidan q ta maxsus buyruq yuboriladi:

1~i – Kodlardagi a[i] elementining holatini zudlik bilan teskarisiga almashtiring! (Agar u 0 bo‘lsa 1 ga, agar 1 bo‘lsa 0 ga o‘zgartiring). Kodlarni doimiy nazoratda tuting!
2~k – Tezda aniqlang: chapdan o‘ngga qarab, k-chi 1 turgan indeks qaysi? Agar bunday kod yetishmasa, -1 qaytaring.

Esingizda bo‘lsin, har bir topshiriqda kodlar istalgan payt o‘zgarishi mumkin, harakatlaringiz tez, diqqatli va aniq bo‘lishi kerak!

Kiruvchi ma'lumotlar:

Sizga uzunligi \(n\) bo'lgan 0 va 1 lardan iborat massiv beriladi.

\(q\) ta so‘rovni bajarish kerak.

So‘rov turlari:

1~i — a[i] ni almashtiring:
- agar a[i]=0 bo‘lsa 1 ga
- agar a[i]=1 bo‘lsa 0 ga
2~k — massivdagi chapdan o‘ngga qarab sanalganda \(k\)-chi 1 ning indexini chiqaring.
Agar bunday 1 mavjud bo‘lmasa, -1 chiqaring.

Eslatma: \(k\) 1 dan boshlanadi.

Cheklovlar

\(1\leq n,~q \leq 2\times 10^5\)

Chiquvchi ma'lumotlar:

Har bir 2 k turidagi so‘rov uchun javob chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 5 1 0 1 0 1 2 2 1 1 2 2 1 3 2 2	2 1 1
2	3 2 0 0 1 1 2 2 5	-1
3	9 2 1 1 0 1 1 0 1 1 0 2 7 2 7	-1 -1

J. Nolga Eng Yaqin Qadamlar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, siz jumboqlar olamidasiz va sizga \(n \times m\) o‘lchamdagi sirli jadval berildi. Har bir katakda xazinani bildiruvchi 0 yoki oddiy yo‘l 1 yashirin.

Sizning vazifangiz: har bir katak uchun unga eng yaqin xazinagacha (0ga) necha qadam yurishni aniqlang. Harakat faqat to‘g‘ri yo‘nalishlarda – yuqoriga, pastga, chapga va o‘ngga amalga oshiriladi. Siz har bir po‘lat niyat bilan qadam bosgan sarguzashtchi sifatida harakat qilasiz!

Qani, kim barcha xazinagacha eng qisqa yo‘llarni topa oladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\; m\)
Keyingi \(n\) qatorda \(m\) tadan 0 yoki 1

Cheklovlar

\(1 \leq n,\; m \leq 1000\)

Griddagi jami kataklar soni \(10^6\) dan oshmaydi

Chiquvchi ma'lumotlar:

Sizga \(n \times m\) o‘lchamdagi jadval beriladi. Har bir katakda 0 yoki 1 bor.

Har bir katak uchun unga eng yaqin 0 gacha bo‘lgan eng kichik masofani toping.

Masofa sifatida yuqoriga, pastga, chapga, o‘ngga yurishlar soni olinadi.

Misollar:

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