A. Sort

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga $N$ ta nomanfiy butun sonlar beriladi, siz bu sonlarni kamaymaydigan tartibda saralab chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, $N(1 \le N \le 200000)$. Keyingi $N$ ta satrda nomanfiy va qiymati $10^{1000000}$ dan oshmaydigan sonlar berilgan. Barcha sonlardagi umumiy ishlatilgan raqamlar miqdori $10^6$ dan oshmasligi kafolotlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida kiritilgan sonlarning kamaymaydigan tartibda, har birini alohida qatorda chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 31415926535897932384626433832795 1 3 10 3 5	1 3 3 5 10 31415926535897932384626433832795

B. Parol

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dilnura yaqinda onlayn hakam tizimlarining biridan ro’yxatdan o’tayotganida tizim undan o’zi uchun maxsus login va maxsus parol tanlashni so’radi, bundan tashqari oddiy parol emas,aynan qiyin parol tanlashi kerakligini talab qildi. Tizim parolni qiyin deb qabul qilishi uchun Dilnuraning yozgan parole quyidagi talablarning barchasiga mos kelishi kerak:

Kamida 6 ta belgidan iborat bo’lishi kerak;
Kamida bitta raqam qatnashishi kerak;
Kamida bitta Ingliz alifbosining kichik harfi qatnashishi kerak
Kamida bitta Ingliz alifbosining katta harfi qatnashishi kerak
Kamida bitta maxsus belgi qatnashishi kerak. Maxsus belgilar: !@#$%^&*()-+

Dilnura parol sifatida uzunligi n ga teng bo’lgan tasodifiy satr kiritdi, ammo u tergan parole qiyin parol bo’lgan yoki yo’qligiga ishonchi komil emas. Sizga Dilnuraning parol sifatida kiritgan satri beriladi, siz parol qiyin hisoblanishi uchun bu satrga kamida nechta belgi qo’shish kerakligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, $n(1 ≤ n ≤ 100)$ kiritiladi. Ikkinchi satrda esa $n$ ta belgidan iborat satr, Dilnuraning parol sifatida yozgan satri kiritiladi. Kiritilgan parol ingliz alifbosining kichik va katta harflaridan, raqamlardan va maxsus belgilardan tashkil topganligi kafolotlanadi.

Chiquvchi ma'lumotlar:

Parol qiyin hisoblanishi uchun Dilnuraning yozgan satriga kamida nechta belgi qo’shish kerakligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 Ab1	3
2	12 #RoboContest	1

C. Biznesmen Jinni

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Bir jinni uy oldi sottisi bilan shug’ullanar ekan. Uning jinniligi shunda ekanki, u hech qachon sotib olgan uyini xarid narxidan qimmatga sotmas ekan, ya’ni u bu savdodan hech qanday foyda ko’rmaydi, bunga sabab uning boshqa bizneslari mavjudligi va bu kasbni shunchaki hobbiy sifatida qabul qilishida. Unda hozirda bir uyning N kun davomidagi narxlarining o’zgarish grafigi bor, shu N kun ichida uyni xarid qilishi va uni xarid narxidan ko’p bo’lmagan pulga sotishi kerak(xarid qilingan kundan keying kunlardagina sotish mumkin).

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida bitta butun son, N(1 ≤ N ≤ 200000). Keyingi qatorda N ta [1, 10¹⁶] oralig’idagi butun son, uy narxining grafigi berilgan.

Chiquvchi ma'lumotlar:

Biznesmen Jinnining eng kam ziyoni qancha bo’lishini aniqlang. Yechim mavjudligi kafolotlanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 5 10 3	2
2	5 20 7 8 2 5	2

D. Oraliqlar daraxti

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Azimjon N ta har xil elementdan iborat(qiymatlari takrorlanmaydigan) A massiv uchun 2×N-1 ta elementdan iborat T oraliqlar daraxti orqali minimum qiymatni hisoblash uchun quyidagi tartibda tuzdi:

for i in range(0, N): T[i+N-1] = A[i]

for i in range(N-2, -1, -1): T[i] = min(T[i*2+1], T[i*2+2])

Shundan so’ng o’zining A massivini tashlab yubordi va o’ziga 2×N-1 ta elementdan iborat T massivni saqlab qoldi. Azimjon uyda yo’qligidan foydalanib uning ukasi Azimjonning T massiv elementlarini qiymatlarini tartibini almashtirib qo’ydi, va hattoki ba’zi elementlarining qiymatini o’zgartirib ham qo’ygan bo’lishi mumkin. Bundan xabar topgan Azimjon o’zining T massivini qiymatlari almashgan bo’lsada yuqoridagi qonuniyatiga mos keladigan holda qayta tiklamoqchi bo’ldi. Qayta tiklaganida ham A massivga mos keladigan elementlar unikal(yagona)ligini saqlab qolishi kerak. Sizning vazifangiz Azimjon buni eplay oladimi yoki yo’qligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida N=2^k shaklidagi bitta butun son, N(1 ≤ N ≤ 2¹⁸) soni kiritiladi. Keyingi satrda 2×N-1 ta son, Azimjonning ukasidan qolgan T(-10⁹ ≤ T_i ≤ 10⁹) massivining elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida agar Azimjon o’z massivini qayta tiklay olsa dastlabki satrda YES so’zini, keyingi satrda esa 2×N-1 ta elementdan iborat T massivining qayta tiklangan holatini (Agar yechimlar ko’p bo’ladigan bo’lsa leksikografik eng kichigini) chop eting, agar qayta tiklay olmasa yagona satrda NO so’zini chop eting.

Misollar:

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