A. Bog`bon Samir

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Samir bog`idagi daraxtlarn sug`ormoqchi. U bitta daraxtga ai ta chelakda suv quyishi kerak va uni bog`ida n ta daraxt bor. U faqat birdaniga 2 ta chelakda suv toshil oladi va qo`lida nechta chelak bo`lsa ham hammasini bitta daraxtga quyishga majbur. U hamma daraxtlarni to`liq sug`orishi uchun nechta energiya sarflashi kerak. Bitta energiyada 2 ta chelak suv quyishi mumkin va bitta energiyani hammasini bitta daraxtga ishlatadi!!!

Kiruvchi ma'lumotlar:

n -> daraxtlar soni

a massiv n ta elementdan iborat

Chiquvchi ma'lumotlar:

nechta energiya sarflashi kerakligi

Misollar:

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

B. Yozda qoraydim

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Yoz fasli ham tugay deb qoldi, yozda Muhammadsiddiq va Nusrat shaharga bordi, ular Toshkent shahridagi eng baland binoga chiqishdi va o'sha yerdan mehmonxona gaplashishdi, mehmonxona derazasidan butun shahar ko'rinib turardi, shunda ikki do'st shahardagi bir narsani tushunib qolishdi ! Ularning derazasidan bir qator qurilgan ammo har xil qavatli binolar jamlanmasini ko'rishdi, tong saxarda bazi binolarga quyosh nuri tushar ekan, bazi binolarga esa o'zidan oldingi binolar baland bo'lganligi uchun umuman quyosh nuri tushmas edi, ular birgalashib quyosh nuri $N$ ta binodan qaysilariga tushishi mumkinligini aniqlashmoqchi bo'lishdi, sizning ularga yordamingiz kerak

Kiruvchi ma'lumotlar:

kirish qismida birinchi qatorda bitta butun son $N(1 \leq N \leq10^3)$ - binolar soni

ikkinchi qatorda $N$ ta butun son $H$ - binolar balandliklari beriladi

Chiquvchi ma'lumotlar:

chiqish qismida nechta bino nurdan to'silib qolishini hisoblang

Misollar:

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

C. Boshlang`ich graflar tushunchasi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Siz A shaxardan B shaxarga borishni rejalashtirib yozib qo`ygansiz qaysi qaysi yo`llardan yurishni lekin boradigan manzilingizni unutib qo`ydingiz. Aksiga olib yo`nalishlaringiz ham chalkashib ketgan lekin qaysi shaxardan boshlashingiz aniq ma`lum va ro`yhatdagi eng birinchi shahardan boshlaysiz! Sizning vazifangiz siz oxirgi bo`lib qaysi shaxarga borishingizni qaytadan topish.

Kiruvchi ma'lumotlar:

$N$ -> Necha marta ko`chish birinchi qatorda

keyingi $N$ ta qatorda yo`nalishlar

Chiquvchi ma'lumotlar:

