A. Matritsaning maksimal yig'indisi

Xotira: 32 MB, Vaqt: 1000 ms

Sizga 2N×2N o’lchamli matritsa berilgan. Siz 0 yoki bir necha marotaba matritsaning ixtiyoriy qatori yoki ixtiyoriy ustunini tanlab teskarisiga o’girishingiz mumkin. Shundan so’ng siz matritsaning yuqori chap burchagidagi N×N qism matritsaning yig’indisini hisoblaganingizda maksimal necha qiymatga ega bo’lishingiz mumkinligini aniqlang.

Masalan:

1	2	→	1	2	→	4	2
3	4		4	3		1	3

1
1 2
3 4

4

2
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108

414

B. Reyting

Xotira: 32 MB, Vaqt: 1000 ms

Baytlandiya mamlakatining BaytContest onlayn hakam tizimida har bir masala ishlangani uchun foydalanuvchiga manfiy bo’lmagan ma’lum bir bal qo’shilib boradi. Bu onlayn hakamda foydalanuvchilar reytingi ularning yig’gan ballariga bog’liq, ya’ni eng yuqori bal olgan foydalanuvchi 1-o’rin, eng kam bal yig’gan foydalanuvchi oxirgi o’rinda turadi, bir xil bal yig’gan foydalanuvchilar esa bir xil o’rinda bo’lishadi. Masalan jami 4 ta foydalanuvchi bo’lsa va ularning yig’gan ballari [100, 90, 90, 80] bo’ladigan bo’lsa, bu foydalanuvchilarning tizimdagi joriy reytingi [1, 2, 2, 3] kabi bo’ladi.

Megaboy BaytContest tizimida ro’yxatdan o’tganidan so’ng jami M ta masalani ishlab bo’lganiga qadar tizimdan undan boshqa hech bir foydalanuvchi foydalanmagani ma’lum.

7
100 100 50 40 40 20 10
4
5 25 50 120

6
4
2
1

C. Shaxmat musobaqasi

Xotira: 16 MB, Vaqt: 1000 ms

Baytlandiya mamlakatida shaxmat o’yinchilar jami 100 ta darajaga bo’lingan, 1-darajali shaxmat o’yinchisi strategik jihatdan eng kuchsiz hisoblanadi, 100-darajali shaxmat o’yinchisi esa strategik jihatdan eng kuchli hisoblanadi. Va yanam shu ma’lumki, bu mamlakatda strategik kuchli o’yinchi doim shaxmat musobaqasida strategik kuchsizroq o’yinchining ustidan g’alaba qozongan, strategiyasi tenglar esa o’yinda teng kuchli bo’lib doim during natija qayd etishgan. Bu mamlakatda shunday kitob borki, uni 1 marotaba o’qigan shaxmatchining strategiyasi 1 ga ortadi, bu kitobni bir necha marotaba o’qib chiqish mumkin, va har o’qiganda strategik darajasi 1 ga ortib boraveradi (100-darajaga yetgandan so’ng strategik daraja ortmaydi).

Megaboy xalqaro shaxmat musobaqasining saralash bosqichiga qatnashmoqchi, hozirda uning strategik darajasi k ga teng. Boshqa ishtirokchilardan farqli o’laroq Megaboy shaxmat musobaqasi tashkilotchisining o’g’li va u otasining yordamida o’z raqiblarining strategik kuchlilik darajalarini aniqlab oldi. Uning aniqlashicha musobaqa jarayonida unga jami N ta raqib to’g’ri keladi. O’yinda keyingi bosqichga faqatgina hech kimga yutqazmagan o’yinchilargina chiqa oladi. Siz Megaboy keyingi bosqichga o’ta olishi uchun shaxmatchilar kitobini eng kamida necha marotaba o’qib chiqishi kerakligini aniqlang.

5 4
1 6 3 5 2

2

D. O’rmon

Xotira: 16 MB, Vaqt: 1000 ms

Sizga o’rmon berilgan (oddiy bog’lanishlardan iborat, sikl mavjud bo’lmagan graf). 

Har bir daraxtda tugunlar soni juft bo’ladigan qilib o’rmondan maksimal sondagi qirralarni olib tashlang.

Misol uchun tugunlar soni 4 bo’lgan quyidagi daraxtdan 1 ta qirrani olib tashlash mumkin:

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

2

E. Adizning birlashtirish algoritmi

Xotira: 32 MB, Vaqt: 2000 ms

Laziz Adizga V massivlar to’plamini M massivga birlashtirish uchun berdi. Adiz massivlarni shunchaki ketma-ket birlashtirishni xoxlamay, o’zi massivni birlashtirishning boshqacha usulini o’ylab topdi. Uning birlashtirish usuli quyidagicha:

• M=[] bo’sh massivni yaratib oladi

• k=V massivlar to’plamidagi massivlar soni

• V to’plamda kamida 1 ta bo’sh bo’lmagan massiv mavjud bo’lsa

  • T = [] bo’sh massivni oladi

  • i = 1

  • i <= k shart qanoatlansa

    • agar Vi bo’sh bo’lmasa

      • Vi ning birinchi elementini o’chirib, uni T massivga qo’shadi

    • i = i + 1

  • T bo’sh bo’lib qolmaguniga qadar

    • T dan eng kichik elementni o’chirib M ning davomidan qo’shadi

• M ni chop etadi

Quyidagi misolda ko’ramiz: V={[3, 5], [1], [2, 4]} bo’lsin

Shunda Adiz quyidagicha amallar ketma-ketligini bajaradi:

Laziz o’zidagi V massivlar to’plamini Adizga berganidan so’ng Adiz o’zining birlashtirish algoritmi orqali massivlarni birlashtirib hosil bo’lgan M massivni Lazizga berdi. Bir necha kundan so’ng Laziz o’zidagi V massivlar to’plamini yo’qotib qo’ydi, unda hozir Adiz birlashtirib bergan M massiv bor xolos. Endi u o’zining V to’plamini qayta tiklamoqchi.

 

3
1 2 3

4

3
2 3 1

3