A. Qism satr

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Uzungligi $N$ bo`lgan $S$ satr beriladi, berilgan satrdan shunday eng uzun qism satrni topingki unda bir xil harf ko`pi bilan $K$ marta qatnashgan bo`lsin.

Masalan:
$N = 6, K = 1$
$S = “Husayn”$ bunda javob sifatida $“Husayn”$ olinsa bo`ladi, chunki hamma harf bir martadan qatnashgan.
Ammo:
$N = 7, K = 1 \newline S = “Hasanov”$
bunda esa $“Has”$ yoki $“sanov”$ ni olish mumkin xolos shart bo`yicha eng uzuni “sanov” olinadi.

Bunday satrlar juda ham ko`p bo`lishi mumkin, sizning vazifangiz satrning uzunligi topish.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ va $K (1 \le K \le N \le 10^5)$ butun sonlari mos ravishda satr uzunligi va qism satr uzunligi.

Keyingi qatorda $N$ uzunlikga ega lotin harflaridan iborat $S$ satr beriladi

Chiquvchi ma'lumotlar:

Yagona butun son, shartni qanoatlantirishi mumkin bo`lgan qism satr uzunligini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 1 Husayn	6
2	7 1 Hasanov	5

B. Massiv tengligi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga N ta sondan tashkil topgan A massivi berilgan. Siz massiv ustida quyidagi amalni cheksiz marotaba bajarishingiz mumkin.

A massiv orasidan K ta ketma-ket kelgan sonlarni tanlang va ularni hammasini shu ketma-ketlikning minimum soniga tenglang.

Topshiriq esa massivni minimal amallar orqali hamma elementlarini bir-biriga tenglashdir.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T (1 ≤ T < $10^5$ )

Har bir T uchun birinchi qatorida N va K butun sonlari (1 ≤ K≤ N ≤ $10^5$ ) N - massiv elementlari soni va K - ketma-ketlik uzunligi. T ta N ning umumiy yig'indisi ≤ $10^6$ ..

Har bir T uchun ikkinchi qatorida N ta sondan tashkil topgan A massivi, $a_1, a_2,...,a_N$ , (1 ≤ $a_i$ ≤ $10^5$ ) - massiv elementlari.

Chiquvchi ma'lumotlar:

Agar tenglashni iloji bo'lsa minimal amallar sonini, agarda iloji bo'lmasa -1 chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 11 4 1 16 20 7 1 9 3 16 17 16 13 11 5 17 15 11 1 8 20 14 9 18 11 4 8 2 15 2 11 16 6 18 3 16	3 3 7
2	1 5 2 2 4 10 15 1	4
3	4 10 3 16 10 2 15 5 7 7 16 10 11 4 3 20 4 18 1 9 5 12 5 14 16 14 16 10 4 4 6 3 13 19 4 8 3 16	5 2 2 3

#

INPUT.TXT

OUTPUT.TXT

1

3
11 4
1 16 20 7 1 9 3 16 17 16 13 
11 5
17 15 11 1 8 20 14 9 18 11 4 
8 2
15 2 11 16 6 18 3 16

3
3
7

2

1
5 2
2 4 10 15 1

3

4
10 3
16 10 2 15 5 7 7 16 10 11 
4 3
20 4 18 1 
9 5
12 5 14 16 14 16 10 4 4 
6 3
13 19 4 8 3 16

C. Boltavoy va guruhlarga ajratish #2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Boltavoyni eslaysizmi? U bugun yana o'z o'quvchilarini guruhlarga ajratmoqchi. Uning o'quvchilari har xil davlatlardan kelgani uchun u guruhlarni quyidagicha ajratmoqchi.

Hech qaysi o'quvchi guruhsiz qolib ketmaslik kerak
Har bir guruhda 1 ta yoki 2 tadan o'quvchi bo'lishi kerak.
Bitta davlatdan bo'lgan o'quvchilar bir xil guruhga tushib qolmasin.

Boltavoy guruhlar sonini minimallashtirmoqchi. Uning yaqin do'sti sifatida unga yordam bering

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida N (1≤N≤ $10^5$ ) - o'quvchilar soni

Keyingi qatorda N ta sondan tashkil topgan massiv $a_1$ , $a_2$ ,…, $a_N$ (1≤ $a_i$ ≤ $10^5$ ) - har bir o'quvchining qaysi davlatdan ekanligi.

