A. Super Mario va Qo'ziqorinlar

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Super Mario oldida 10 ta qo'ziqorin bor. Ular ketma-ket joylashgan va har biri ma'lum miqdorda ball beradi.

Mario qo'ziqorinlarni faqat chapdan o‘ngga qarab terishi mumkin hamda u barchasini olishga majbur emas. Uning asosiy maqsadi – yig‘ilgan ballar sonini 100 ga iloji boricha yaqinlashtirish.

Agar ikki xil natija 100 ga bir xil masofada joylashgan bo‘lsa (masalan, 95 va 105), Mario katta ballni tanlaydi (bu holatda 105).

Mario qancha ball to‘plashini aniqlang!

Kiruvchi ma'lumotlar:

Kirish 10 ta qatordan iborat bo‘lib, har bir qator 1 dan 100 gacha bo‘lgan musbat butun sonni o‘z ichiga oladi. Bu sonlar Mario qo'ziqorinlarni olganida beriladigan ballarni bildiradi.

Chiquvchi ma'lumotlar:

Yagona butun son – Mario tomonidan to‘plangan ballar sonini chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	16 34 18 17 15 41 27 76 39 88	100
2	30 30 30 30 30 30 30 30 30 30	90
3	1 2 3 5 8 13 21 34 55 89	87

B. Hashar

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Bugun maktab tashqarisini tozalash kuni. Ismoil maktab yaqinidagi yo‘lda tushib ketgan axlatlarni yig‘ishi kerak. U kamida $N$ ta axlat yig‘ishi shart.

Ismoil hozir 0-holatda turibdi. $M$ ta axlatning joylashuv koordinatalari berilgan. Ismoil $N$ ta axlatni yig‘ish uchun minimal masofani bosib o‘tishi kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N$ va $M$ sonlar beriladi. $(1 ≤ N ≤ M ≤ 2*10^6)$

Keyingi M ta qatorda M ta axlat koordinatalari beriladi. $(-3*10^6 ≤ A_i ≤ 3*10^6)$ ( $A_i ≠ A_j$ axlatlarning joylashuv joylari takrorlanmaydi)

Chiquvchi ma'lumotlar:

Ismoil $N$ ta axlatni yig‘ish uchun bosib o‘tishi kerak bo‘lgan minimal masofani chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 6 -14 -12 -11 -6 10 13	34
2	3 8 -18 -15 -2 3 4 5 14 18	5

C. Serverlarni nusxalash

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Tashkilotda $N$ ta server mavjud bo‘lib, ularning har biri uchun zaxira nusxa olish muddati $B[i]$ daqiqa vaqt talab etadi. Serverlar $1$ dan $N$ gacha tartiblanadi va zaxira nusxa olish ishlarini faqat ketma‑ket bajarish mumkin (serverlar tartibida bo‘lishi shart). Zaxira nusxa olish jarayonida, agar bir kunda bir nechta server zaxiralansa, ular orasida majburiy $D$ daqiqa bo‘sh vaqt ajratiladi. Serverning zaxira nusxasi bir kun ichida butunlay amalga oshirilishi lozim. Ya'ni har bir serverning zaxira nusxasini olish jarayoni toʻliq bir kun davomida bajarilishi kerak. Ya’ni, agar serverning zaxira nusxasi olish jarayoni $3$ daqiqa davom etsa, ushbu $3$ daqiqa bir kunda bajarilishi shart. Agar qolgan vaqt $3$ daqiqadan kam boʻlsa, ushbu serverning nusxasi olish jarayoni yarim kun ichida bo'lib qolmaydi, balki toʻliq keyingi kunga oʻtkaziladi.

