A. Bo'lishish

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Shaxzod va Jaloliddin yangi yil uchun mandarin sotib olishdi. Endi ularda N ta mandarin bor. Ular N ta mandarinni necha xil usulda bo'lishib olishlari mumkin?

Kiruvchi ma'lumotlar:

N natural soni $1<N\leq 10^5$ .

Chiquvchi ma'lumotlar:

Masala javobi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2	1

B. Qutidagi to'plar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizda bo'sh quti va juda ko'p to'plar bor.
Siz quyidagi amallarni istalgan marta, istalgan tartibda bajarishingiz mumkin.

A: qutiga 1 ta to'p solish.
B: qutidagi to'plarni 2 baravar ko'paytirish.

Qutida N ta to'p bo'lishi uchun bajarish kerak bo'lgan amallar ketma-ketligini chop eting.
Siz ko'pi bilan 120 ta amal bajarishingiz mumkin va amallar sonini minimallashtirish shart emas.

Kiruvchi ma'lumotlar:

N natural soni $(1\leq N \leq 10^{18})$ .
120 ta amalda N sonini yasab bo'lishi kafolatlanadi.

Chiquvchi ma'lumotlar:

A va B harflaridan iborat satr chop eting, bunda A harfi A amalni, B harfi B amalni ifodalaydi. Chop etilgan satr uzunligi 120 dan oshmasligi kerak.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7	BBBABABA
2	4	ABB

C. Matritsa

Xotira: 64 MB, Vaqt: 1000 ms

Masala

$N*N$ o'lchamli $C$ matritsa berilgan. Sizdan shunday $A$ va $B$ massivlar mavjudligini tekshirish so'raladiki, bunda har bir $i,\space j \space (1\leq i,j \leq N)$ juftlik uchun $C_{i,j}=A_i+B_j$ shart bajarilsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ natural soni. Keyingi $N$ ta qatorda $N$ tadan butun son, $C$ matritsa elementlari.

$1\leq N \leq 10^3, \space\space 0\leq C_{i,j}\leq10^9.$

Chiquvchi ma'lumotlar:

Agar shartni qanoatlantiruvchi $A$ va $B$ massivlar mavjud bo'lsa YES, aks holda NO so'zini chop eting.

Misollar:


YES
YES
YES
YES
NO

#	INPUT.TXT	OUTPUT.TXT
1	2 2 4 2 4	YES
2	1 1	YES
3	3 1 2 3 2 3 4 4 5 6	YES
4	3 1 1 1 1 1 1 1 1 1	YES
5	3 1 1 1 1 0 1 1 1 1	NO

D. Labirint

Xotira: 128 MB, Vaqt: 1250 ms

Masala

Ma’lum bir fermer xo‘jaligi yerining eni $N$ metr va bo‘yi $N$ metr ekan. Bunda to‘liq yer 1 metrga 1 metr maydonchalarga ajratilgan. Ba’zi maydonchalarda makkajo‘xori ekilgan, ba’zilari esa bo‘m-bo‘sh.

Asadullo va Ulug‘bek shu yer maydonida berkinmachoq o‘ynamoqchi bo‘lishdi. Ammo Asadullo injiq bo‘lgani sababli o‘yingoh labirint ko‘rinishida bo‘lmasa yoki bo‘sh maydonchalar soni ikkitadan kam bo‘lsa, o‘ynamasligini ma’lum qildi.

Agarda istalgan bo‘sh maydonchadan boshqa bir bo‘sh maydonchaga yagona usulda yetib borishning iloji bo‘lsa, bu yer maydonini labirint deb hisoblasak bo‘ladi. Bitta umumiy tomonga ega maydonchalar qo‘shni hisoblanadi va biridan ikkinchisiga o‘tib bo‘ladi. Albattaki, ekinlarni payhon qilmaslik uchun makkajo‘xori ekilgan maydonchalardan yurish taqiqlanadi.

Sizning vazifangiz Asadullo va Ulug‘bek berkinmachoq o‘ynay olishlarini tekshirish.

Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida bitta butun son - $N(1 \le N \le 3000)$ kiritiladi.

Keyingi $N$ ta qatorning har birida $N$ tadan son - maydonchalar holati kiritiladi.

