A. Dumaloq sonlar

Xotira: 32 MB, Vaqt: 1000 ms

Masala

d000...000 ko'rinishidagi ya'ni birinchi raqamidan boshqa barchasi nol bo'lgan songa "dumaloq son" deyiladi. Bundan tashqari 1 dan 9 gacha bo'lgan raqamlar ham dumaloq son hisoblanadi.
Sizga n natural soni berilgan. Siz shunday dumaloq sonlarni topingki ularni yig'indisi n ga teng bo'lsin. Agar buning imkoni bo'lsa "yes" aks holda "no" chiqaring.

Kiruvchi ma'lumotlar:

Bitta qatorda n natular soni. (1<=n<=\(10^{18}\))

Chiquvchi ma'lumotlar:

Yig'indisi n ga teng bo'lgan dumaloq sonlar mavjud bo'lsa "yes", aks holda "no" chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1111	yes

B. Bilag'on va Bilmasvoy

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bilag'on va Bilmasvoy har kuni masalalar yechib, o‘zaro raqobat qiladilar. Kunning oxirida ular nechta masala yechganini taqqoslaydi.

Agar Bilag'on ko‘proq masala yechgan bo‘lsa, “Bilag'on” g'olib bo'ladi.
Agar Bilmasvoy ko‘proq yechgan bo‘lsa, “Bilmasvoy” g'olib bo'ladi.
Ikkalasi ham bir xil sonli masala yechgan bo‘lsa, ular “Durrang” deya e’lon qiladilar.

Sizning vazifangiz kun oxirida kim g'olib bo'lganini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda Bilag'on yechgan masalalar soni.
Ikkinchi qatorda Bilmasvoy yechgan masalalar soni.
Barcha sonlar 10^18 gacha bo'ladi.

Chiquvchi ma'lumotlar:

Kun oxirida kim g'olib bo'lganini aniqlang.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	9 7	Bilag'on
2	1 1	Durrang

C. Uchburchak

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bilmasvoy bugun matematika darsidan uchburchak mavzusini o'rgandi. Dars tugaganidan so'ng ustozi unga quyidagicha topshiriq berdi: Uchburchakning 3 ta tomoni uzunligi beriladi, shu tomonlardan foydalangan holda uchburchakning turini (teng yonli, teng tomonli, turli tomonli) yoki uchburchak yasash mumkin emasligini aniqlashingiz kerak.

Agar uchburchak yasashning iloji bo'lmasa “mumkin emas” so'zi chiqsin.
Agar uchburchak teng tomonli bo'lsa “teng tomonli” so'zi chiqsin.
Agar uchburchak teng yonli bo'lsa “teng yonli” so'zi chiqsin.
Agar uchburchak turli tomonli bo'lsa “turli tomonli” so'zi chiqsin.

Kiruvchi ma'lumotlar:

Bitta qatorda 3 ta Natural a, b, c sonlari. (1 ≤ a, b, c ≤ 1000).

Chiquvchi ma'lumotlar:

Bitta qatorda masala javobini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 4 5	turli tomonli
2	10 99 25	mumkin emas
3	5 5 5	teng tomonli

D. G'aroyib Lift

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Ko'p qavatli binoda g'alati qoidalar asosida ishlaydigan lift mavjud. Uning harakati uchun quyidagi shartlar o'rinli:

Liftning har bir qavat orasidagi harakati uchun 1 soniya vaqt sarflanadi.
Lift yuqoriga harakatlanayotganda faqat toq qavatlarda to'xtay oladi (1, 3, 5, ...).
Lift pastga harakatlanayotganda faqat juft qavatlarda to'xtay oladi (..., 6, 4, 2).
Odamlar faqat lift to'xtaydigan qavatlardagina unga kirishi yoki undan chiqishi mumkin.
Lift 1-qavatda va N-qavatda har qanday holatda to'xtaydi.

Lift o'z harakatini 1-qavatdan boshlab eng yuqori N-qavatgacha olib boradi, so'ngra yo'nalishini o'zgartirib, 1-qavatga qaytadi va bu jarayon doimiy takrorlanadi.

Anvar hozirda A-qavatda va u B-qavatga borishi kerak. U o'z manziliga yetib borishi uchun ketadigan minimal vaqtni toping.

Muhim: Anvar liftni kutib turishi uchun qo'shimcha vaqt sarflamaydi deb hisoblang. Vaqt faqat lift ichida qavatlar oralig'ida harakatlanganida hisoblanadi.

Kiruvchi ma'lumotlar:

Yagona qatorda uchta butun son: N, A, B (2 ≤ N ≤ 100; 1 ≤ A, B ≤ N;).