oxirgi bo`lib qaysi shaharga yetib borishingiz

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 a b b c	c

D. Hisobla-chi !

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Muhammadsiddiqga vazifa berildi, lekin u buni bajarishga qiynalyapti, sizni unga yordamingiz kerak. U $1$ dan $N$ gacha bolgan sonlarni qog'ozga yozib chiqmoqchi, lekin u avval nechta raqam yozishini hisoblab chiqmoqchi, lekin shuni hisoblashga ham erinyapti, siz unga bu sonlarni hisoblab beruvchi dastur tuzib bering

kelasi masalada siz unga sonlarni yozib ham berasiz 😁

Kiruvchi ma'lumotlar:

kirish qismida bitta butun son $N(1\leq N \leq 10^{18})$ - Muhammadsiddiq yozmoqchi bo'lgan son beriladi

Chiquvchi ma'lumotlar:

chiqish qismida masala javobini chop eting

Izoh:

$N=13$ bo'lsa $12345678910111213$ raqamlarini yozadi va bu raqamlar soni $17$ ta

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	13	17

E. Muhammadsiddiq

Xotira: 32 MB, Vaqt: 500 ms

Masala

Muḥammadsidḋiq juda juda aqlli, bоshқacha qilib aytadigan bоlsak ushlagan joýini qo‘yib yubоrmaydiganlardan, u dasturlashni oʻrgandi. U roboconteѕt kabi saýtlarḋa masala ishlashni bоshladi, tirishqoq Muḥammadsidḋiq bir yoki bir necha kún masala ishladi, u ḥar kúni oʻsish tartibida masalalar ishlardi, birinchi kún biṭṭa masala, ikkinchi kúni 2 ta masala, 3-kuni еsa uchta va hokazo, lekin dam оlgani hisobiga bu urinіshlari kúnlik ritmga taѕir qilishini istamadi, agar uni 4-kuni (bir kún) dam оldi deb hisoblasak, 5-kúni 5 ta masala ishlardi.

Kiruvchi ma'lumotlar:

birinchi qatorda bitta butun son $X(1\leq X \leq 10^5)$ - nechta saytda ishlashi,

keyingi $X$ ta qatorda 3 ta butun son, har bir sayt uchun masala ishlashni boshlagan kunidan oxirgi marta masala ishlagan $M_1$ kunigacha bo'lgan kunlar soni, orada $N$ kun dam olgani va yana $M_2$ kun ishlagan masalalar soni beriladi $1\leq M_1,N,M_2 \leq 10^9$

Chiquvchi ma'lumotlar:

chiqish qismida Muhammadsiddiq $X$ ta saytda ishlagan masalalari sonlarini chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 1 1 4 3 5 5 1 2	11 60 30

F. Joyini topdi

Xotira: 96 MB, Vaqt: 1000 ms

Masala

Bu masalamiz ham Nusrat haqida bo`lishi mumkin edi lekin Nusrat hozir juda juda uzoqlarda. Lekin bizga judayam yaqin bo`kgan bir joyda Muhammadrizo yashaydi. U raqamlar bilan o`ynashni yaxshi ko`radi va sal avval akasining massividan tasodifiy bir elementni olib o`ynayotgandi. Akasi har doim massivlarini tartiblab yuradi. Lekin endi u elementni joyini topolmayapti qayerga qo`yish kerakligini topolmayapti. Unga sizning yordamingiz kerak iltimos unga yordam bering.

Kiruvchi ma'lumotlar:

$N$ -> Muhammadrizoning akasining massivining uzunligi $1 \leq N \leq 10^{9}$

keyingi qatorda N - 1 ta son ya`ni massiv