Bu yerda 0 bo‘sh maydoncha, 1 esa makkajo‘xori ekilgan maydoncha.

Chiquvchi ma'lumotlar:

Agar do‘stlar berkinmachoq o‘ynay olishsa “Yes” aks holda “No” so‘zini qo‘shtirnoqlarsiz chiqaring.

Izoh:

.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 000 110 000	Yes
2	4 0001 0101 0000 1111	No

E. "Joyida"

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizda 1 dan $N$ gacha bo'lgan sonlarning ixtiyoriy permutatsiyasi $P$ va $M$ ta $(x,y)$ ko'rinishidagi juftliklar berilgan. Siz $P_x$ va $P_y$ qiymatlarni istalgancha almashtirishingiz mumkin.
Permutatsiyadagi son ″joyiga″ tushgan hisoblanadi, qachonki permutatsiyada o'ziga teng indeksni egallasa. Indekslash 1 dan boshlanadi.
Berilgan permutatsiyada almashtirishlarni bajarish orqali ko'pi bilan nechta elementni ″joyiga″ tushirish mumkinligini hisoblang.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ va $M$ natural sonlari. Ikkinchi qatorda $N$ ta elementdan iborat $P$ permutatsiya. Keyingi $M$ ta qatorda $x_i$ va $y_i \space (1\leq i \leq M)$ juftliklar beriladi.

$1 \leq N,M \leq 10^5, \space 1 \leq x_i,y_i \leq N.$

Chiquvchi ma'lumotlar:

Joyiga tushgan elementlar sonini chop eting.

Misollar:

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

F. Archa do`konida

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Archasiz yangi yil bayramini tassavur qilib bo`lmasa kerak. Albatta, Asilbek ham shunday fikrda. Bundan tashqari uning fikricha archalar qancha ko`p bo`lsa shuncha yaxshi!

Ma'lum bir do`konda jami $N$ ta archalar bor. $i$ -archaning narxi $a[i]$ $(dollar).

Asilbek sizga quyidagi so`rovdan $Q$ marta beradi:

$Y$ va $X$ butun sonlari kiritiladi. X $(dollar) dan ko`p pul ishlatmagan holda kamida Y ta archa xarid qilishning nechta turli xil usuli mavjud?

Sizing vazifangiz barcha so`rovlarga javob berishdir.

Ikki xarid bir xil hisoblanadi, agarda ikki xaridda ham sotib olingan archalar to`plami ustma-ust tushsa. Aks holda ular har xil.

Kiruvchi ma'lumotlar:

Birinchi qatorda yagona butun son - $N(1 \leq N \leq 50)$ kiritiladi.

Ikkinchi qatorda $N$ ta butun son - $a$ massiv elementlari $(1 \leq a[i] \leq 1000)$ kiritiladi.

Uchinchi qatorda yagona butun son - $Q(1 \leq Q \leq 5*10^5)$ so`rovlar soni kiritiladi.

Keyingi $Q$ ta qatorning har birida ikkitadan butun son - navbatdagi so`rov uchun $Y,X(1 \leq Y \leq 100, 1 \leq X \leq 2000)$ sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir so`rov uchun yangi qatorda, turli xil xaridlar usulini chop eting.

Izoh:

1-test:

2-so`rov uchun xaridlar: [1], [2].

4-so`rov uchun xarid: [1,2,3].

6-so`rov uchun xaridlar: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

7-so`rov uchun xaridlar mavjud emas.

2-test:

3-so`rov uchun xaridlar: [3,4], [3,5], [4,5].

