A. Shirinliklar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Chap tomondagi vazada N ta shokolad, o'rtadagisida M ta va o'ngdagida esa K ta shokolad bor. Aziz shokoladlarni quyidagidek yeydi. Avval chapdagi vazadan, keyin o'rtadagi, o'ngdagi, o'rtadagi, chap, o'rta, o'ng (ya'ni chapdan o'ngga, o'ngdan chapga). Agar qaysidir vazadan shokolad tugab qolgan bo'lsa, u yeyishni to'xtatadi. Siz Aziz jami nechta shokolad yeyishini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T (1≤T≤\(10^5\)) - testcaselar soni.

Har bir T uchun N,M,K butun sonlari (1≤N,M,K≤\(10^5\)) - har bir vazadagi shokoladlar soni.

Chiquvchi ma'lumotlar:

Har bir T uchun bitta qatorda jami yeyilgan shokoladlar sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 2 3 1 3 7 6 3 1 4	6 12 3
2	1 6 1 4	3

B. Maksimal kuch yig'ish #EASY

Xotira: 20 MB, Vaqt: 1700 ms

Masala

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

Birinchi qatorda testlar soni - t(1≤t≤100) kiritiladi.

Har bir test-case ichi quyidagicha bo'ladi:

1 - qatorda raqiblar soni n(1≤n≤10\(^5\)) va x (\(1<=x<=10^9\))

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 darajaga ega bo'lgan raqibni yenga olamiz. Bundan keyin, X = 5. 6 darajadagi raqibni yenga olmaymiz chunki 6>5. A = 5 bo'lgan raqibni yengamiz va X = 5+5 = 10. A = 8 ni ham yengib bo'lganimizdan keyin X = 10+8=18 bo'ladi.

Misollar:

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

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

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

F. FEKUB - Faktoriallik EKUB

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga n, a, b sonlari berilgan. n sonining a factorial darajasi va n sonining b factorial darajasining Eng katta umumiy bo'luvchisini toping. Aniqroq qilib aytadigan bo'lsak quyidagini toping.

EKUB(\(n^{a!}\),\(n^{b!}\))

Agar yechim juda ham katta bo'lib ketadigan bo'lsa, yechimning 1000000007 ga qoldig'ini chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T ( 1 ≤ T ≤ \(10^5\)) - testcaselar soni
Har bir T uchun yagona qatorda a, b, n ( 1 ≤ a, b, n ≤ \(10^5\))

Chiquvchi ma'lumotlar:

Har bir T uchun yagona qatorda yechimni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 1 2 3 3 1 2 5 1 3 4 5	2 1 1 15625

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