uchinchi qatorda Muhammadrizo olib qo`ygan son

Chiquvchi ma'lumotlar:

elementni indexini topishingiz kerak

Izoh:

agar yo`qolgan son bilan teng elementlar mavjud bo`lsa u eng birinchisini olgan deb hisoblang

Misollar:

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

G. Quvnoq Prefixlar

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Nusrat yoshligida raqamlar bilan o'ynashni yaxshi ko'rardi. U har doim raqamlarni almashtirib o'ynaydi. Lekin bu safar bu o'yiniga biroz o'zgartirish kiritmoqchi. Uni N ta raqami bor uni A massivni ichiga joylashtirib chiqqan. Va uni ichidagi ba'zi elementlarni o'zgartirib chiqmoqchi bo'ldi. Lekin bu hammasi ham emas u massivni prefixlari eng maksimal bo'lgan manfiy joyni iloji boricha kichiklashtirmoqchi (Yaxshiroq tushunish uchun izohga qarang) va bu sonni q bilan belgilaydi. Siz massivni istalgancha o'zgartirishingiz mumkin. Lekin bitta sharti bor va shart quyidagicha: Sizga p massiv beriladi va bu massiv 1 va 0 lardan iborat bu massivning uzunligi N asl massivning uzunligi bilan teng agar l[i]=1 bo'ladigan bo'lsa siz A[i] sini joyini o'zgartirolmaysiz, agar l[i]=0 bo'lsa va boshqa l[j]=0 bo'lsa siz A[i] ni va A[j] sini o'rnini almashtirishingiz mumkin va bu ishni istaganingizcha takrorlashingiz mumkin. Tasavvur qiling sizda pref nomli massiv bor va bunda A massivning barcha prefix yig'indilari yozib chiqilgan. misol uchun A = [1, 2, 3, 4, 5] bo'ladigan bo'lsa pref = [1, 3, 6, 10, 15] bo'ladi.

Bu yerda esa q quyidagicha aniqlanadi:

A massivining prefix yig'indilari orasida manfiy bo'lib qoladigan eng oxirgi indeks q deb belgilanadi. Agar prefixlarning ichida umuman manfiy qiymat bo'lmasa, unda q = 0 deb olinadi. Masalan, agar A = [2, -5, 1, 3] bo'lsa, pref = [2, -3, -2, 1] bo'ladi va bu yerda oxirgi manfiy qiymat 3-elementda (-2) joylashgan — demak, q = 3 bo‘ladi.

Nusrat shu q ni iloji boricha kichikroq son qilmoqchi. Lekin hozir Nusrat judayam erinchoq bo'lib qolgan aslida u bu vazifani bajara oladi lekin bunga erinyapti shu uchun sizning yordamingizga muhtoj. Sizning vazifangiz qaysi kombinatsiyadagi q soni eng kichik bo'lsa shu massivni topishda Nusratga yordam berishdan iborat.

Kiruvchi ma'lumotlar:

T - testlar soni $1<=T<=1000$

keyin T marta:

N -> A va p massivlar uzunligi $1<=N<=100$
A -> butun sonlardan iborat N uzunlikdagi massiv $-10^9<= A <= 10^9$
p -> 0 va 1 lardan iborat N uzunlikdagi ikkilik massiv

Chiquvchi ma'lumotlar:

masalada so`ralgan narsani chop eting

Izoh:

1-testda massivdagi har bir elementni o`zgartirishimiz mumkin ekan.

Bu holatda biz 1 2 3 variantini oladigan bo`lsak pref = [1, 3, 6] 3-son bunda maximal bo`ladi. Bu testda manfiy sonlar bo`lmagani uchun masalani asl mohiyati bu yerda ko`rinmayapti. Demak massivni har bir elementi musbat son bo`ladigan bo'lsa bizda istalgan massiv yechin bo'lolishi mumkin ekan

2-testda esa biz faqat birinchi uchta element — ya’ni 0, 1, va -4 sonlarini o‘zaro almashtirish huquqiga egamiz. Chunki aynan shu elementlar P massivida 0 ga mos keladi, ya’ni ular "erkin".

To‘rtinchi (6) va beshinchi (3) elementlar esa qulflangan bo‘lib, o‘z joyidan siljitib bo‘lmaydi.

Bu uchta erkin sonni shunday tartibda joylashtirish kerakki, prefix yig‘indilar orasida manfiy qiymat iloji boricha kam va erta tugaydigan bo‘lsin. Eng optimal joylashtirish:
-4 0 1 6 3

Bu holatda prefixlar quyidagicha bo‘ladi:

p1 = -4

p2 = -4 + 0 = -4

p3 = -4 + 0 + 1 = -3

p4 = -3 + 6 = 3

p5 = 3 + 3 = 6