Chiquvchi ma'lumotlar:

Chiqish faylining yagona qatorida bitta son - minimal guruhlar sonini chop eting.

Izoh:

Boltavoy guruhlarga ajirata olishi kafolatlanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 3 1 1 1 1 1	5
2	2 1 2	1

D. Futbol taktikasi

Xotira: 8 MB, Vaqt: 250 ms

Masala

Bilamiz har bir futbol jamoasida jami 11 ta o'yinchi bo'ladi va jamoa o'zi uchun taktika tuzib chiqadi. Juda ham mashhur taktikalarga misol qilib: 1-4-4-2 yoki 1-3-4-3 keltirishimiz mumkin. 1 - taktikani ko'rib chiqadigan bo'lsak. Jamoada har doim 1 ta darvozabon bo'ladi. 4 ta himoyachi, 4 ta yarim himoyachi va 2 ta hujumchi. Endi biz futbol o'yinini yana ham qiziqarliroq qildik va har bir jamoada N ta o'yinchi bo'lishini aytdik. Sizning vazifangiz esa jami nechta har xil taktikalar mavjud ekanligini aniqlash.
E'tibor qarating:

O'yinchilarning qaysi pazitsiyada turgani muhim emas, muhimi har bir pazitsiyadagi o'yinchilar soni.
Har bir pazitsiyada kamida 1 tadan o'yinchi bo'lishi kerak.
Darvozada faqatgina 1 ta o'yinchi o'ynay oladi.

Kiruvchi ma'lumotlar:

Kirish faylining yagona qatorida N soni (4 ≤ N ≤ $10^6$ ) - Jamoadagi o'yinchilar soni.

Chiquvchi ma'lumotlar:

Chiqish faylida berilgan topshiriqqa javobni chop eting.

Misollar:

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

E. Maksimal kuch yig'ish #HARD

Xotira: 16 MB, Vaqt: 1000 ms

Masala

!Diqqat bu Maksimal kuch yig'ish masalasining qiyinroq versiyasi va sizning janglaringiz soni cheklangan.

Bu masalani yechish uchun siz quyidagi o'yin oxirida maksimal kuchga ega bo'lishingiz kerak. Xullas, o'yin quyidagicha:

Avvalo siz o'yinni X kuch bilan boshlaysiz. Sizda k ta raqib bilan bellashish imkoniyati bo'ladi va siz ulardan foydalanishingiz yoki foydalanmasligingiz mumkin. Keyinchalik esa sizda ketma-ket kelgan $A_i$ kuchga ega bo'lgan raqiblarga to'qnash kelasiz. Agar u raqib sizdan kuchli bo'lsa siz hech narsa qila olmaysiz va agar unga hujum qilsangiz kuchingiz 0 ga tenglashadi. Lekin agar siz undan kuchli yoki kuchlaringiz teng bo'lsa siz unga hujum qilib mag'lub eta olasiz. Bu jang uchun sizning kuchingizga $A_i$ (raqibning kuchi) qo'shiladi.

Eslatma: Siz raqib bilan jang qilishingiz yoki qilmasligingiz mumkin. Agar siz jang qilmasangiz, keyingi raqib tomonga yo'l olasiz. Lekin siz hech qachon oldin sizga uchragan raqib bilan qayta uchrasha olmaysiz!

Kiruvchi ma'lumotlar:

1 - qatorda raqiblar soni n(1≤n≤25) va x ( $1<=x<=10^9$ ) va k (1≤k≤ $20$ )

Keyingi qatorda n ta son raqiblar kuchlari(1≤A≤ $10^9$ ).

Chiquvchi ma'lumotlar:

Yagona qatorda maksimal kuchni chiqaring.

Izoh:

Boshida bizda X = 3 bo'ladi va biz 2 kuchga ega bo'lgan raqibni yenga olamiz. Bundan keyin, X = 5. 6 kuchga ega raqibni yenga olmaymiz chunki 6>5. A = 5 bo'lgan raqibni yengamiz va X = 5+5 = 10. A = 8 ni ham yengib bo'lganimizda X = 10+8=18 bo'lar edi, ammo janglar soni cheklangan va javob x= 10.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 2 2 6 5 8	10