A. Sehrli matritsa

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Jamshid \(3\times 3\) sehrli matritsalarni yaxshi ko'radi. Uning o'ylashicha matritsaning istalgan satrining, ustunning va ikki diogonalning elementlarning yig'indisi bir biriga teng bo'lsa ushbu matritsa sehirli matritsa hisoblanadi.

Jamshid sehrli matritsani hosil qilishda asosiy diogonallaridagi elementlarni yozishda xatolikka yo'l qo'ydi. Sizning vazifangiz ushbu matritsani faqatgina asosiy dioganalini o'zgartirgan holda sehrli matritsaga keltirishdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylida \(3\times 3\) o'lchamli matritsa kiritiladi. Har bir satrda uchtadan manfiy bo'lmagan \(9\) dan oshmaydigan butun sonlar beriladi.

Chiquvchi ma'lumotlar:

Jamshid hosil qilishi kerak bo'lgan matritsani chop eting. Hosil qilinishi kerak bo'lgan matritsaning elementlarini manfiy bo'lmagan sonlarni tanlang. Agar sehrli matritsaga keltirishning imkoni bo'lmasa -1 ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	0 1 1 1 0 1 1 1 0	1 1 1 1 1 1 1 1 1

B. ICPC 22-23

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dasturlash bo‘yicha dunyoning eng nufuzli musobaqasi ICPC turnirining ilk saralash O‘zbekiston va Tojikiston bosqichi start olishiga oz muddat qolmoqda, shu sababli Sharof Rashidov nomidagi Samarqand davlat universiteti 6 ta talabasi bu musobaqada qatnashish uchun tayorgarlik korishmoqda. Ustozlar bu 6 ta talabani ikki jamoaga ajratish borasida qiyinchilika duch kelishdi.
Agar \(i-\)talabaning bilim darajasi \(a_i\) ga teng bo'lsa bu talabalarni ikkita bilim darajasi teng jamoalarga ajratish mumkunmi tekshiring.

Kiruvchi ma'lumotlar:

Bir qatorda 6 ta \(a_1,..., a_6 ( 0 \leq a_i \leq 1000 )\) - talabalarni bilim darajalari beriladi.

Chiquvchi ma'lumotlar:

Agar bilim darajasi teng bo'lgan ikki jamoa tashkil qilish mumkin bo'lsa \('Yes'\) aks holda \('No'\) so'zini chop eting.
Siz chop etayotgan so'z harflari yuqori yoki quyi registirda bo'lishidan qati nazar ma'no jihatdan \('yes'\) yoki \('no'\) ga teng bo'lishi kerak.

Izoh:

ICPC terma jamoasi uchun har bir jamoada 3 tadan talaba ishtirok etishi kerak.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 3 2 1 2 1	yEs
2	1 1 1 1 1 99	No

C. Tenglama #2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga \(x^2+f(x)*x=n\) ko'rinishidagi tenglama beriladi. Agar sizga \(n\) soni berilsa tenglamaning eng kichik butun yechimini aniqlashingiz kerak bo'ladi.

Bu yerda \(x, n -\) musbat butun sonlar, \(f(x)-\)funksiya \(x\) ning raqamlari yig'indisini hisoblab beradi.

Kiruvchi ma'lumotlar:

Yagona satrda \(n(1\leq n\leq 10^{18})\) - natural son beriladi.

Chiquvchi ma'lumotlar:

Yagona qatorda masalaning javobini chop eting. Yechim mavjud bo'lmasa -1 ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2	1
2	110	10

D. Massivni almashtirish

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga 1 dan n gacha bo'lgan sonlarning premutatsiyalaridan biri beriladi. Ya'ni \(a_n(a_1,a_2,a_3,...,a_n)\) massiv berilgan, shu massivni elementlari tartibi shunday o'zgartiring hosil bo'lgan \(b_n(b_1,b_2,b_3,...,b_n)\) massiv kiritilgan massiv bilan quyidagi shartlarni qanoatlantirsin.

\(a_1 \not= b_1, a_2 \not= b_2, ... ,a_n \not= b_n\)

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t(1 \leq t \leq 200)\) testlar soni va har bir testni birinchi qatorida \(n(1 \leq n \leq 1000)\) massiv uzunligi va ikkinchi qatorida \(a_1,a_2,a_3,...,a_n(1 \leq a_i \leq n)\) sonlar toplami kiritiladi.

