A. Ichki tarmoq

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Shimoliy qutbda barcha axborot texnologiyalariga oid muammolar bilan “Elf technologies” korporatsiyasi shug'ullanadi. Sizni dasturchi sifatida ushbu korporatsiya tarkibiga kiruvchi va dasturlash muammolarini hal qiluvchi Elfsoft kompaniyasiga ishga joylashtirishdi.

Bu yili Elfsoft kompaniyasi uchun alohida yangi bino qurilgan, ammo hozircha foydalanish uchun to'liq tayyor emas. Qilinishi kerak bo'lgan oxirgi ish qolgan: bino bo'ylab xonalarga internet tarmog'ini o'tkazish. Elf telekom kompaniyasi ishchilari allaqachon kabel va routerlarni tayyor holatga keltirishgan. Sizning birinchi vazifangiz binoning ichki tarmog'i uchun niqob qo'yish (ing. subnet mask).

Ichki tarmoq uchun niqob nuqtalar bilan ajratilgan to'rt qismdan iborat bo'lib, har bir qism 0 dan 255 gacha sonlar bilan ifodalanadi. Niqobdagi bo'sh joylar soni tarmoqga ulanishi mumkin bo'lgan qurilmalar sonini belgilaydi. Masalan \(255.255.255.255\) ko'rinishidagi niqobda ulanish uchun 1 ta joy bor, \(255.255.255.200\) ko'rinishidagi niqobda 56 ta, \(255.255.0.0\) ko'rinishidagi niqobda esa 65536 ta. \(0.0.0.0\) manzili binodan chiquvchi tarmoq uchun, \(1.1.1.1\) manzili esa ichki tarmoqdagi barcha qurilmalarga bir vaqtda xabar jo'natish uchun zahiralangan. Shuning uchun bu 2 ta manzilni ishlatib bo'lmaydi.

Binoda tarmoqqa ulanuvchi N ta qurilma borligini bilgan holda ichki tarmoq uchun eng katta niqob qo'ying.

Kiruvchi ma'lumotlar:

N natural soni, \(N \leq 2^{32}-2\).

Chiquvchi ma'lumotlar:

Ichki tarmoq uchun eng katta niqob. Sonlar oldida ortiqcha nollarsiz chiqsin.

Izoh:

Haqiqiy tarmoqlarda ichki tarmoq niqoblari bu tarzda hisoblanmaydi, ichki tarmoqqa niqob qo'yish va undagi qurilmalar sonini aniqlash masalada ko'rsatilganidan murakkabroq.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1
 
255.255.255.255
2 
10
 
255.255.255.246
3 
3993055546
 
17.254.206.198

B. Elvaria 374

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Elfsoft kompaniyasi yangi binoga ko'chib o'tgach sizga ham alohida ish stoli ajratishdi. Endi albatta barcha dasturchilarga o'xshab yangi ish stolini suvinerlar va kerakli jihozlar bilan to'ldirishingiz kerak. Bunday narsalarni sotib olish uchun eng ma'qul joy albatta “Elf electronics” do'konidir.

Do'konga kirganda birinchi navbatda e'tiborni tortadigan narsa vitrinalarga ko'rgazma uchun qo'yilgan “Elvaria 374" va “Elvaria 374 Ultima” qurilmalaridir (*1). Siz “Elvaria 374 Ultima” sotib olishni xohladingiz, lekin bu model hali yangi bo'lgani uchun unga narx yorlig'i yopishtirilmagan. Ikkita elf sotuvchilar narx yozilgan yorliqni yopishtirmoqchi bo'lib turishibdi, lekin narx faqat 9 va 6 raqamlaridan iborat bo'lgani uchun qaysi tarafi bilan yopishtirishsa to'g'ri narx bo'lishini bilishmayapti. Chunki yorliq to'g'ri holida ham, 180 gradusga aylantirilsa ham to'g'ri yozilgan son hosil bo'ladi. Xavotir olmang do'kon egasi kelib ikkala qurilma uchun ham to'g'ri narxni topib beradi, siz shunchaki sotuvchi elflar qurilmaning narxini belgilashda eng ko'pi bilan qanchaga adashishlari mumkinligini toping.

*1. Elvaria - elflar bir necha yuz yillardan buyon masofaviy muloqot uchun foydalanib kelayotgan qurilma. Qurilma doimiy ravishda takomillashtirib kelingan va 2024-yilda taqdim etilgan eng oxirgi modeli Elvaria 374 va Elvaria 374 Ultima modellaridir. Elvaria - lotincha “elv” - elf va “aria” - qo'shiq yoki ohang. Ultima - lotinchadan oxirgi yoki mukammallik cho'qqisi. Qurilma Shimoliy qutbning barcha sirlarini o'zida saqlovchi “Qutb yog'dusi”dan quvvat oladi va bir martalik to'liq quvvatlanish bilan 1 yil davomida ishlay oladi.

