A. Satrchalar

Xotira: 128 MB, Vaqt: 1000 ms

Dilshod "qog'oz kesish" ni yaxshi ko'radi: u gazeta sarlavhasidan belgilarni kesib tashlaydi va ulardan boshqa satr hosil qilish uchun qayda joylashtirib chiqadi.

Unda $n$ ta $S_1, S_2 \dots S_n$ gazeta sarvlahalari bor va u ulardan bittasini tanlab yangi satr yaratmoqchi. U hali qaysi sarvlahani tanlashini bilmaydi, shuning uchun sarlvaha tanlashidan qat'iy nazar, aniq yasay oladigan eng uzun so'zini topmoqchi. 

Bunda siz unga yordam bering. 

3
abcca
ca
cccca

ac

2
bcde
fghij

-1

B. TTMT

Xotira: 128 MB, Vaqt: 1000 ms

Komiljon hozirgina uzunligi $n$ ga teng va faqatgina ‘T’ va ‘M’ harflaridan tuzilgan $s$ satrini topib oldi. Komiljon $TTMT$ satrini yaxshi satr deb hisoblagani sababli, $s$ dagi yaxshi satrlar sonini maksimallashtirmoqchi. Satrdagi $TTMT$ satrlarning soni $s_is_{i+1}s_{i+2}s_{i+3} = TTMT$ shartini qanoatlantirgan $i$ larning soniga tengdir.

Komiljon bitta amalda $s$ satrining istalgan joyiga ‘T’ yoki ‘M’ satrlardan birini joylashtirishi mumkin. Bu amalni birinchi marta bajarish uchun badal olinmaydi, ammo ikkinchi marta bajarish uchun 1 tanga, uchinchi marta bajarish uchun 2 tanga va h.k. davom etadi.

Komiljonning umumiy kayfiyati, 

(natijaviy satrdagi $TTMT$ lar soni) $-$ (jami to'lagan tangalari soni)

ga teng. Sizga boshlang'ich $s$ satrli ma'lum, uning kayfiyatining maksimal qiymatini toping.

4
3
TTT
5
TTTTM
4
TMTM
9
TTMTTTTMT

1
1
1
3

C. RPG

Xotira: 128 MB, Vaqt: 2000 ms

Komiljon hozirda RPG turidagi kompyuter o'yinini o'ynamoqda. Hozirda uning vazifasi joni $H$ birlikka teng maxluqni zarb etishdir. Maxluqning joni 0 yoki undan kamroq bo'lsa, u zarb etiladi.

Buning uchun u o'zida bor $n$ ta $1,2,\dots n$ bilan raqamlangan qurollaridan foydalana oladi. Biroq har bir qurol ko'pi bilan 1 marta ishlatilishi mumkin, bundan tashqari qaysidir qurolni ishlatganidan so'ng, Komiljon biroz vaqt ichida umuman hech qaysi qurollardan foydalana olmaydi.

Aytaylik Komiljon $i$-qurolini o'yin boshlanganidan $x$ soniya o'tgach ishlatsin. Komiljonning ushbu qurolini ishga tushirganidan so'ng $t_i$ soniya dam olishi kerak. Bu degani Komiljon $(x + t_i)$-soniyagacha hech qaysi qurollardan foydalana olmaydi. Bundan tashqari qurol o'zining aktiv turish vaqti $len_i$ ega. Yanada aniqroq aytsak, qurol ishga tushilrilganidan $(1 \leq j < len_i)$ soniya o'tkach, ya'ni o'yinning $(x + j)$-soniyasida, maxluqning joni $d_{i, j}$ miqdorga kamayadi. E'tibor bering, $len_i$ soni $t_i$ dan kattaroq bo'lishi mumkin. Ya'ni qurol ishga tushirilganch juda uzoq vaqt ishlab turilishi mumkin va uning effekti(aktiv turishi) boshqa qurollarniki bilan ustma ust bir vaqtda ishlatilishi mumkin.

O'yin 0-soniyada boshlanadi. Qurollarni to'g'ri ketma ketlikda ishlatgan holda, maxluqni eng minimal nechanchi soniya ichida zabt etib bo'lishini toping. Agar barcha qurollarini ishlatib bo'lgandan so'ng ham maxluq zabt etilmasa, ekranga $-1$ chiqaring.

3
1 100
5 3
50 60 70
2 100
2 3
40 40 100
100 2
20 5
1 1000
1 1
999

1
2
-1

D. Super Struktura

Xotira: 256 MB, Vaqt: 2500 ms

Uzunligi $n$ ga teng $a$ massivi berilgan. Sizning vazifangiz jami $q$ ta 4 xil turdagi so'rovlarga javob berish.

• $1 \ x \ y \ z$ so'rovi kiritilganda, har bir $1 \leq i \leq n$ soni uchun, agar $x \leq a_i \leq y$ sharti bajarisa, $a_i \leftarrow z$ amalini bajaring. ($\leftarrow$ amali o'zlashtirishni anglatadi).
• $2 \ l \ r \ c$ so'rovi kiritilganda, har bir $l \leq i \leq r$ uchun $a_i \leftarrow c$ amalini bajaring.
• $3 \ p$ so'rovi kiritilganda, $a_p$ ni ekranga chiqaring.
• $4 \ p$ so'rovi kiritilganda, $1 \leq i \leq n$ va $a_i > a_p$ shartini qanoatlantiruvchi $i$ lar sonini chiqaring.

