A. Konfetlar Sirli Almashinuvi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Siz bir nechta do‘stlar bilan shirinlik bayramida ishtirok etyapsiz! $n$ ta do‘st bor va har biri o‘ziga xos 3 tadan (faqat bitta turdagi) shokoladga ega. Har bir boladagi shokolad turi boshqalaridan farq qiladi.
Demak, umumiy $n$ turdagi shokolad bor va har turdan faqat 3 tadan mavjud. Dastlab, har bir bola faqat o‘z turidagi 3 ta shokoladga ega.

Aynan $k$ ta bola o‘zida kamida 2 xil turdagi shokolad bo‘lishini istaydi, qolgan $n - k$ bola esa, faqat 1 xil turdagi shokolad bilan qolmoqchi. Siz bir amalda

Istalgan 2 do‘stdan bittadan shokoladni olib ularni o‘zaro almashtirishingiz mumkin.

Suz bu amaldan istalgancha foydalanib $k$ ta do'stda kamida 2 xil turdagi shokolad va qolganlarida faqat 1 xil turdagi shokolad bo‘lishiga erisha olasizmi? Ha bo‘lsa $\text{YES}$, aks holda $\text{NO}$ deb javob bering!

Kiruvchi ma'lumotlar:

Har bir testda $n$ va $k$ beriladi $0 \leq k \leq n,\ 1 \leq n \leq 10^9$.

Chiquvchi ma'lumotlar:

Masala javobini ekranga chiqaring

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1	NO
2	8 6	YES

B. Panel yangilanishlari

Xotira: 256 MB, Vaqt: 1000 ms

Masala

AlgoritmTech kompaniyasi ko‘chadagi n ta aqlli reklama panelini (ketma-ket) boshqaradi. Har bir panelda faqat 0, 1 yoki 2 raqami yonib turadi.

Kompaniyada bitta “yangilash” buyrug'i bor — u shunday ishlaydi:

Istalgan i (1 ≤ i ≤ n) pozitsiyani tanlaysiz,
So‘ng i-paneldan boshlab oxirigacha (j ≥ i bo‘lgan barcha panellar) raqam 1 ga oshadi, lekin 3 bo‘yicha qoldiq bilan:
- 0 → 1, 1 → 2, 2 → 0

Maqsad: barcha panellarda 0 raqamini yoqish.
Buni eng kam nechta yangilash bilan qilish mumkinligini toping.

Kiruvchi ma'lumotlar:

Birinchi qatorda $n (1 ≤ n ≤ 2⋅10^5)$

Ikkinchi qatorda uzunligi n bo‘lgan s satr (faqat '0', '1', '2')

Chiquvchi ma'lumotlar:

Bitta butun son — barcha panellarni 0 qilish uchun kerak bo‘ladigan minimal yangilashlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 12021	8

C. Sehrli Tunnel Darvozasi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Husanboy sehrli ichimlik solingan idish topib oldi. Idish ustidagi yozuvda qadimiy sirli darvozani ochish uchun tunnel ichidan qanday harakat qilish kerakligi aytilgan.

Tunnel poliga kvadrat kataklar yotqizilgan. Tunnel bir nechta qatordan iborat bo‘lib, har bir qatorda $N$ ta katak bor. Kataklar quyidagicha raqamlanadi:

1-qator chapdan o‘ngga: $1, 2, 3, ..., N$
2-qator chapdan o‘ngga: $N+1, N+2, ..., 2N$
va shu tarzda davom etadi (qatorma-qator, chapdan o‘ngga).

Husanboy tunnel kirishida, 1-qator oldida turibdi. Darvozani ochish uchun u aynan $P$ raqamli katakka yetib borishi kerak.

Harakat qoidalari

Kirishdan Husanboy 1-qatorning istalgan katagiga $(1..N)$ sakrashi mumkin. Bu sakrash uchun 0 tomchi sarflanadi.
Agar Husanboy hozir $X$ raqamli katakda bo‘lsa, u:

$X + 1$ raqamli katakka sakrashi mumkin — buning uchun 1 tomchi sarflaydi;
$2 * X$ raqamli katakka sakrashi mumkin — buning uchun 2 tomchi sarflaydi.

Husanboy $P$ raqamli katakka yetib borishi uchun bosib o'tadigan minimum kataklar soni hamda sarflaydigan minimum tomchilar sonini toping.

Kiruvchi ma'lumotlar:

Yagona qatorda ikkita natural son - $N, P$ kiritiladi. $(1\le N\le 10^4, 1\le P\le 10^{18})$

Chiquvchi ma'lumotlar:

Yagona qatorda minimal bosish kerak bo'lgan kataklar soni va minimal sarflanadigan tomchilar sonini chiqaring.

Misollar:

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

D. Chiziqlar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, sizga $n$ ta qator va $m$ ta ustundan iborat maxsus jadval berilgan. Bu jadval faqatgina nuqta (`.`) va plyus (`+`) belgilaridan tashkil topgan.

Biz bu o'yinda chiziq deb quyidagiga aytamiz:

Yonalma-yon uzluksiz kelgan kamida ikki ta `+` belgisidan iborat har qanday qism-kesma chiziq hisoblanadi.
Chiziqlar gorizontal (yotig'iga) yoki vertikal (tikkasiga) bo'lishi mumkin.
Yolg'iz o'zi turgan bitta `+` belgisi chiziq hisoblanmaydi!
Katta uzluksiz `+` lar qatoridan bir nechta turli xil chiziqlar ajratib olish mumkin (masalan, `+++` qismidan jami 3 ta chiziq chiqadi).

Sizning vazifangiz berilgan $type$ (tur) raqamiga qarab quyidagi shartlardan birini bajarishdir:

1-tur $(type = 1)$: Turli qatorlarda joylashgan ikkita gorizontal chiziqni tanlashning jami necha xil usuli borligini topish.
2-tur $(type = 2)$: Turli ustunlarda joylashgan ikkita vertikal chiziqni tanlashning jami necha xil usuli borligini topish.

Kiruvchi ma'lumotlar:

Birinchi qatorda uchta butun son: $type$, $n$ va $m$ beriladi.

$type \in \{1,2\}$ faqat $1$ yoki $2$ bo'lishi mumkin.
$(1 \leq n, m \leq 1000,\ n \times m \leq 10^6)$

Keyingi $n$ ta qatorning har birida $m$ tadan belgi (`.` yoki `+`) beriladi.

Chiquvchi ma'lumotlar:

Yagona butun son — barcha qoidalarga mos keluvchi chiziqlar juftligini tanlash usullari sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2 5 +++.. .++++	18
2	2 2 5 +++.. .++++	1

E. Help to rshohruh

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Tasavvur qiling, siz ulkan bir o‘rmonda sayr qilmoqdasiz! Bu o‘rmonning yo‘lagi bo‘ylab $N$ ta daraxt saf tortib turibdi. Ularning balandligi har xil bo‘lib, 1 dan $N$ gacha barcha sonlar ishtirok etgancha har biri o‘ziga xos – ya’ni, bu raqamlar o‘zaro takrorlanmaydigan permutatsiyani hosil qiladi.

Shohruh ushbu o‘rmondan yog‘och yig‘ishga qaror qildi va daraxtlarni kesishda sizning zukkoligingizga suyanmoqda. U quyidagicha kesish usulini o‘ylab topdi: har safar yo‘ldan ketma-ket $M$ ta daraxt tanlab, ularning barchasining balandligini o‘sha oralig‘idagi eng past daraxt balandligigacha pasaytirib chiqadi. Bu harakatni Shohruh istagancha ko‘p bajara oladi.

Endi esa, Shohruh sizga $Q$ ta qiziqarli savol beradi! Har bir savolda sizga $M$ va $K$ qiymatlari beriladi, va maqsad – siz kesishlar yordamida aynan balandligi $K$ bo‘lib qolgan daraxtlarning maksimal sonini topishingiz kerak.

Shohruhning barcha savollariga chaqqon va samarali javob bera olasizmi?

!! Har bir so'rov oldingisiga bog'liq emas.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ va $Q$ beriladi. Ikkinchi qatorda $N$ ta son, daraxtlar balandligi $h[1], h[2], \dots, h[N]$ beriladi. Keyingi $Q$ qatorda har bir so‘rov uchun $M$ va $K$ beriladi. Har bir so‘rov uchun alohida qatorda javob chiqaring.
$N$ — daraxtlar soni.
$h[i]$ — $i$-chi daraxt balandligi.
$Q$ — so‘rovlar soni.
$M$ va $K$ — har bir so‘rov parametrlari.
$1 \le N,Q \le 10^5$

$1 \le M,K \le N$

Chiquvchi ma'lumotlar:

Har bir so'rov uchun masala javobini chiqaring.

Misollar:

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