Chiquvchi ma'lumotlar:

Anvar manziliga yetib borishi uchun liftda o'tkazgan minnimal vaqtni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 1 2	1
2	4 2 4	4

E. Tartiblash

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga 4 ta elementdan iborat butun sonli qator berilgan. Siz bu qatordagi istalgan bir nechta ketma ket elementlarni tanlab ularning qiymatini bir xil songa oshirishingiz yoki kamaytirishingiz mumkin.
Sonli qator elementlarining barchasi teng bo'lishi uchun yuqoridagi amallarni bajargan holda eng kamida nechta qadam talab qilinadi?

Kiruvchi ma'lumotlar:

Birchi qatorda qiymati -100 va 100 oralig'ida bo'lgan 4 ta butun son probel bilan ajratilgan holda kiritiladi,

Chiquvchi ma'lumotlar:

Sonli qatorning barcha elementlari bir xil qiymatga ega bo'lishi uchun kerak bo'lgan eng kam qadamlar soni.

Misollar:

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

F. Massiv

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bilmasvoyga N ta butun sondan iborat A[1 … N] massivi berildi. U shu massivning qanday tartibda joylashganini aniqlashi kerak. Massiv to‘rt xil holatdan biriga kiradi:

Tur nomi	Ta’rif
O‘suvchi	Har bir keyingi element avvalgisidan katta: `A[i] <= A[i + 1]`
Kamayuvchi	Har bir keyingi element avvalgisidan kichik: `A[i] >= A[i + 1]`
Teng	Barcha elementlar bir xil: `A[1] = A[2] = … = A[N]`
Aralash	Yuqoridagi uchta holatdan hech biriga mos kelmaydi (masalan, ba’zi joyda ko‘tariladi, ba’zi joyda tushadi)

Kiruvchi ma'lumotlar:

Birinchi qatorda N natural soni. (1 ≤ N ≤ 1000).
Ikkinchi qatorda N ta elementdan tashkil topgan A massiv kiritiladi. (-1000 ≤ A[i] ≤ 1000).

Chiquvchi ma'lumotlar:

Bitta qatorda masala javobini chiqaring.

Izoh:

1 1 2 2 3 o'suvchi ketma ketlikka kiradi.
6 6 5 4 1 kamayuvchi ketma ketlikka kiradi.
5 5 5 5 5 esa faqatgina teng ketma ketlikka kiradi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 4 3 1 2 5	Aralash
2	6 1 2 3 4 5 6	O'suvchi

G. 3 va 5

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bilmasvoy bugun optimallashtirish haqidagi darslarni va arximetik progressiyani o'rgandi. Endi u quyidagicha masalaga duch keldi. A va B naturla sonlari berilgan sizning vazifangiz A va B orasidagi 3 ga yoki 5 ga bo'linadigan sonlar yi'g'indisini toping.

Kiruvchi ma'lumotlar:

Bitta qatorda 2 ta Natural son A va B beriladi.
1 <= A <= B <= 10^18

Chiquvchi ma'lumotlar:

Bitta qatorda masala yechimini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 1	0
2	1 100	2418

H. Kitob javoni

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Ulug'bek rasadxonasining qadimiy kutubxonasida kitoblar javonlarga bo'yi bo'yicha o'sish tartibida taxlab chiqilgan. Yosh munajjimga bir necha bor ma'lum bir balandlikdagi kitobni topib kelish vazifasi yuklatiladi. Javonda minglab kitoblar borligi sababli, har safar boshidan oxirigacha qarab chiqish juda ko'p vaqt oladi. Siz munajjimga yordam berish uchun samarali qidiruv tizimini yaratishingiz kerak. Tizimga javondagi kitoblar bo'ylari haqidagi ma'lumot va bir nechta so'rovlar beriladi. Har bir so'rovda qidirilayotgan kitobning bo'yi x beriladi. Siz shu bo'ydagi kitob javonda nechanchi o'rinda (chapdan o'ngga, 1-dan boshlab sanaganda) turganini topishingiz kerak. Agar bunday bo'ydagi kitob javonda mavjud bo'lmasa, -1 deb javob berish kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda javondagi kitoblar soni N kiritiladi. Ikkinchi qatorda N ta butun son — o'sish tartibida saralangan kitoblar bo'ylari kiritiladi. Uchinchi qatorda so'rovlar soni Q kiritiladi. Keyingi Q ta qatorning har birida qidirilayotgan kitob bo'yi x kiritiladi.

1 <= N, Q <= 10^5
1 <= kitob bo'yi, x <= 10^9

Chiquvchi ma'lumotlar:

Har bir so'rov uchun alohida qatorda kitobning 1-dan boshlab hisoblangan tartib raqamini yoki u mavjud bo'lmasa -1 ni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 10 25 25 38 45 70 82 4 25 40 82 10	2 -1 7 1
2	1 5 1 5	1

I. Xattot Tanlovi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Qadimiy Buxoro madrasalaridan birida xattotlik san'ati bo'yicha musobaqa o'tkazilmoqda. Musobaqa shartiga ko'ra, har bir xattot o'zi uchun 1 dan N gacha bo'lgan sonlardan birini tanlashi va shu sonning "mukammalligi"ga mos naqsh chizishi kerak. Sonning mukammalligi uning natural bo'luvchilari soni bilan o'lchanadi. Qancha ko'p bo'luvchisi bo'lsa, son shuncha mukammal hisoblanadi. Sizning vazifangiz — tanlov ishtirokchisiga yordam berish. U sizdan 1 dan N gacha bo'lgan sonlar orasida eng mukammalini, ya'ni bo'luvchilari soni eng ko'p bo'lganini topib berishingizni so'radi. Agar bunday sonlar bir nechta bo'lsa, ularning eng kichigini tanlash kerak, chunki kichik sonlar nafisroq hisoblanadi.

Kiruvchi ma'lumotlar:

Yagona qatorda butun son N kiritiladi.

1 <= N <= 100,000

Chiquvchi ma'lumotlar:

1 dan N gacha bo'lgan sonlar ichida bo'luvchilari soni maksimal bo'lgan eng kichik sonni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	20	12
2	1	1

J. Sayohat

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sardor sayohatlarni yoqtiradi. Sardorning 2 ta shlyapasi bor: oq va qora. U sayohat qilganida birinchi shaharga oq shlapasini kiyib borsa, ikkinchi shaharga qora shlapasini kiyib boradi, uchinchi shaharga oq va to'rtinchi shaharga yana qora... . Hech qachon ketma-ket ikki shaharga bir xil shlayapa kiymaydi.
Sardor shu yil borish uchun n ta davlatning ro'yxatini tuzib chiqdi. Ularning har birida \(a_1, a_2, a_3,...,a_n\) ta shahar bor. Lekin Sardor sayohatni oq shlyapa bilan boshlab oq shlyapa bilan yakunlamoqchi.
Agar Sardor qaysidir davlatni tanlasa, undagi barcha shaharlarga borishi shart. Sardor sayohatni oq shlyapada yakunlashi uchun eng ko'pi bilan nechta shaharga borishi mumkin.

Kiruvchi ma'lumotlar:

Birinchi satrda bitta butun son n yozilgan ( 1≤n≤100 ) — Sardorning borishi mumkin bo'lgan davlatlar soni. Ikkinchi satrda n ta butun son \(a_i\) ( 1≤\(a_i\)≤100 ) yozilgan — i-chi davlatdagi shaharlar soni.

Chiquvchi ma'lumotlar:

Safarni oq shlyapada yakunlash uchun kerak bo'lgan maksimal shaharlar soni. Agar buning imkoni bo'lmasa 0 chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 2 3	5
2	10 90 72 76 60 22 87 5 67 17 65	561

K. Registon Mehmonlari

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Samarqandning yuragi bo'lgan Registon maydoni har kuni minglab sayyohlarni o'ziga jalb qiladi. Maydon ma'muriyati xavfsizlik va qulaylikni ta'minlash maqsadida bir vaqtning o'zida maydonda nechta odam bo'lishini doimiy nazorat qilib boradi. Sizning vazifangiz, ma'muriyat uchun maxsus dastur ishlab chiqish. Dasturga kun davomida maydonga tashrif buyurgan N ta sayyohning har birining kirish va chiqish vaqtlari kiritiladi. Siz shu ma'lumotlar asosida kunning istalgan bir paytida maydonda bir vaqtning o'zida bo'lgan sayyohlarning soni eng ko'pi bilan nechaga yetganini aniqlashingiz kerak.

Masalan, bir sayyoh 10-daqiqada kirib, 20-daqiqada chiqsa, u [10, 20] vaqt oralig'ida, ya'ni 10-daqiqadan 20-daqiqagacha maydonda bo'lgan hisoblanadi.

Kiruvchi ma'lumotlar:

Birinchi qatorda sayyohlar soni N kiritiladi. Keyingi N ta qatorning har birida ikkita butun son: sayyohning maydonga kirish vaqti S[i] va chiqish vaqti E[i] kiritiladi.

1 <= N <= 2 * 10^5
0 <= S[i] < E[i] <= 10^9

Chiquvchi ma'lumotlar:

Yagona qatorda bir vaqtning o'zida maydonda bo'lgan maksimal sayyohlar sonini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 0 1	1
2	2 0 2 1 3	2

