A. MAX oraliq

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga bir satr beriladi. Siz bu satrning yonma-yon bo'lgan belgilarning ASCII jadvalidagi o'rinlari ayirmasini modullarining maksimal qiymatini topishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda satrning uzunliki L (1≤L≤10**5)

Ikkinchi qatorda string S.

Chiquvchi ma'lumotlar:

Eng katta oraliqning qiymatini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 abcd	1
2	7 azd-,e3	25

B. Tanga to'la sandiqlar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Alisher Aliboboning xazina to'la g'orini topib oldi. U bu g'ordan aynan m tanga olib chiqmoqchi. Ammo u sandiq ichida qancha tanga bo'lsa shuncha tanga ola oladi. Unga tezroq Alibobo kelib qolmasidan oldin qaysi indeksdagi sandiqlarni olishini ayting.

Kiruvchi ma'lumotlar:

Birinchi qatorda g'ordagi sandiqlar soni n (1≤n≤100)

Ikkinchi qatorda g'ordagi har bir sandiqda qancha tanga borligi a (1≤ai≤100)

Uchinchi qatorda Alisher olmoqchi tangalar soni m (1≤m≤10000)

Chiquvchi ma'lumotlar:

Alisher eng kamida nechta sandiq tanlashi va qaysi indexdagi sandiqlarni tanlashi kerkaligini chop eting.

Izoh:

Indexlash 1 dan boshlanadi

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 7 3 2 31 5 8	2 2 5
2	3 1 1 1 3	3 1 2 3

C. Sehrli Kvadrat Yo'li

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga 𝑁 × 𝑁 o'lchamdagi butun sonlardan iborat matritsa berilgan. Siz matritsaning chap yuqori (1,1) burchagidan boshlaysiz va o'ng pastki (𝑁,𝑁) burchagiga borishingiz kerak. Ammo quyidagi shartlarga amal qilishingiz kerak:

Faqat pastga yoki o'ngga harakat qilish mumkin (orqaga yoki chapga qaytib bo‘lmaydi).
Harakatlanayotgan yo'lingizdagi sonlarning EKUB qiymati eng katta bo'lishi kerak.
Yo'l oxirida olgan eng katta EKUB qiymatining o'zi javob bo'ladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son N (2 ≤ 𝑁 ≤ 10) – matritsaning o'lchami.

Keyingi N qatorning har biri N ta butun sondan iborat bo‘lib, Aᵢⱼ (1 ≤ Aᵢⱼ ≤ 1000) qiymatlar bilan berilgan.

Chiquvchi ma'lumotlar:

Berilgan shartlarga mos keladigan eng katta EKUB ni chiqaring.

Izoh:

Siz eng katta EKUB bo'ladigan yo'lni tanlashingiz kerak:

6 → 12 → 18 → 30
Bu yo'lda EKUB(6, 12, 18, 30) = 6 bo‘ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 6 12 4 8 18 9 10 30 15	6

D. Sehrli Kvadrat Yo'li (Hard Version)

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga 𝑁 × 𝑁 o‘lchamdagi matritsa berilgan. Siz (1,1) dan (𝑁,𝑁) gacha yetib borishingiz kerak, ammo yo‘l uzunligi aniq 2 × 𝑁 − 1 bo‘lishi kerak va yo‘ldagi sonlar maksimal EKUK ga ega bo‘lishi lozim.

Bunda faqat quyidagi 3 yo‘nalishda harakatlanish mumkin:

Pastga (↓)
O‘ngga (→)
Diagonali pastga-o‘ngga (↘️)

Siz shunday yo‘lni tanlashingiz kerakki, yo‘ldagi sonlarning EKUK qiymati maksimal bo‘lsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son N (2 ≤ 𝑁 ≤ 15) – matritsaning o‘lchami.

Keyingi N qatorning har biri N ta butun sonni o‘z ichiga oladi: Aᵢⱼ (1 ≤ Aᵢⱼ ≤ 1000).

Chiquvchi ma'lumotlar:

Minimal EKUK qiymatini chiqaring.

Izoh:

Eng yaxshi yo‘llardan biri:
8 → 12 → 15 → 21 → 35

Bu yo‘lda EKUK(8, 12, 15, 21, 35) = 4200 bo‘ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 8 12 6 10 15 9 14 21 35	840

E. Sayyoh Savdogar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga N ta shahar va ularning orasidagi masofalar jadvali berilgan. Savdogar eng qisqa yo‘lni tanlab, barcha shaharlarni bir martadan bosib o‘tib, yana boshlang‘ich shaharga qaytishi kerak. Siz eng qisqa yo‘l uzunligini topishingiz kerak.

Kiruvchi ma'lumotlar:

Dastlab, bitta butun son N (2 ≤ N ≤ 10) – shaharlar soni beriladi.
Keyingi N qatorda N ta butun son bo‘lib, d[i][j] – i-shahardan j-shaharga bo‘lgan masofani bildiradi (0 ≤ d[i][j] ≤ 1000).

Shartlar:

d[i][i] = 0 (o‘zidan o‘ziga borish mumkin emas).
d[i][j] = d[j][i] (masofalar simmetrik).

Chiquvchi ma'lumotlar:

Eng qisqa sayohat uzunligi (barcha shaharlarni bir martadan bosib o‘tib, boshlang‘ich shaharga qaytish).

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0	80
2	3 0 20 30 20 0 10 30 10 0	60