A. Diagonallar soni

Xotira: 16 MB, Vaqt: 1000 ms

Masala

N Natural son berilgan. Sizning vazifangiz N ta tomonga ega bo’lgan qavariq ko’pburchakning diagonallar sonini topishdan iborat.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida yagona son, $N (1 ≤ N ≤ 10^9)$ kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida yagona son, masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5	5
2	6	9

B. Sonni izlab top!

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Bu interaktiv masala!

Hakamlar hay’ati dasturi N(1 ≤ N ≤ 10⁹) sonini o’ylaydi. Sizning dasturingiz ko’pi bilan 100 ta so’rovda hakamlar hay’ati dasturi o’ylagan sonni izlab topishi talab etiladi. Har bir so’ravda dasturingiz hakamlar hay’atining dasturiga X(-2³¹ ≤ X < 2³¹) sonini berganida hakamlar hay’atining dasturi sizga kirish oqimida har bir so’rov uchun alohida qatorda:

agar X > N bo’lsa ‘>’ belgisi, yoki

agar X < N bo’lsa ‘<’ belgisi, yoki

agar X = N bo’lsa ‘=’ belgisini kiritadi.

Kiruvchi ma'lumotlar:

Kirish faylida sizning har bir so’rovingizda alohida qatorda hakamlar hay’atining dasturiga bergan X soningizga mos holda >, < yoki = belgilari berilgan.

Chiquvchi ma'lumotlar:

Ko’pi bilan 100 ta so’rovda hakamlar hay’atining dasturi o’ylagan sonni izlab toping. Sizning oxirgi so’rovingiz hakamlar hay’atining o’ylagan soni deb qabul qilinadi!

ESLATMA: Interaktiv masalada sizning javobingizni hakamlar hay’ati qabul qila olishi uchun siz har bir so’rovingiz oxirida

Agar Pascal tilida ishlagan bo’lsangiz: flush(output)
Agar C/C++ tilida ishlagan bo’lsangiz fflush(stdout) yoki cout.flush()
Agar Java tilida ishlagan bo’lsangiz System.out.flush()
Agar pythonda ishlagan bo’lsangiz sys.stdout.flush()
Agar C# tilida ishlagan bo’lsangiz Console.Out.Flush()

Buyruqlardan birini yozishingiz kerak bo’ladi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	> < > =	6 3 5 4

C. Rangli markerlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga kvadrat katakchalardan iborat cheksiz jadval beriladi. Dastlab, barcha katak oq rangda.

Sizda qizil va ko'k marker bor. Siz jami a ta katakni qizil marker bilan, b ta katakni ko’k marker bilan bo'yashingiz mumkin. Bitta katakni bir vaqtda har ikkala rangda bo’yash mumkin emas. Ikkala markerni ham to’liq ishlatishingiz kerak, buning uchun jadvalda jami a ta katak qizil rangda, b ta katak ko’k rangda bo’lishi kerak.

Siz jadvalni quyidagi qonuniyat asosida bo’yashingiz kerak:

Jadvalda yuzasi a + b ga teng bo’lgan, bo’yalgan to’rtburchak hosil bo’lishi kerak;
kamida bitta rangdagi barcha kataklar ham to'rtburchak hosil qilsin .

To'g'ri bo’yashga ba'zi misollari:

Noto’g’ri bo’yashga ba’zi misollar:

Berilgan a va b dan foydalanib to’g’ri bo’yash hisoblanadigan to’rtburchaklar ichidan perimetri eng kichik bo’lgan to’rtburchakning perimetrini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida ikkita butun son, $a$ va $b(1 \le a,b \le 10^{14})$ , qizil va ko’k markerda bo’yalishi kerak bo’lgan kataklar soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, masala yechimini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 4	12
2	3 9	14
3	9 3	14
4	3 6	12

D. Analiz

Xotira: 16 MB, Vaqt: 3000 ms

Masala

Insertion sort algoritmi barchaga ma’lum. Shunday bo’lsada yanam bir bor eslatib o’tamiz:

n uzunlikdagi massivni kamaymaydigan tartibda saralash uchun:

arr[1] dan arr[n] gacha barcha element birma-bir yurib chiqiladi;
Joriy element o’zidan oldingilar bilan solishtiriladi;
Joriy elementdan katta bo’lgan barcha elementlar bir pog’ona o’ngga suriladi, bo’sh qolgan joyga joriy element joylashtiriladi.

Misol uchun: 4 3 2 10 12 1 5 6 ketma-ketlikdagi massiv quyidagi ketma-ketlikda saralanadi:

Bu saralash algoritmida asosiy vaqt elementlarni surish uchun ketadi. Jami surishlar soni yuqoridagi jadvalda qizil rang bilan ko’rsatilgan kataklar soniga teng bo’lishi bizga ma’lum.

Siz n ta elementdan iborat arr massivi uchun Insertion sort algoritmi necha marotaba surish amalini ishlatishini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, $T (1 \le T \le 15)$ testlar soni kiritiladi. Ikkinchi satrdan boshlab, har bir test uchun alohida ikkita satrning birinchi satrida $n (1 \le n \le 100000)$ , massiv elementlari soni, ikkinchi satrida n ta butun son, $arr (1 \le arr_i \le 10000000)$ massiv elementlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida satrda bitta butun son, masala yechimini chop eting

Misollar:

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

E. Palindrom

Xotira: 64 MB, Vaqt: 2000 ms

Masala

Sizda a va b satrlari bor, siz quyidagi shartlarni qanoatlantiradigan s satrni topishingiz kerak:

s ni s = $s_a+s_b$ shaklida yozib bo’lsin. Bu yerda $s_a$ a satrning bo’sh bo’lmagan qism satri ekanligini bildiradi, $s_b$ b satrning bo’sh bo’lmagan qism satri ekanligini bildiradi.
s palindrom satr bo’lsin.
s satr bo’lishi mumkin bo’lgan satrlar ichida eng uzuni, eng uzunlar ichida esa leksikografik eng kichigi bo’lsin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, $T (1 \le T \le 10)$ , so’rovlar soni kiritiladi. Keyingi satrdan boshlab har bir so’rov uchun alohida ikkita qatorda $a$ va $b (1 \le |a|, |b| \le 10^5)$ satrlari kiritiladi.

$a$ va $b$ satrlari ingliz alifbosining kichik harflaridan tashkil topgan.

Barcha so’rovlardagi $|a|$ lar yig’indisi $2*10^5$ dan oshmaydi.

Barcha so’rovlardagi $|b|$ lar yig’indisi $2*10^5$ dan oshmaydi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda, agar yuqoridagi shartlarni qanoatlantiradigan s satri mavjud bo’lsa s satrini chop eting, aks holda -1 sonini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 bac bac abc def jdfh fds	aba -1 dfhfd