A. Qodirali va Sonlar Sarguzashti

Xotira: 32 MB, Vaqt: 1000 ms

Qodirali o‘zini haqiqiy raqamlar sehrgari deb biladi va har safar yangi sonli o‘yinlarni kashf etishni yoqtiradi. Bugun esa u qo‘lida uzunligi \(n\) bo‘lgan 0-indeksli \(arr\) massiv bilan o‘ynayapti.

Siz \([0, n-1]\) oraliqdan \(k\) ta son ( \(k \ge 2\) ) tanlaysiz. Qoidaga ko‘ra, tanlagan sonlaringiz orasida \(0\) va \(n-1\) albatta bo‘lishi kerak.

Qodirali tanlagan indeklaringizdan yangi \(ind\) massiv tuzadi. Endi, bu massiv yordamida u o‘zining maxsus «qiziqarli qiymat»ini quyidagicha hisoblaydi:

\[s = \sum_{i=1}^{k} (-1)^{i+1} \cdot (ind_i - ind_{i-1}) \cdot arr[ind_i]\]

Sizning vazifangiz – shunday indekslar to‘plamini tanlash kerakki, hosil bo‘ladigan \(s\) maksimal qiymatga ega bo‘lsin. Eng kattasini toping va ekranga chiqaring!

5
17 14 15 15 8

37

10
12 16 10 14 18 11 14 1 6 4

91

B. Ko'prikdan o'tish

Xotira: 128 MB, Vaqt: 1000 ms

Osma ko‘prik chuqur darani kesib o‘tadi. Odamlar ko‘prikdan guruh bo‘lib o‘tishlari mumkin, ammo ko'prik juda ham eski bo'lganligi uchun, hammani bir vaqtda ko'tara olmaydi, boshqa so'zlar bilan aytganda bir vaqtda ko'prikdan faqatgina 1 ta guruh o'tishi mumkin va guruhdagi odamlar soni M tadan oshmasligi kerak. Guruhning ko‘prikdan o‘tish vaqti shu guruhdagi eng sekin odamning tezligiga bog‘liq. Siz ko‘prik xavfsizligi uchun mas’ulsiz va guruhlarning o‘tishini nazorat qilasiz.

Odamlar navbatda turishgan; oldingi guruh o‘tib bo‘lgach, siz navbatdagi bir necha kishiga “endi o‘tishingiz mumkin” deb ruxsat berasiz. Guruhlar turli hajmda bo‘lishi mumkin, lekin hech bir guruhda M tadan ortiq odam bo‘lmasligi shart. Maqsad — odamlarning tartibini buzmasdan, hammani eng qisqa umumiy vaqt ichida ko'prikdan o‘tkazishdir.

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

9
11
6

C. Ajoyib juftliklar 3

Xotira: 32 MB, Vaqt: 1000 ms

Javohirning ustozi Mehriddin unga matematik masala berdi. Ammo u juda erinchoqligi uchun dastur tuzishga qaror qildi. Masala sharti quyidagicha: n va s natural sonlari beriladi, sizning vazifangiz n xonali yig’indisi s ga teng bo’lgan eng kichik va eng katta ikkita qiymatni topish. Agar bunday qiymatlar mavjud bo’lmasa, "-1 -1" (qo'shtirnoqsiz) ni chop eting

2 1

10 10

3 10

109 910

D. Psevdokod

Xotira: 256 MB, Vaqt: 3000 ms

Nyuboy CP(Competitive Programming)ga qiziqadi. U hozir bitta masalani ishlayotgan edi. Nyuboy ushbu masalani 2-urinishda hal qildi. Sizga Nyuboyning 1-yechimi beriladi. Siz ushbu masalani ishlay olasizmi?

!!! Nyuboyning 1-yechimidagi yagona muammo Time Limit edi.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n, q; cin >> n >> q;
	vector <int> a(n + 1);
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	while (q --){
		int l, r, k;
		cin >> l >> r >> k;
		vector <int> b;
		for (int i = l; i <= r; ++ i) b.push_back(a[i]);
		sort(b.begin(), b.end());
		cout << b[k - 1] << '\n';
	}
	return 0;
}

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

3
2
3
5

E. Maxsus topshiriq

Xotira: 256 MB, Vaqt: 1000 ms