Bu yerda manfiy bo‘lib qoladigan eng oxirgi prefix p3 (ya'ni 3-pozitsiya). Demak, q = 3 bo‘ladi.

Agar boshqa tartiblarni sinab ko‘rsak, q bundan katta bo‘lishi mumkin, shuning uchun bu variant eng optimal natija hisoblanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 3 1 3 2 0 0 0 5 0 1 -4 6 3 0 0 0 1 1	1 2 3 -4 0 1 6 3

H. Labirintsimon graflar

Xotira: 54 MB, Vaqt: 1000 ms

Masala

Lochinbek maktab tomonidan uyushtirilgan musobaqada sayohat uchun vaucher yutib oldi va buni bitta sharti bor edi u sayohat davomida minimal miqdorda pul sarflashi kerak edi. U $n*m$ o`lchamdagi shaharlarni $1*1$-sida turibdi har bir shaharga kirish uchun to`lovlar mavjud u 1-shaharga kirish uchun ham to`lov qilishi kerak. u $m*n$-shaharga minimal pul sarflab o`tishi kerak u faqat o'ngdagi yoki pastdagi shaharlarga o'tishi mumkin! Siz unga minimal miqdorda qancha pul sarflashi kerakligini aniqlab bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda $n$ va $m$ beriladi $2<= n, m <= 1000$

keyin sizga $n*m$ o`lchamdagi matritsa beriladi bu matritsa shaharga kirish uchun qancha pul to`lash kerakligini bildiradi ya'ni narxlar matritsasi.

Chiquvchi ma'lumotlar:

Eng kamida qancha pul sarflab $n*m$-shaharga yetib borish mumkinligini chop eting!

Izoh:

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	7

I. Nusrat mukofot oldi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Nusrat Kiberxavfsizlik bo`yicha O`zbekistonda eng kuchlilaridan va u bugun Bankdan 1000000$ o'g'irlanishini oldini oldi. Va bunga mukofot sifatida ishxonasidan uni mediaparkdan olgan $X$ oylik kreditlarini to`lab berishlarini aytishdi. Nusrat bundan judayam xursand. Va hoziroq Mediapark ga yo`lga chiqdi. u yerda $N$ xil mahsulotlar bor ekan va bu maxsulotlarga necha oyga kreditga berilishi va narxini yozib qo`yishibdi. Nusrat bunday imkoniyat har doim ham bo'lavermasligini tushunib bu imkoniyatdan maximal foyda olmoqchi. Siz u Maximal qanchfoyda olishi mumkinligini aniqlab berishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$

Ikkinchi qatorda$X$

Uchinchi qatorda mahsulotlarning narxi $costs$ massivi beriladi va uning uzunligi $N$

To`rtinchi qatorda $months$ massivi mahsulotlarni necha oyga kreditga berilishi.

Chiquvchi ma'lumotlar:

maximal qancha foydalana olishi mumkinligini chop eting!

Izoh:

u har bir mahsulotdan istalgancha olishi mumkin!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 10 50 60 70 80 90 1 2 3 4 5	500

J. Nusrat mukofot oldi 2

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Nusrat Kiberxavfsizlik bo`yicha O`zbekistonda eng kuchlilaridan va u bugun Bankdan 1000000$ o'g'irlanishini oldini oldi. Va bunga mukofot sifatida ishxonasidan uni mediaparkdan olgan $X$ oylik kreditlarini to`lab berishlarini aytishdi. Nusrat bundan judayam xursand. Va hoziroq Mediapark ga yo`lga chiqdi. u yerda $N$ xil mahsulotlar bor ekan va bu maxsulotlarga necha oyga kreditga berilishi va narxini yozib qo`yishibdi. Nusrat bunday imkoniyat har doim ham bo'lavermasligini tushunib bu imkoniyatdan maximal foyda olmoqchi. Siz u Maximal qanchfoyda olishi mumkinligini aniqlab berishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$

Ikkinchi qatorda$X$

Uchinchi qatorda mahsulotlarning narxi $costs$ massivi beriladi va uning uzunligi $N$

To`rtinchi qatorda $months$ massivi mahsulotlarni necha oyga kreditga berilishi.

Chiquvchi ma'lumotlar:

maximal qancha foydalana olishi mumkinligini chop eting!

Izoh:

u bitta mahsulotni faqat 1 marta sotib oladi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 10 50 60 70 80 90 1 2 3 4 5	260