Chiquvchi ma'lumotlar:

Hosil qilinadigan premutatsiyalar bir nechtasi shartni qanoatlantirishi mumkun, shuning uchun leksikografik jihatdan eng kichik premutasiyani chop eting. Agar bunday premutasiya mavjud bo'lmasa -1 ni chop eting.

Misollar:

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

E. Start up nomlash

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Shohrux va Jasur juda qalin do‘stlar. Lekin baʼzida ular oddiy narsalar ustida ham tortishib turishadi. Yaqinda ular start up loyiha boshlashdi va unga nom berish ustida tortishib qolishdi. Bu muommoni hal qilish maqsadida bir qiziqarli o'yin o'ylab topishdi.

Ikki do'st har ikkalasi ixtiyoriy \(n\) ta belgidan tashkil topgan to'plamni tanlaydi(belgilar takrorlangan bo'lishi mumkun). Dastlab loyihaning nomi \(n\) ta \(?\) belgisidan iborat va ular nabat bilan o'zidagi to'plamdan bir belgini olib istalgan \(?\) begini o'rniga joylashtiradi.

O'yinni Shohrux boshlaydi va u loyihaning nomi imkon qadar liksografik jihatdan kichik bo'lishini, Jasur esa liksografik jihatdan katta bo'lishi istaydi. Agar ikkisi ham optemal o'ynasa loyiha nomi nima bo'lishini aniqlang.

Kiruvchi ma'lumotlar:

Alohida qatorlarda \(s_1,s_2(1\leq |s_1|,|s_2|\leq3*10^5; |s_1|=|s_2|)\) lotin alifbosining kichik harflaridan tashkil topgan satrlar beriladi.

Chiquvchi ma'lumotlar:

Shohrux va Jasur hosil qilgan loyiha nomini chop eting.

Izoh:

1-test: Shohrux {\(i, o, i\)} to'plamni, Jasur {\(i, m, o\)} to'plamni tanlaydi. Loyiha nomi dastlab \(???\) ga teng. Shohrux birinchi \(?\) belgisini o'rniga o'zidagi to'plamdan \(i\) ni joylashtiradi hozirda loyiha nomi \(i??\), Jasur esa ikkinchi \(?\) belgisini o'rniga \(o\) harfini joylashtiradi \(io?\) va Shohrux uchunchi \(?\) belgisini o'rniga \(i\) belgisini joylashtiradi hosil bo'lgan loyiha nomi \(ioi\).

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	ioi imo	ioi
2	olex iows	ewls

F. Sayohat qilmoq

Xotira: 512 MB, Vaqt: 1000 ms

Masala

Qulmamat Liplandiya shahriga sayohatga bordi. Bu shaxarda \(1\) dan \(n\) gacha raqamlangan shaxarlar mavjud bo'lib, ikkita shaxarni bog'lovchi yo'l bir tomonlama edi. Qulmamatning \(T\) soat vaqti mavjud bo'lib, u \(T\) soat ichida imkon qadar ko'proq shaxarlarga sayohatni amalga oshirishni istaydi.

Qulmamat \(1\) shaxardan sayohatni boshlab \(n\) shaxarda yakunlamoqchi. Agar ikki shaxarni bog'lab turuvchi yo'l \((u_i, v_i)\) mavjud bo'lsa bu yo'lni u \(t_i\) soatda bosib o'tadi.

Sizning vazifangiz Qulmamat imkon qadar ko'proq shaxarlarga sayohat qilishi uchun \(T\) soatdan oshmagan vaqtda ketma-ket qaysi shaxarlarga borish kerak ekanligini ko'rsatuvchi dastur tuzib berishdan iborat.

Kiruvchi ma'lumotlar:

Dastlabki satrda \(n,m,T(2\leq n\leq 10000, 1\leq m\leq 10000, 1\leq T\leq 10^6)\) sonlar, mos ravishda shaxarlar soni, yo'llar soni va sayohat uchun Qulmamatda mavjud bo'lgan vaqt.

Kiyingi \(m\) ta satrda \(u_i, v_i, t_i(1\leq u_i, v_i\leq n, 1\leq t_i\leq 10^9)\) uchliklar, bu yerda \((u, v)\) juflik o'rtasida yo'l mavjud va bu yo'lni bosib o'tish uchun \(t\) vaqt ketadi.

Chiquvchi ma'lumotlar:

Chiqish faylining dastlabki satrida Qulmamat jami nechta shaxarlarga sayohat qilishini va kiyingi satrda sayohatni qaysi shaxarlarda amalga oshirishi kerak ekanligini ketma-ket probil bilan ajratilgan holda chop eting. Agar bunday yechimlar bir nechta bo'lsa istalganini chop etishingiz mumkun.

Izoh:

Eslatma: Liplandiya mamlakatida siklik yo'l mavjud emas!

Misollar:

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

G. Qal'a himoyasi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Berlandiya mamlakatida bir qal'a mavjud. Bu qal'aga dushman hujum qilmoqchi. Siz qal'ani yovuz dushmanlarning hujumidan himoya qilish uchun kamonchi elflarni boshqarishingiz kerak. Qal'a uch tomondan o'tib bo'lmas to'siqlar bilan himoyalangan va qolgan to'rtinchi kirish tomonida esa \(n\) ta bo'limdan iborat devor bor. Ayni paytda \(i\)-bo'limda \(a_i\) ta kamonchi elflar joylashgan. Malumki \(i-\)bo'limda joylashgan har bir kamonchi \(r\) dan ortiq bo'lmagan masofalardagi bo'limga hujim qilayotgan dushmanga qarshi o'q uzaoladi, ya'ni \(j(|i-j|\leq r)\) raqamli bo'limlarga o'q uzaoladi.

\(i-\)bo'limning xafsizligi - bu qisimga hujum qilayotgan dushmanlarga o'q uzishi mumkin bo'lgan kamonchilarning umumiy soniga teng. Mudofa rejasining ishonchliligi har qanday bo'lim xafsizligining minimal qiymati hisoblanadi.

Dushman hujum qilishiga juda oz vaqt qoldi va siz bo'limlardagi kamonchilarni qayta joylashtirib chiqish uchun vaqingiz yo'q. Biroq sizda bo'limlarga joylashtirish uchun zaxirada \(k\) ta kamonchilar zaxirasi mavjud. Sizning vazifangiz mudofa rejasining ishonchliligini maksimal qilishdan iborat.

Kiruvchi ma'lumotlar:

Dastlabki satrda \(n,r,k(1\leq n\leq 500000, 0\leq r \leq n, 0\leq k\leq 10^{18})\) mos ravshda devorni tashkil etuvchi bo'limlar soni, har bir kamonchi o'q uzishi mumkun bo'lgan maksimal masofa va zaxiradagi kamonchilar soni. Kiyingi satrda \(n\) ta butun son \(a_i(0\leq a_i\leq 10^9)\) \(i-\)bo'limda joylashgan kamonchilar soni.

Chiquvchi ma'lumotlar:

Yagona butun sonni chop eting - mudofa rejasi ishonchliligining maksimal mumkun bo'lgan qiymati, ya'ni zaxiradagi \(k\) ta kamonchilarni optimal joylashtirish orqali devorning bir qismini himoya qilishning maksimal mumkun bo'lgan minimal qiymatini chop eting.

Izoh:

1-test: Jami bo'li \(4\) ta bo'lim devorni himoyalaydi.
\(1-\)bo'limda \(5\) ta kamonchi bor va bu bo'limga \(2-\)bo'limdagi kamonchilar yordam beraoladi, sababi \(|1-2|\leq r\) va bu bo'limning himoyasi \(5+1=6\) ga teng.
\(2-\)bo'limdiki esa \(5+1+1=7\) ga teng.
\(3-\)bo'limniki esa \(1+1+2=4\) ga teng.
\(4-\)bo'limniki \(1+2=3\) ga teng.
Siz agar uchunchi bo'limga zaxiradagi \(2\) ta kamonchini joyllashtirsangiz ikkinchi bo'liming himoyasi \(9\) ga, uchunchi bo'limning himoyasi \(6\) ga va to'rtinchi bo'limning himoyasi \(5\) ga o'zgaradi. Shunday qilib bo'limlar himoyalarini maksimal qilganimizdan so'ng, barcha bo'limlar uchun minimal himoyani tanlaymiz. \(min(6, 9, 6, 5) = 5\) bu qal'a devornig himoyasini ifodalaydi.

Misollar:

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