Mashhur tadbirkor Aziz Asqarov, N ta korxonaga egalik qiladi. Uning yaqin do‘sti, taniqli moliyachi Bekzod Rustamov esa “TUIT Bank” xolding kompaniyasiga ega bo‘lib, unda ham N ta bank mavjud.
Ularning uzoq yillik hamkorligi tufayli — Azizning korxonalari faqat Bekzodning banklaridan kredit oladi, va Bekzodning banklari faqat Azizning korxonalariga kredit beradi. Kredit summalari soliqlardan qochish maqsadida sir tutilgan.

Ammo bir kuni ularning eski raqibi, Moliyaviy nazorat qo‘mitasi boshlig‘i Jamshid Karimov, o‘tmishdagi raqobatdan o‘ch olishga qaror qiladi. Jamshidning maqsadi — Aziz va Bekzod o‘rtasidagi barcha kredit operatsiyalarini fosh etish.

Avvalo, Jamshidning inspektorlari Azizning korxonalaridan ayrim hujjatlarni qo‘lga kiritishdi.
Har bir korxona uchun jami olingan kredit miqdori aniqlanib, bu SR[i] deb belgilandi.
Keyin esa Bekzodning banklarida o‘tkazilgan reydlarda har bir bank tomonidan berilgan jami kredit miqdori topildi — bu SC[j] qiymatlari sifatida yozildi.

Endi Jamshidning maqsadi — ushbu ma’lumotlar asosida kredit matritsasini tiklash.

Bu matritsa N×N o‘lchamdagi jadval bo‘lib, har bir elementi
A[i, j] = i-korxona Bekzodning j-bankidan olgan kredit miqdori
ko‘rinishida bo‘ladi.

Ma’lumki, har bir kredit miqdori 0 dan 100 gacha bo‘lgan butun son.
Ammo Jamshid olgan ma’lumotlar soxtalashtirilgan bo‘lishi mumkin, shuning uchun bunday matritsani tuzish imkonsiz holatlar ham bo‘ladi.

3
15 10 3
11 5 12

YES
10 0 5
0 3 7
1 2 0

2
201 0
100 101

NO

F. Sehrli sonlar

Xotira: 32 MB, Vaqt: 1000 ms

Bilmasvoy raqamlarni juda yaxshi ko‘radi. Har kuni u turli sonlar bilan o‘ynab, “sehrli sonlar” deb nomlagan sonlarni izlaydi.

Uning fikricha, sonning sehrli bo‘lishi uchun uning raqamlari yig‘indisi ma’lum bir \(S\) soniga teng bo‘lishi kerak.

Endi Bilmasvoy bir oraliqni tanladi: \([A, B]\). U shunday savolga javob izlamoqda: Shu \([A, B]\) oraliqda nechta sehrli son mavjud? Va ular orasida eng kichigi qaysi?

Bilmasvoy juda charchagan, shuning uchun u bu ishni kompyuterga topshirishni xohlaydi. Uning o‘rniga shunday dastur yozingki, u sehrli sonlar sonini va eng kichik sehrli sonni topib bersin.

1 9 5

1
5

1 100 10

9
19

G. Parvoz vaqti

Xotira: 32 MB, Vaqt: 1000 ms

ICPC ishtirokchilari tayyorgarlik uchun chet elga yo‘l olishdi. Ular har daqiqadan unumli foydalanishni xohlagani uchun samolyotda uchish davomida masalalar yechmoqchi. Ularda masalalar ustida ishlash uchun eng kamida qancha vaqt borligini aniqlang.

12:00
13:00
0

01:00

23:00
01:00
0

02:00

01:50
12:50
+1

10:00

H. Zarif sayohati

Xotira: 32 MB, Vaqt: 1000 ms

Sayohatchi Zarif dekart koordinatalar sistemasining \((x_1, y_1)\) nuqtasidan undan farqli bo'lgan \((x_2, y_2)\)  nuqtasiga yetib bormoqchi. Lekin u sakrashni birdan qila olmaydi, oldin  \((x_1, y_1)\) dan turib undan farqli bo'lgan \((x_3, y_3)\) nuqtaga yurib, keyin \((x_3, y_3)\) nuqtadan undan farqli \((x_2, y_2)\) nuqtaga o'tmoqchi. Yagona sharti, o'tish davomida shunaqangi  \((x_3, y_3)\)  koordinatalarni tanlamoqchiki, butun sayohati davomida \((x_1, y_1), (x_2, y_2), (x_3, y_3)\) nuqtalaridan tashqari boshqa umuman butun koordinatali nuqtalar ustidan bosib o'tmasligi kerak.

3
0 0 100 0
0 0 12 8
-1000000000 1000000000 1000000000 -1000000000

101 -1
11 -1
1000000001 999999999