5 8
1 2 3 2 1
4 5
1 1 1 4
4 3
2 1 2 1
4 4
2 2 3 7
4 1
3 4

3
2
2
4
2

E. Red-Blue Tree

Xotira: 128 MB, Vaqt: 1000 ms

Dilshod va Qodir o'yin o'ynashmoqchi. Bu safar ularda $n$ ta tugundan iborat bog'langan siklsiz graf, ya'ni daraxt bor. Daraxtning ba'zi tugunlari qizil, qolganlari esa ko'k rangga bo'yalgan.

No'malum usul orqali, o'yinni boshlash uchun boshlang'ich tugun tanlanadi va u yerga o'yin fishka qo'yiladi. Bundan so'ng o'yinchilar navbatma navbat quyidagi amallarni bajaradi:

• O'yinchi hozirda fishka turgan tugunga ulangan hamda oldin bloklanmagan qirra tanlaydi. Agar qirrani tanlashning imkoni bo'lmasa, o'yin o'z yakuniga yetadi;
• O'yinchi qirradan foydalanib, fishkani qo'shni tugunga olib qo'yishni yoki fishkani joyida qoldirishni tanlaydi;
• Tanlangan qirra bloklanadi. E'tibor bering bloklangan qirralardan boshqa foydalanish mumkin emas. 

O'yin yakunida, Fishka qizil rangli tugunda qolsa, Dilshod yutadi, ko'k rangli tugunda qolsa, Qodir yutadi. O'yin doimo Dilshodning navbati bilan boshlanadi. Ikkala o'yinchi ham optimal o'ynaydi.

Hozirda Dilshod o'yin qaysi tugunlardan boshlansa, u g'olib bo'lishini bilmoqchi. Buni hisoblash uchun unga yordam bering.

4
2 2 1 2
1 3
4 2
2 1

4
1 2 3 4

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

4
1 2 3 5

5
1 1 1 1 1
1 3
2 3
1 4
5 2

0

F. Sandwich

Xotira: 128 MB, Vaqt: 1000 ms

Komiljon Sandwich yeyishni yoqtiradi, va bugun u $N$ ta sandwich ta'tib ko'rmoqchi.

Komiljon Sandwich xarid qilayotgan do'konda chegirma davom etmoqda. Bir dona Sandwichning narxi $30000$ so'm, lekin bir kishi tomonidan sotib olinadigan har sakkizinchi(8, 16, 24, 32, 40…) Sandwich, bor yo'g'i $8000$ so'mga sotiladi.

Komiljon $N$ ta sandwichning hammasini sotib olishi uchun, o'zi bilan kamida necha pul olib chiqish kerak.

3

90000

9

248000

28

774000

G. Musobaqa

Xotira: 128 MB, Vaqt: 1000 ms

Anvar navbatdagi dasturlash musobaqasida qatnashmoqda. Musobaqada ishtirokchilarga $K$ta masala berilgan. Anvar ulardan $X$tasini ishladi va jami $Y$ daqiqa jarima oldi.

Buni qarangki, afsungar Moldevort unga yordam bera olishini aytdi. Moldevortda $N$ta masala afsuni hamda $M$ta jarima afsuni mavjud. $i$-masala afsuni $A[i]$ tanga turadi va Anvarning ishlagan masalalari sonini bittaga orttirib qo'yadi (ortiqcha jarimasiz). $j$-jarima afsuni esa $B[j]$ tanga turadi va Anvarning umumiy jarimasi miqdorini bittaga kamaytirib qo'yadi.

Anvarda jami $C$ tanga bor. Anvar tangalarini optimal usulda ishlatsa, uning eng yaxshi natijasini (masala va jarima miqdorini) chiqaring.

E'tibor bering, ishtirokchilar orasida shubha uyg'onmasligi uchun, Anvar ishlagan masalalari soni $K$dan oshmasligi, uning jarimasi esa $0$dan kam bo'lmasligi kerak.

*Yakuniy natijalarda avval eng ko'p masala ishlaganlar, teng bo'lib qolgan taqdirda eng kam jarimaga ega ishtirokchilar bo'yicha aniqlanadi.

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

5 63

3 2 21 0
1 2
1
1 1

2 21

H. O'suvchi qism ketma-ketlik

Xotira: 256 MB, Vaqt: 2000 ms

Ahmadjonda uzunligi $n$ bo'lgan $p$ permutatsiya* bor. U $1 \leq i_1 \leq i_2 \leq \dots i_k \leq n$ ketma-ketlikni sekin o'suvchi deydi, agarda har bir $1 \leq j < k$ uchun $p_{i_j} + 1 = p_{i_{j+1}}$ sharti bajarilsa.

Boshqa so'z bilan aytgancha, $p_{i_1},p_{i_2},\dots p_{i_k}$ ketma-ketlik, $x, x + 1, \dots x + k-1$ shaklidagi ketma ket sonlardan tashkil topsin.

Qodirjon Ahmadjonga $q$ ta $(l, r)$ turdagi so'rovlarni beradi. Har so'rovga Ahmadjon $p$ massivining $[l, r]$ oralig'idagi eng uzun sekin o'suvchi ketma-ketlikning uzunligini aytishi lozim. Ahmadjonga yordam bering.

*Permutatsiya bu 1 dan $n$ gacha sonlarning har biri 1 martadan qatnashgan massivdir.

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

2
3
2