Kiruvchi ma'lumotlar:

Faqat 9 va 6 raqamlaridan tashkil topgan, uzunligi 16 ta belgidan oshmagan butun son.

Chiquvchi ma'lumotlar:

Masala javobi - elflar adashishi mumkin bo'lgan eng katta qiymat.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
6
 
3
2 
669
 
30

C. Ichma-ich sikllar

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Ish stolingizni taxlab olganingizdan so'ng va nihoyat Elfsoft kompaniyasidagi birinchi ish kuningiz boshlandi. Ish har doimgidek o'zingiz qo'shilgan loyihaning oldindan yozilgan kodlarini ko'rb chiqish bilan boshlanadi. Kodlarni ko'rib chiqish davomida quyidagicha kod qismini ko'rish mumkin:

for (int a = 0; a < n; a++) {
	for (int b = a + 1; b < n; b++) {
		for (int c = b + 1; c < n; c++) {
			...
			(K ta shunday ichma-ich sikl)
		}
	}
}

Sizni eng ichkarida joylashgan sikl tanasi necha marta bajarilishi qiziqtirib qoldi. Albatta buni qo'lda hisoblab chiqish juda qiyin ish, shuning uchun buni hisoblash uchun dastur yozishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K natural sonlari, \(K \leq N \leq 10^6\).

Chiquvchi ma'lumotlar:

Eng ichkaridagi sikl tanasining bajarilishlar soni. Bu son juda katta bo'lib ketishi mumkin, shuning uchun uning 1000000007 ga bo'lgandagi qoldig'ini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
10 1
 
10
2 
10 2
 
45
3 
10 3
 
120
4 
11 4
 
330
5 
18 13
 
8568

D. Elf editor

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Boshqa dasturlash kompaniyalari singari Elfsoft kompaniyasi ham o'zining barcha mahsulotlariga sun'iy intellekt imkoniyatlarini qo'shib chiqmoqda. Kompaniya tomonidan ishlab chiqilgan, Shimoliy qutbda eng ko'p ishlatiladigan dastur albatta Elfsoft Office paketi hisoblanadi. Paketga kiruvchi dasturlar orasida yangilanish navbati Elfsoft Mail dasturiga keldi va sun'iy intellektchi elflar unga bolajonlar tomonidan Qorboboga jo'natilgan xabarlarga avtomatik javob yaratib beruvchi xususiyat qo'shishdi. Keyinchalik Elfsoftning testlovchi elflari shuni aniqlashdiki bu xususiyat qo'shilgandan keyin Elfsoft Mailning tahrirchisida matnni sahifa bo'ylab tekislash (justify) imkoniyati ishlamay qolgan. Siz Elfsoft Mail tahrirchisi uchun javobgar dasturchi sifatida bu xususiyatni qayta yozib bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda jo'natilayotgan xabar matni beriladi. Matn katta va kichik lotin alifbosi harflari, tinish belgilari va bo'shliqlardan iborat bo'ladi. Matnda kamida 1 ta so'z bo'lishi, so'zdan keyin tinish belgisi kelsa ularning orasida bo'shliq bo'lmasligi va matn uzunligi \(1000\) ta belgidan oshmasligi kafolatlanadi.

Ikkinchi qatorda Elfsoft Mail dasturidagi sahifaning har bir qatoridagi belgilar soni \(K\) beriladi, \(K \leq 1000\). \(K\) ning eng kichik qiymati matndagi eng uzun so'z uzunligidan kam bo'lmaydi.

Chiquvchi ma'lumotlar:

Matnning \(K\) kenglikdagi sahifaga tekislangan holatini chop eting, bunda quyidagi qoidalarga amal qiling:

  • Har bir qatorga iloji boricha ko'proq so'z joylashtiring.
  • So'zdan keyin tinish belgisi kelsa orasida bo'shliq bo'lmasin.
  • So'zlar orasida eng kamida bitta bo'shliq bo'lisin.
  • Qatorning boshi va oxirida bo'shliqlar bo'lmasin. Bitta qatorda faqat bitta so'z joylashish holati bundan mustasno, bu holatda bo'shliqlar qator oxirida bo'lishi shart.
  • Bitta qatordagi bo'shliqlar so'zlar orasida iloji boricha teng qilib taqsimlansin. Buning iloji bo'lmasa qator oxiridagi bo'shliqlar kattaroq bo'lsin. Masalan bitta qatorda 4 ta so'z va 10 ta bo'shliq mavjud bo'lsa 1 va 2, 2 va 3-so'zlar orasida 3 tadan bo'shliq, 3 va 4-so'zlar orasida 4 ta bo'shliq qilib ajratiladi.
  • Qator faqat bo'shliqdan iborat bo'lishi yoki bo'sh bo'lishi mumkin emas.

  • Oxirgi qatorni kenglik bo'yicha tekislash shart emas.

    E'TIBOR BERING. Oxirgi qatordan boshqa har bir qator uzunligi bo'shliqlar bilan birga aynan K ga teng bo'lishi shart!

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
Happy new year to everyone
9
 
Happy new
year   to
everyone
2 
Bu eng yaxshi masala
10
 
Bu     eng
yaxshi    
masala

E. Sovg'a konveyeri 2

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Sizning dasturlash mahoratingiz tufayli Elfsoft kompaniyasi yangi yilga tayyor. Endi Shimoliy qutbdagi boshqa ishlarga yordamlashishingiz mumkin. Yangi yilga 1 kun qolganda eng ko'p ish sovg'a qadoqlash zalida bo'ladi, shuning uchun bu bo'limga yordam berish uchun yetib keldingiz.

Zalga kirganda birinchi bo'lib tayyor qadoqlangan sovg'alar chiqib keluvchi 2 ta konveyerni ko'rish mumkin. Bu yerda bitta elf ishlaydi, uning vazifasi 2 ta konveyerdan kelayotgan sovg'alarni Qorboboning sovg'alar qopiga joylash. Konveyerlarning tepasida katta monitor ham bor, unda ikkala konveyerdan sovg'alar chiqib kelishining aniq vaqtlari ko'rsatiladi. Bu vaqt ish kunining boshlanish vaqtidan boshlab necha soniya vaqt o'tgandan keyin sovg'aning chiqishini bildiradi. 

Elf konveyerdan sovg'ani olish uchun uning to'g'risida turishi kerak. Ishning boshlanishida u qaysi konveyer to'g'risida turishni tanlab oladi va qaysi konveyerdan birinchi bo'lib sovg'a chiqib kelsa o'sha konveyerning oldiga o'tadi. U shunchalik mukammal ishlamoqchiki, bitta konveyerdan boshqasiga o'tishlar soni ham minimal bo'lishi kerak. Siz monitordagi sovg'alar chiqish vaqtini ko'rgan holda elf uchun minimal o'tishlar sonini topib bering.

Kiruvchi ma'lumotlar:

Monitorda 2 ta ustun mavjud bo'lib 1-ustun 1-konveyerdan sovg'alar chiqish vaqtlarini, 2-ustun 2-sidan chiqish vaqtlarini bildiradi. Vaqtlar har bir ustun uchun kamaymaslik tartibida bo'ladi va qiymati \(10^9\) dan oshmaydi. Umumiy sovg'alar soni \(2*10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar:

Elf uchun bitta konveyerdan boshqasiga o'tishlarning minimal sonini hisoblab bering.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
0 1
2 3
3 4
6 5
7 6
8 8
9 9
11 10
12 13
17 17
 
10

F. Sovg'a qadoqlash

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Sovg'a qadoqlash zalida bir elfning o'ylanib o'tirganiga ko'zingiz tushdi. Uning oldiga borganingizda u bir sovg'ani ixcham qilib qadoqlash haqida bosh qotirib turgan ekan. Sovg'a N*N o'lchamli rasmli boshqotirma. Uni ixchamlashtirish uchun K*K o'lchamli kichik kvadratchalarga ajratib undagi hamma bo'lakchalarni ustma-ust joylashtirish orqali amalga oshiriladi. Lekin bunda qadoqdagi har bir ustun faqat bir xil ranglardan tashkil topgan bo'lishi kerak, aks holda uni qayta o'z holatiga keltirishda bo'lakchalarning tartibi buzilib ketishi mumkin. Rasm K*K o'lchamli kvadratchalarga ajratilganda bo'lakchalar ortib qolmasligi ham kerak.

Siz bu elf uchun N*N o'lchamli rasmni minimal qanday o'lchamga keltirish mumkinligini hisoblab bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda N natural soni - rasmning o'lchami, \(N \leq 1000\).

Keyingi N ta qatorda N tadan son. i-qatordagi j-son rasmning aynan shu pikselining rangini bildiradi. Rasmda 16 xil rang bor va 1 dan 16 gacha bo'lgan sonlar bilan ifodalangan.

Chiquvchi ma'lumotlar:

Rasmni ixchamlashtirish mumkin bo'lgan eng kichik o'lchamini chiqaring.

Izoh:

1-testda 8*8 o'lchamli rasmni 4*4 o'lchamli bo'laklarga ajratib yig'ish mumkin, shunda ixchamlashgan holatda 2*2 o'lchamli rasm hosil bo'ladi.

2-testda 2*2 o'lchamli bo'lakchalarga ajratish mumkin, natijaviy rasm 4*4 bo'ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
8
1 1 1 1 14 14 14 14 
1 1 1 1 14 14 14 14 
1 1 1 1 14 14 14 14 
1 1 1 1 14 14 14 14 
8 8 8 8 16 16 16 16 
8 8 8 8 16 16 16 16 
8 8 8 8 16 16 16 16 
8 8 8 8 16 16 16 16
 
2
2 
8
3 3 12 12 13 13 8 8 
3 3 12 12 13 13 8 8 
1 1 13 13 13 13 3 3 
1 1 13 13 13 13 3 3 
14 14 1 1 2 2 6 6 
14 14 1 1 2 2 6 6 
15 15 3 3 4 4 6 6 
15 15 3 3 4 4 6 6
 
4

G. Qo'lqop

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Bu yili Qorbobo bolajonlarga o'zlari so'ragan sovg'alardan tashqari bir juftdan qo'lqoplar ham qo'shib bermoqchi. Shuning uchun tikuvchi elflarga juda ko'p miqdorda qo'lqoplar ham tikdirib tayyorlab qo'ygan. Siz endi qo'lqoplarni juft-juft qilib taxlashga yordam berishingiz kerak. Tikish xonasida N ta qo'lqoplar ketma-ket qo'yilgan. Ular o'lchami va rangiga qarab farqlanadi. Albatta bir juft qo'lqoplarning o'lchami ham rangi ham bir xil bo'lishi kerak.

Qo'lqoplarning juftini topish oson bo'lishi uchun ular 1 dan 100 gacha bo'lgan sonlar bilan raqamlab chiqilgan. Bir xil raqamli qo'lqoplar bir xil raqamga ega. Siz ketma-ket turgan N ta qo'lqopdan eng katta oraliqni tanlab olingki oraliqda bitta ham qo'lqop juftsiz qolmasin.

Kiruvchi ma'lumotlar:

Birinchi qatorda N natural soni - tikuv xonasidagi qo'lqoplar soni, \(N \leq 10^5\).

Ikkinchi qatorda N ta [1,100] oralig'idagi sonlar, i-son i-qo'lqopning raqamini bildiradi.

Chiquvchi ma'lumotlar:

Tanlangan eng katta oraliqning o'lchamini chiqaring.

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

H. Tozalovchi robotlar

Xotira: 256 MB, Vaqt: 2000 ms
Masala

Va nihoyat uzoq ish kunidan so'ng sovg'a qadoqlash zalidagi ishlar yakunlandi. Barcha sovg'alar qadoqlanib, qoplarga solinib, Qorboboning chanasiga joylanib tayyor holatga keltirildi. Sovg'a qadoqlash zali esa yaroqsiz sovg'a qutilari va lentalar sochilganicha tartibsiz holatda qoldi. Uni tozalash sizning vazifangiz, xavotir olmang uni qo'lda tozalab chiqmaysiz 😄.

Sovg'a qadoqlash zali N*M o'lchamda, zalga K ta tozalovchi robotni joylashtirib chiqgansiz. Har bir robotning turgan joyi aniq va ular zalning o'zi turgan koordinatasini tozalaydi. Hamma robotlar uchun sizda bitta boshqaruv pulti bor, robotlar pultdan kelgan buyruqni sinxron ravishda bir vaqtda bajaradi. Pult 4 ta tugmadan iborat, tugmalar yordamida robotlarna orqaga, oldinga, o'ngga va chapga harakatlantirish mumkin. Agar robot zal devoriga urilib ketsa ishdan chiqishi mumkin, robotlar juda qimmat bo'lgani uchun birorta ham robot ishdan chiqmasligi kerak.

Robotlarni birinchi taxlab qo'ygan holatingizda eng ko'pi bilan zalning qancha qismini tozalash mumkin? Robotlarni faqat pult bilan boshqarish mumkin, ularni alohida qayta joylashtirish mumkin emas.

Kiruvchi ma'lumotlar:

Birinchi qatorda N, M va K sonlari, N va M zalning o'lchami, K esa robotlar soni. \(K \leq N*M \leq 10^6\)

Keyingi K ta qatorda 2 tadan son, i-qatordagi sonlar i-robotning joylashgan koordinatasini bildiradi.

Chiquvchi ma'lumotlar:

Zalning tozalash mumkin bo'lgan maksimal yuzasi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 5 2
1 1
3 3
 
17
2 
5 5 3
1 1
1 5
5 1
 
3

I. Konchilar shahri

Xotira: 128 MB, Vaqt: 4000 ms
Masala

Va nihoyat yangi yil kechasi ham yetib keldi. Shu vaqtgacha o'z ishlaringizni professional bajarib Qorboboning ishonchiga kira olganingiz uchun u sizni ham sovg'a tarqatish uchun elflar bilan birga olib ketishga qaror qildi.

Sizga sovg'a tarqatishdagi birinchi vazifa sifatida kichkina konchilar shahridagi bolalarga sovg'alarini yetkazish berildi. Shaharchada N ta uy mavjud, ular bir-biri bilan yo'llar orqali bog'langan. Yangi yil kechasi bo'lgani sababli barcha uylar bo'm-bosh, sababi shaharchada bu yerga yaqin joyda joylashgan kon ishchilari vaqtinchalik, faqat ish vaqtlarida yashashadi. Hozir esa dam olish vaqti bo'lgani uchun ular bu yerda emas.

Faqatgina shaharchaning boshi va oxirida joylashgan 1 va N-uylarda shaharchaning qorovullari oilasi bilan doimiy yashashadi. Sizning vazifangiz shu ikki oila bolalariga sovg'alarini yetkazish va bu ishni iloji boricha tez bajarish.

Sizning elvariangizda butun dunyoning to'liq xaritasi mavjud, lekin bu shaharcha kichkina bo'lgani uchun xarita dasturini yasagan dasturchi elflar tomonidan e'tiborsiz qoldirilgan ekan. Elvariada bu shaharcha xaritasining K xil versiyasi mavjud. Har bir xarita to'g'ri yo'llarni ko'rsatadi, lekin to'liq emas. Elvariadagi xarita ilovasida xaritaning K xil versiyasidan faqat bittasini saqlash mumkin, boshqa versiyasini yuklab olish uchun 1 daqiqa vaqt kerak bo'ladi, sababi shaharchada internet tarmog'i sekin. Xaritaning yangi versiyasi yuklab olingandan so'ng eski versiyasi o'chib ketadi.

Dastlab elvariangizda shaharcha xaritalarining birortasi yuklab olinmagan va shaharchadagi 1-uyda turgan bo'lsangiz N-uyga yetib borish uchun minimal qancha vaqtni xarita yuklab olish uchun sarflashingiz kerak bo'ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(K\) sonlari, shaharchadagi uylar soni va xaritalar soni. \(1 \leq N,K \leq 2000\).

Keyingi qatorlarda \(K\) ta xarita ma'lumotlari quyidagi formatda beriladi: i-xarita ma'lumotining 1-qatorida \(C_i\) soni - i-xaritadagi yo'llar soni beriladi. Keyingi \(C_i\) ta qatorning har birida ikkitadan natural son a va b \((1 \leq a,b \leq N, a \neq b)\) sonlari beriladi, bu sonlar i-xaritadagi a va b uylar orasida yo'l borligini bildiradi. Barcha \(K\) ta xaritadagi yo'llar soni \(2*10^5\) tadan oshmaydi.

Chiquvchi ma'lumotlar:

Xarita yuklab olish uchun sarflanadigan minimal vaqtni chop eting. Agar N-uyga yetib borishning iloji bo'lmasa -1 chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
10 3
2
6 8
8 7
2
1 3
1 6
6
7 10
1 2
3 7
1 4
2 9
4 5
 
2
2 
10 3
11
2 4
6 2
3 5
10 9
2 8
7 9
4 10
4 8
4 7
3 7
5 6
1
1 2
3
1 9
2 3
6 8
 
2

J. Shimoliy qutb siri

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Tabriklayman, barcha sovg'alar muvaffaqiyatli yetkazildi!!!

Xo'sh shuncha sarguzashtlar davomida Shimoliy qutb sirini topdingizmi?

Kiruvchi ma'lumotlar:

Kiruvchi ma'lumotlar mavjud emas.

Chiquvchi ma'lumotlar:

Shimoliy qutb sirini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
Kitob yaratilingan sana: 08-Jan-25 08:14