A. Xossani saqlang

Xotira: 16 MB, Vaqt: 1000 ms

Sirojiddinda ikkita: \(a\) va \(b(a \le b)\) musbat butun sonlar bor. Bu sonlar unga yoqmay qoldi. Shu sababli u sonlarni boshqa musbat butun \(c\) va \(d(c\le d)\) sonlariga almashtirmoqchi. Faqat u quyidagi xossalardan biri almashmay qolishini istaydi.

1. + xossasi. \(a+b=c+d\) bo‘lishi kerak.
2. – xossasi.  \(b-a=d-c\) bo‘lishi kerak.
3. \(*\) xossasi. \(a*b=c*d\) bo‘lishi kerak.
4. / xossasi. \(\frac {b}{a}=\frac{d}{c}\) bo‘lishi kerak.

Unga istalgan \(c\) va \(d\) musbat butun sonlarini topishga yordam bering.

2 3 *

1 6

8 9 +

4 13

7 9 -

29 31

9 12 /

60 80

B. Viktorinadagi vazifa

Xotira: 32 MB, Vaqt: 1250 ms

Yaqin kunlarda Sunnatbekning maktabida viktorina uyishtirilishi ma’lum bo‘ldi. Viktorina har xil qiyinchilikdagi turli xil savollar va vazifalardan iborat. Viktorinadagi eng so‘nggi vazifa sharti unga ma’lum bo‘lib qoldi.

Sunnatbek quyidagi shartlarni qanoatlantiruvchi istalgan \(X\) natural sonini topishi kerak ekan:

• sonning uzunligi \(N\) ga teng va u \(0\) raqami bilan boshlanmaydi;
• \(\lfloor \frac{X}{10^{N-i}} \rfloor\) soni \(A_i(1 \le i \le N)\) soniga qoldiqsiz bo‘linishi lozim. Bunda \(1 \le A_i \le 10\).\(\lfloor y \rfloor\) - y sonidan kichik yoki teng eng katta butun sondir. Misol uchun: \(\lfloor 2.6 \rfloor = 2\), \(\lfloor -3.2 \rfloor = -4\) hamda \(\lfloor 7 \rfloor = 7\).

Viktorina boshlanishiga vaqt hali bor, lekin Sunnatbek istalgan \(N\) soni va \(A\) massivi uchun shartni qanoatlantiruvchi biror bir \(X\) sonini topuvchi dastur yaratib qo‘ymoqchi.

Buni u osonlikcha uddaladi. Siz ham shunday dastur yaratib ko‘ring.

4
5 5 6 7

5523

3
2 10 9

207

C. Labirint

Xotira: 128 MB, Vaqt: 1250 ms

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.

3
000
110
000

Yes

4
0001
0101
0000
1111

No

D. Kill the monsters!

Xotira: 64 MB, Vaqt: 1250 ms

“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.

3 2
M 1 4
W 2
M 3 6

6

3 1
M 1 4
W 2
M 3 6

IMPOSSIBLE

2 1
M -1000000000 1
M 1000000000 2

1000000002

E. Asadbekning gullari

Xotira: 16 MB, Vaqt: 1000 ms

Asadbek gullarni parvarishlashni yoqtiradi. U “Ci plus plusium” gullaridan o‘zining qator joylashgan \(n\) ta tuvagining barchasiga ekdi. Birinchi kuni barcha gullarning bo‘yi 0 deb hisoblasa bo‘ladi. Shu kundan boshlab har kuni Asadbek:

• shunday \([l, r]\) oraliqni tanlaydiki, shu oraliqdagi barcha tuvaklardagi gullarning bo‘yi  bir xil bo‘lsin;
• \([l+1,r-1]\) oraliqdagi barcha tuvaklarga suv quyadi. Keyingi kungacha shu oraliqdagi tuvaklarda joylashgan gullar 1 birlikka ga o‘sadi.

Misol, \(n=6\) uchun mos ravishda 1-2-3-kunlardagi gullarning bo‘yini quyidagicha tasvirlash mumkin:

 

1-kuni \([1,6]\) oraliq tanlangan va \([2,5]\) oraliqdagi tuvaklarga suv quyilgan.

2-kuni \([3,5]\) oraliq tanlangan va \([4,4]\) oraliqdagi tuvaklarga suv quyilgan.

0 yoki bir necha kundan so‘ng, Asadbek o‘zining gullari bilan maqtanmoqchi bo‘lib, har bir gulining bo‘yini \(A\) massiviga yozib, uni sizga berdi (\(A_i=i\)-tuvakdagi gulning bo‘yi). Ammo ba’zi gullarining bo‘ylarini eslay olmagani uchun, ularning bo‘ylarini o‘rniga -1  sonini yozdi.

Sizning vazifangiz Asadbek bergan ma’lumotlarga ko‘ra, bugungi kunda uning gullari necha xil ko‘rinishda bo‘lishi mumkinligini sanashdir. Agarda Asadbek sizni aldagan bo‘lsa, 0 chiqaring.

Natija katta bo‘lishi mumkinligi sababli, natijani \(10^9+7\) ga bo‘lingandagi qoldig‘ini chiqaring.

4
-1 -1 3 -1

0

6
-1 -1 2 -1 -1 -1

3