5-so`rov uchun xaridlar: [1,2,3,4], [1,2,3,5], [1,2,4,5], [1,3,4,5], [2,3,4,5].

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 2 3 7 1 1 1 2 2 2 3 3 3 6 1 10 7 12	1 2 0 0 1 7 0
2	5 300 400 100 50 177 5 3 800 6 1000 2 300 3 1200 4 977	11 0 3 16 5

G. Kill the monsters!

Xotira: 64 MB, Vaqt: 1250 ms

Masala

“Kill the monsters!” nomli o‘yin mavjud. Bu o‘yinda, siz tushunib ulgurganingizdek, monsterlar bor va ularni o‘ldirish lozim.

O‘yin maydoni bitta uzun kesma bo‘lib, u $-10^9$ dan $10^9$ gacha raqamlangan koordinatalardan iborat. Koordinata 3 xil holatda bo‘lishi mumkin: koordinata bo‘sh, koordinatada 1 ta monster bor yoki koordinatada 1 ta devor bor. Maydondagi jami devorlar va monsterlar soni $n$ ga teng. Har bir monster o‘zining sog‘lik darajasiga ega.

Siz $k$ marta quyidagi ishni qila olasiz:

o‘yin maydonida devor bo‘lmagan va oldin belgilanmagan koordinatani tanlash va uni belgilash

So‘ng barcha belgilangan koordinatalarda bir vaqtda olov yoqasiz.

Qaysidir koordinatada olov yongan bo‘lsa, 1 soniyada shu koordinatadagi monsterning sog‘lik darajasi 1 birlikka kamayadi, hamda olov oldin yonmagan va devori yo‘q bo‘lgan qo‘shni koordinataga ham o‘tadi. Olov yongan koordinatada u hech qachon o‘chmaydi. Monsterning sog‘lik darajasi 0 ga tushsa, u o‘ldi deb hisoblanadi.

Yondirish uchun $k$ ta koordinatani optimal tanlab ularni yondirgach, eng kami bilan necha soniyadan so‘ng barcha monsterlar o‘lishini toping.

Optimal tanlovda ham, $10^{100}$ soniyadan so‘ng tirik monster topilsa, “IMPOSSIBLE” so‘zini qo‘shtirnoqlarsiz chiqaring.

Kiruvchi ma'lumotlar:

Kirish oqimining birinchi qatorida ikkita butun sonlar - $n,k(1 \le k \le n \le 2*10^5)$ kiritiladi.

Keyingi $n$ ta qatorning har birida maydondagi bo‘shmas kataklar ko‘rsatiladi.

Monster uchun yangi qatorda ‘M’ belgisi va yana 2 ta butun son - $x(-10^9 \le x \le 10^9)$ monster turgan koordinata va $h(1 \le h \le 10^9)$ monsterning sog‘lik darajasi kiritiladi.

Devor uchun yangi qatorda ‘W’ belgisi va yana 1 ta butun son - $x(-10^9 \le x \le 10^9)$ devor turgan koordinata kiritiladi.

Barcha testlar tepadagi shartlarni qanoatlantirishi kafolatlanadi.

Chiquvchi ma'lumotlar:

Yagona qatorda masala javobini chiqaring.

Izoh:

Birinchi testda:

1 koordinatada sog‘ligi 4 bo‘lgan monster bor.
2 koordinatada devor bor.
3 koordinatada sog‘ligi 6 bo‘lgan monster bor.

Yondirish uchun 2 ta koordinatani belgilash lozim. 1 va 3 koordinatani belgilab ularni yondirsak, 6 soniyada barcha monsterlar o‘ladi. Bu eng yaxshi natija ekanligini isbotlasa bo‘ladi.

Ikkinchi testda:

Devor va monsterlar xuddi birinchi testdagidek, yagona farqi yondirish uchun faqatgina 1 ta koordinatani tanlash mumkin. Bu holatda javob “IMPOSSIBLE”. Chunki qaysi koordinatani yondirmaylik, bitta monster o‘ladi, boshqa monster esa devor sababli $10^{100}$ soniyadan so‘ng ham tirik qoladi.

Uchinchi testda:

Faqatgina 1 ta koordinatani yondirish mumkin. 0 koordinatani tanlash optimal bo‘ladi. Bunda 1-monsterga yetib olib uni o‘ldirish uchun $10^9+1$ soniya vaqt kerak. 2-monsterga yetib olib uni o‘ldirish uchun esa $10^9+2$ soniya vaqt kerak. Jami $10^9+2$ soniyadan so‘ng barcha monsterlar o‘lgan bo‘ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2 M 1 4 W 2 M 3 6	6
2	3 1 M 1 4 W 2 M 3 6	IMPOSSIBLE
3	2 1 M -1000000000 1 M 1000000000 2	1000000002