Tashkilot ish jarayonidagi qo‘shimcha yukni kamaytirish maqsadida, zaxira nusxa olish jarayonidagi eng ko‘p sarflanadigan (kunlik) vaqtni minimal darajaga tushirishni xohlaydi. Sizga maksimal $T$ kun ichida barcha serverlarning zaxira nusxasini olish uchun zarur bo‘lgan minimal kunlik vaqt chegarasi $X$ ni aniqlash topshirig‘i beriladi. Agar hatto eng kattaroq imkoniyat (ya’ni, server zaxira vaqtlarining yig‘indisi va bo'sh vaqtlar qo‘shilganda) ham $T$ kundan oshsa, $–1$ ni chiqarishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N, T$ va $D$ butun sonlari $(1 ≤ N ≤ 10^5, 1 ≤ T ≤ 10^5, 0 ≤ D ≤ 1440).$

Ikkinchi qatorda $N$ ta butun son, $B[i](1≤B[i]≤1440).$

Chiquvchi ma'lumotlar:

Barcha serverlarning zaxira nusxasini olish uchun talab qilinadigan minimal kunlik vaqt chegarasi $X$ , yoki $–1$ (agar $T$ kundan ichida rejalashtirish mumkin bo‘lmasa).

Izoh:

Serverlar tartibida natijada quyidagicha bo'ladi:

1‑va 2‑serverlar birinchi kunda: 3 + 2 + 1 = 6 daqiqa
3‑va 4‑serverlar ikkinchi kunda: 4 + 2 + 1 = 7 daqiqa
5‑server uchinchi kunda: 5 daqiqa
Maksimal kunlik yuk 7 daqiqa bo‘ladi, demak $X = 7.$

1 kun 1440 daqiqadan iborat

Misollar:

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

D. Nodirning ajoyib sonlari

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Nodir — matematikaga qiziqadigan o‘quvchi. U sonlar bilan bog‘liq qiziqarli qonuniyatlarni topishni yaxshi ko‘radi. Bir kuni u raqamlar tartibini kuzatib, g‘alati bir holatni payqadi : ayrim sonlar toq va juft raqamlarning aniq ketma-ketligiga ega edi.

Masalan, 10, 12, 14, 16, 18, 21, 23, ... kabi sonlarning raqamlari toq-juft yoki juft-toq ketma-ketligida joylashgan edi. Nodir bu kabi sonlarni "ajoyib sonlar" deb atadi. U ilk ajoyib son 10 ekanligini aniqladi va shu qonuniyat bo‘yicha davom etadigan barcha sonlarni yozib chiqdi.

Endi esa u bir muammo ustida bosh qotirmoqda: N-chi ajoyib sonni qanday tez topish mumkin? Bu masalada unga yordam bera olasizmi?

Kiruvchi ma'lumotlar:

Birinchi qatorda $T(1\le T \le 10^5)$ testlar soni beriladi.

Keyingi $T$ qatorda har birida $N (1 ≤ N ≤ 10^{18})$ soni beriladi — qaysi tartibdagi ajoyib son topilishi kerakligi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda $N$ -ajoyib sonni chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 5 8	10 18 25

E. Tarmoq monitoringi

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Bugun kiberxavfsizlik markazi tarmoq xavfsizligini tekshirish bilan band. Har bir server faqat bitta keyingi serverga (yoki hech qaysisiga) ma’lumot jo‘natadi. Tarmoqda sirli xakerlar bor bo‘lib, ular serverlar o‘rtasidagi ma’lumot almashinuvini buzishi mumkin.

Tizim xavfsizligini tekshirish uchun tarmoq administratoriga ikkita asosiy buyruq taqdim etiladi:

Tahlil qilish — 1 X - Server X ga yuborilgan ma’lumot qaysi yakuniy serverga yetib boradi?
Bloklash — 2 X - Server X ning keyingi serverga jo‘natilayotgan aloqasi o‘chiriladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda $N (1 ≤ N ≤ 3 \times 10^5)$ — serverlar soni kiritiladi.

Ikkinchi qatorda N ta son beriladi, i-chi son server i dan qaysi serverga ma’lumot uzatilishini bildiradi. Agar qiymat 0 bo‘lsa, bu server ma’lumot uzatmaydi.

Keyingi qatorda $Q (1 ≤ Q ≤ 3 \times 10^5)$ — so‘rovlar soni kiritiladi.

Keyingi Q ta qatorda quyidagi ikkita turdagi so‘rovlar beriladi:

1 X — Server X ga yuborilgan ma’lumot qayerga yetib borishini aniqlang.
2 X — Server X ning keyingi serverga bo‘lgan aloqasini uzing.

Chiquvchi ma'lumotlar:

Har bir 1 X so‘rovi uchun bitta son chiqaring — yakuniy server raqami yoki -1, agar ma’lumot cheksiz aylansa.

Misollar:

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

F. Akbar va Uning Super Tuzilmasi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Akbar har xil ma’lumot tuzilmalarini ishlab chiqishdan charchadi va bitta mukammal tuzilma yaratishga qaror qildi. Ushbu tuzilma unga sonlar ketma-ketligi ustida turli amallarni bajarish imkonini beradi.

Sizga boshlang‘ich sonlar ketma-ketligi va so‘rovlar ketma-ketligi beriladi. Har bir so‘rov quyidagi turlardan biri bo‘lishi mumkin:

So‘rovlar turlari:

1 A B X — [A, B] oraliqdagi barcha elementlarni X ga tenglashtirish
2 A B X — A elementiga X qo‘shish, (A+1) elementiga 2X qo‘shish, ..., B elementiga (B-A+1)X qo‘shish
3 C X — C-indeks oldiga yangi X qiymatli element qo‘shish
4 A B — [A, B] oraliqdagi elementlar yig‘indisini chiqarish

Kiruvchi ma'lumotlar:

Birinchi qatorda N $(1 ≤ N ≤ 10^5)$ — boshlang‘ich ketma-ketlik uzunligi va Q $(1 ≤ Q ≤ 10^5)$ — so‘rovlar soni kiritiladi

Ikkinchi qatorda N ta musbat butun son, har biri $0 ≤ a_i ≤ 10^5$

Keyingi Q ta qatorda yuqorida ko‘rsatilgan so‘rovlar kiritiladi.

Barcha testlar uchun $1 \le X \le 100$

Chiquvchi ma'lumotlar:

Har bir 4 A B so‘rovi uchun bitta son chiqaring — [A, B] oraliqdagi elementlar yig‘indisi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	9 4 9 8 7 6 5 4 3 2 1 1 3 5 0 2 3 5 2 3 4 100 4 6 7	10