A. Yoqimli raqam

Xotira: 32 MB, Vaqt: 1000 ms

Diyorbek mashinalarni katta ishqibozi. U har doim mashinalarga qarab ularni davlat raqamlarini eslab qolishga urinadi. U mashina raqami faqat 5 va 7 dan tashkil topgan bo'lsa uni yoqimli deb hisoblaydi. 

Endi uni bir savol qiziqtirib qoldi. 1 dan \(n\) gacha nechta yoqimli son mavjud.

29

2

55

3

32

2

B. Daraxtdagi LIS

Xotira: 32 MB, Vaqt: 1000 ms

N ta tugundan tashkil topgan daraxt mavjud. \(i-\)yo'l \(u_i\) va \(v_i\) tugunlarni o'zaro bog'laydi va qiymati \(a_i\) ga teng. 1 dan N gacha bo'lgan har bir k butun soni uchun quyidagini aniqlang:

• Yo'llarga yozilgan butun sonlarni 1-yo'ldan k-yo'lgacha bo'lgan eng qisqa yo'l bo'ylab ular paydo bo'ladigan tartibda qatorlab ketma-ketlik hosil qilamiz.  Ushbu ketma-ketlikning eng uzun ortib boruvchi pastki ketma-ketligi (LIS)ining uzunligini toping.

Bu yerda uzunligi \(L\) boʻlgan \(A\) ketma-ketlikning eng uzun ortib boruvchi pastki ketma-ketligi \(M\) ning mumkin boʻlgan eng katta qiymatiga ega boʻlgan \(A_{i_1}\) ,\(A_{i_2}\) ,...,\(A_{i_M}\) qatori boʻlib, \(1≤i_1 <i_2 <...<i_M ≤L\) va \(A_{i_1} < A_{i_2} <...< A_{i_M}\) bo'ladi.

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

1
2
3
3
4
4
5
2
2
3

C. Avtobus chiptachisi Shermat

Xotira: 32 MB, Vaqt: 1000 ms

Dasturlashdan bo'sh vaqtlarida Shermat avtobusda chipta sotishga amakisiga yordam beradi. Bu jarayon aslida juda oson, ammo, naqt pulda yo'lkirani to'laydiganlar uni doim qiynab keladi. Chunki ularga qaytim qaytarish juda qiyin. Yo'lkira narxi aslida 2000 so'm. Yo'lovchilar esa odatda 5000 so'mlik yoki 2000 so'mlik kupyuralarda to'lashadi. 2000 so'm to'laydiganlarda muammo yo'q ammo 5000 to'laydiganlarga qaytim topib berish muammoroq. Shu uchun Shermat ularni jazolash maqsadida ularga 2000 so'm qaytim qaytaradi.

Shermat statistika va ehtimollilik fanlarini yoqtiradi. U kunlik kuzatishlari natijasida shunday xulosaga keldi. Bugun avtobusga \(n\) ta 2000 so'mlik kupyurada to'laydigan va \(m\) ta 5000 so'mlik kupyurada to'laydigan yo'laovchilar chiqishi kutilmoqda. Hamda safar boshida Shermatda  \(k\) ta 2000 so'mlik kupyuralar bor qaytim qaytarish uchun. Endi sizdan butun kun davomida qaytim qaytarish bilan muammo bo'lmasligi ehtimolliligini aniqlashda yordam so'ramoqda. Bunda har bir yo'lovchining avtobusga chiqish tartibi teng ehtimollilikka ega.

5 3 1

0.857143

0 5 5

1

0 1 0

0

D. Xor va summa

Xotira: 32 MB, Vaqt: 1000 ms

Sizga L soni berilgan. Quyidagi shartlarni qanoatlantiradigan juftliklar sonini hisoblang:

• \(a + b \le L\)
• \(a + b = a\ XOR\ b\)

10

5

1011

45

E. To'g'ri chiziq

Xotira: 32 MB, Vaqt: 1000 ms

Rustam yaqinda maktabda to'g'ri chiziqlar mavzusini o'rgandi. Endi uni bir savol qiynamoqda. Bir nechta nuqtalar berilgan ular bir to'g'ri chiziqda yotadimi yoki yo'q?

1 2 3 4 5 6
2 3 4 5 6 7

HA

1 2 3 4 5 7
1 2 4 5 6 7

YO'Q

F. Chigirtka

Xotira: 32 MB, Vaqt: 1000 ms

Chigirtka bir sakradi, ikki sakradi, uchinchisida qo'lga tushdi.

Shohruh bir chigirtkani ushlab oldi. Endi uni mehmon qilmoqchi. Dastlab u chigirtkani \(n\times m\) o'chamdagi qutiga joylashtirmoqchi. U chigirtkani joylashtirishdan oldin har bir yacheykalarga bittadan chigirtka yoqtiradigan hashorat joylashtirdi. Chigirtka bir sakrashda verikal yoki gorizantal yo'nalishda aynan \(d\) katakka sakrashi mumkin. Faqat birgina sharti u qutidan chiqib keta olmaydi. Endi sizdan savol chigirtka eng ko'p hashorat yeya olishi uchun dastlabki joylashuvi bo'lishi mumkin bo'lgan yacheykalar sonini toping.

2 3 1000000

6

3 3 2

4

1 2 3

2

G. Orollar urushi

Xotira: 32 MB, Vaqt: 1000 ms

N ta shahar va ularni bog'lovchi N-1 ta ikki tomonlama ko'prik mavjud. \(1 \le i \le N-1\) uchun \(i-\) tugun \(i\) va \(i+1\) shaharlarni o'zaro bog'laydi. Ba'zi orollar orasida nizo kelib chiqdi va endi shu orollarning biridan ikkinchisiga borish imkonsiz bo'lishi lozim. Buning uchun qaysidir ko'prikni buzish mumkin. Barcha nizolarni hal qilish uchun kamida nechta ko'prikni buzish talab etiladi.

5 2
1 4
2 5

1

9 5
1 8
2 7
3 5
4 6
7 9

2