L. Kriptografning Sirli Soni

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Maxfiy xizmat agenti "Burgut" dushmanning shifrlangan xabarini qo'lga kiritdi. Xabarni ochish uchun kalit — bu "maxsus son". Maxsus son deb shunday K natural songa aytiladiki, uning barcha tub bo'luvchilari yig'indisi ham tub son bo'lishi kerak. Masalan, 12 sonining tub bo'luvchilari 2 va 3. Ularning yig'indisi 2+3=5, bu ham tub son. Demak, 12 — maxsus son. "Burgut"ga 1 dan N gacha bo'lgan oraliqda nechta shunday maxsus son borligini tezda hisoblashga yordam bering.

Kiruvchi ma'lumotlar:

Yagona butun son N (1≤N≤2*10^6).

Chiquvchi ma'lumotlar:

1 dan N gacha bo'lgan oraliqdagi maxsus sonlar miqdori.

Izoh:

Maxsus sonlar ro'yxati: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 16, 17, 18, 19, 20.
Maxsus bo'lmagan sonlar: 1, 14, 15.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	20	17

M. Xazinaga Oltin Yig'ish

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Qaroqchilar sardori Jek afsonaviy xazinani topdi. Xazinada N ta oltin yombi bor. Har bir yombining o'z og'irligi bor. Jek o'z kemasiga faqat aniq W og'irlikdagi oltinni olib keta oladi — na bir gramm ortiq, na bir gramm kam. Aks holda, qadimiy la'nat kemani cho'ktirib yuboradi. Jek yombilardan shunday to'plam tuza oladimi-ki, ularning umumiy og'irligi aniq W ga teng bo'lsin?

Kiruvchi ma'lumotlar:

Birinchi qatorda N (1≤N≤40) va W (1≤W≤10^18). Ikkinchi qatorda N ta yombining og'irligi.

Chiquvchi ma'lumotlar:

Agar umumiy og'irlik W ga teng bo'ladigan to'plam tuzish mumkin bo'lsa "Yes", aks holda "No".

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 50 2 5 8 10 15 17 20 22 25 30	Yes

N. Robotlar Poygasi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

"Kiber-Olimp" musobaqasida sizning jamoangizga N ta vazifadan iborat topshiriq kelib tushdi. Musobaqa shartiga ko'ra, jamoa N ta vazifani bajarishi kerak. Har bir vazifani bajarish uchun ma'lum bir T[i] vaqt kerak bo'ladi. Sizda bu vazifalarni bajarish uchun M ta robot mavjud.

Robotlarning ishlash prinsipi quyidagicha: Vazifalar ro'yxatda qanday tartibda kelgan bo'lsa, ularni xuddi shu ketma-ketlikni buzmagan holda robotlarga taqsimlash kerak. Ya'ni, birinchi robot ro'yxat boshidan boshlab ketma-ket bir nechta vazifani oladi. Ikkinchi robot esa birinchi robot ishini tugatgan vazifaning keyingisidan boshlab o'ziga vazifalarni oladi va hokazo. Hech bir robot vazifalarni tanlab yoki o'rnini almashtirib ola olmaydi.

Sizning vazifangiz — vazifalarni robotlar o'rtasida shunday taqsimlash kerakki, eng ko'p ish vaqt sarflagan (eng band bo'lgan) robotning umumiy ish vaqti imkon qadar minimal bo'lsin.

Kiruvchi ma'lumotlar:

Kiritish: Birinchi qatorda N (1≤N≤10^5) va M (1≤M≤10^5). Ikkinchi qatorda N ta butun son: T[1], ..., T[N] (1≤T[i]≤10^9).

Chiquvchi ma'lumotlar:

Minimal mumkin bo'lgan maksimal ish vaqti.

Izoh:

Maqsadimiz — vazifalarni 3 ta robotga shunday taqsimlashki, eng ko'p ishlagan robotning umumiy ish vaqti imkon qadar kam bo'lsin. Javob 12. Keling, nima uchun aynan 12 ekanligini ko'rib chiqamiz.

Biz har bir robotning ish vaqtini 12 dan oshirmasdan barcha vazifalarni taqsimlay olamiz. Mana bir misol taqsimot:

1-robot: 8 va 4 vaqtli vazifalarni oladi. Umumiy ish vaqti: 8 + 4 = 12.
2-robot: 7 va 5 vaqtli vazifalarni oladi. Umumiy ish vaqti: 7 + 5 = 12.
3-robot: 6, 3 va 2 vaqtli vazifalarni oladi. Umumiy ish vaqti: 6 + 3 + 2 = 11.

Misollar:

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