A. Qorboboning Yangi topshirig'i

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Har Yangi yil kechasi orzu va mo‘jizalar vaqti! Qorbobo o‘zining sehrli ustaxonasida elflar bilan ertalabgacha bolalar uchun ajoyib sovg‘alarni tayyorlaydi. Ammo bir kuni, sho‘x elflar Qorboboning eng sevimli chanasini tasodifan buzib qo‘yishdi! Qorbobo esa jazolash o‘rniga ularga noodatiy matematik sarguzasht tayyorladi.

Siz tasavvur qiling: ustaxonada 3 ta uzun stol bor. Birinchi stolga x ta, ikkinchi stolga y ta va uchinchi stolga z ta qutilar joylashtirilgan. Qorbobo "yaxshi joylashtirish" deb quyidagicha holatni ataydi:

har bir stolda kamida bittadan sovg'a mavjud;
x ni y ga bo‘lganda chiqqan qoldiq aynan y ni z ga bo‘lganda chiqqan qoldiqqa teng;
y ni z ga bo‘lganda chiqqan qoldiq aynan z ni x ga bo‘lganda chiqqan qoldiqqa teng.

Har bir stolda qutilar soni quyidagicha bo'lishi mumkin: birinchi stol uchun ko‘pi bilan a ta, ikkinchi stol uchun b ta va uchinchi stol uchun c ta. Qorbobo elflardan nechta turli xil "yaxshi joylashtirish" usullari borligini hisoblashni buyurdi. Elflar juda yaxshi usta bo'lgani bilan bunday topshiriq ularni qiynab qo'yadi, yangi yil arafasida elflarni bunday qiyin topshiriqdan qutqarish uchun bu topshiriq sizga yuklatildi.

Kiruvchi ma'lumotlar:

Birinchi qatorda T butun soni keltirilgan — testlar soni.
Keyingi T qatorning har birida uchta butun son: a, b va c beriladi.

\(1 \le T \le 100\)

\(1 \le a, b, c \le 100\)

Chiquvchi ma'lumotlar:

Har bir test uchun yuqoridagi shartlarga to'gri keladigan sovg‘a qutilari uchliklari sonini chiqaring.

Misollar:

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

B. RoboContest reyting tizimi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

"ICPC TUIT" hamjamiyati nafaqat algoritmlar bilan shug‘ullanadi, balki har bir talabaga haqiqiy qahramon kabi motivatsiya berishni ham biladi! Har safar biror talaba RoboContest reyting tizimida yangi darajaga erishsa, unga maxsus reyting darajasi yozilgan futbolka sovg‘a qilinadi. RoboContest tizimida reyting taqsimoti quyidagicha:

Daraja	Minimum reyting	Maksimum reyting
pupil	\(-\ \infty\)	1599
specialist	1600	1699
expert	1700	1799
candidate master	1800	1999
master	2000	2199
international master	2200	2399
grandmaster	2400	2699
international grandmaster	2700	2999
legendary grandmaster	3000	\(+\ \infty\)

Bir necha daqiqa oldin RoboContestda musobaqa o'tkazildi va unda hamjamiyat a'zolaridan biri qatnashdi. Vazifangiz sizga berilgan natijalarga ko'ra talaba qaysi daraja nomi tushirilgan futbolkaga ega bo'lishini aniqlash.

Kiruvchi ma'lumotlar:

Birinchi qatorda uzunligi 20 dan ko'p bo'lmagan, lotin alifbosining katta va kichik harflaridan tashkil topgan \(S\) satr - talabaning saytdagi taxallusi (username) kiritiladi.

Keyingi qatorda talabaning hozirgi reytingi - \(C \ (-10^9 \le C \le 10^9)\), maksimal reytingi - \(M \ (C \le M \le 10^9)\) va so'nggi musobaqada olgan deltasi - \(D (-10^9 \le D \le 10^9)\) beriladi.

Bundan tashqari talaba oldin kamida bitta musobaqada qatnashganligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Agar talaba yangi darajaga ko'tarilgan bo'lsa ushbu daraja nomini chiqaring. Aks holda "Sen buni uddalaysan" so'zini (qo'shtirnoqlarsiz) chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	rshohruh 2189 2189 29	international master
2	MDSPro 1834 1899 100	Sen buni uddalaysan
3	azizbek 1662 1710 75	Sen buni uddalaysan

C. Yangi yil sovg'alari

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Yangi yil kechasi yaqinlashmoqda va Qorbobo ustaxonasidagi elflar sovg'alarni qadoqlash uchun qizg'in ishlashmoqda! Ular oldida n ta sovg'a bor — har biri turli kattalikda va ularni qutilarga joylashtirish kerak. Har bir sovg'a bir xil oʻlchamdagi qutilarga joylanadi va \(i-\) sovg'ani sigʻdirish uchun quti hajmi kamida \(a_i\) boʻlishi lozim.

Elflar esa yirik sovg'alarni qutilarga joylashtirishni yoqtirishmaydi, ularning orzusi — eng kichik oʻlchamdagi qutilar ishlatish! Buning uchun ular bir sovg'ani ikkita butun qiymatli ikkita sovg'alarga boʻlib, har birini alohida qadoqlashlari mumkin. Ammo Qorbobo tartibni saqlash uchun faqat k marta bunday sehrli boʻlishga ruxsat bergan.

Elflarga yordam bering: berilgan sehrdan samarali foydalangan holda ishlatilishi mumkin bo'lgan eng kichik sovg'a qutisi o'lchamini aniqlang!

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida ikkita butun son n va k beriladi — ustaxonadagi sovg'alar soni va maksimal ajratish (bo'lish) operatsiyalari soni.

Keyingi qatorda n ta butun son \(a_i\) — har bir sovg'a oʻlchamlari beriladi.

\(1 \le n \le 10^6\)

\(1 \le a_i \le 10^9\)

\(0 \le k \le 10^9\)

Chiquvchi ma'lumotlar:

Sovg'alar uchun ishlatilishi mumkin bo'lgan qutining eng kichik hajmini chop eting.

Misollar:

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

D. Yangi yil bezagi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Har yili yangi yil bayramida elflar Qorboboning ustaxonasini rang-barang chiroqlar zanjiri bilan bezatadi. Bu yil ham elflar aynan shu ish bilan mashg'ul. Doimiy bir xillikdan zerikkan Qorbobo bu safar yangilik kiritishga qaror qildi: ba'zi chiroqlar bir xil rangda yonishi kerak, shunda ular jozibador ko'rinadi. Qorbobo elflarga aynan shunday topshiriq berdi. Tabiiyki, elflar rang-baranglikni yoqtiradi, shuning uchun elflar iloji boricha ko'proq turdagi ranglar bo'lishini xohlaydi. Qorboboning talablariga javob bergan holda, ko'pi bilan necha xil chiroq o'rnatish mumkin ekanligini aniqlashda elflarga yordam bering.

Kiruvchi ma'lumotlar:

Kirishning birinchi qatorida n va m - zanjirdagi chiroqlar soni va Qorboboning talablari soni kiritiladi.

Keyingi \(m\) qatorning har birida Qorboboning talabi kiritiladi. Har bir qator uchta butun son - \(a_i, b_i, l_i\) dan iborat

Bunday uchlik shuni anglatadiki, zanjirning
\(\{a_i, \ldots, a_i + l_i - 1\}\) va \(\{b_i, \ldots, b_i + l_i - 1\}\) raqamli chiroqlardan iborat bo‘laklari bir xil bo‘lishi kerak.

Boshqacha aytganda, \(a_i\) va \(b_i\) raqamli chiroqlar bir xil rangda bo‘lishi kerak; xuddi shunday, \(a_i + 1\) va \(b_i + 1\), va hokazo, \(a_i + l_i - 1\) va \(b_i + l_i - 1\) gacha.

\(2 \le n \le 2000\)

\(1 \le m \le 2000\)

\(1 \le a_i, b_i, l_i;\; a_i \ne b_i;\; a_i, b_i \le n - l_i + 1\)

Chiquvchi ma'lumotlar:

Elflar Qorboboning shartlarini bajargan holda ko'pi bilan necha xil turdagi chiroqlardan foydalana olishini chop eting.

Misollar:

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

E. O'xshash familiyalar

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Yangi yil oqshomida chaqqon elflar bolalarga atalgan sovg'alarni tayyorlashmoqda. Har bir sovg'aning o'z egasiga aniq yetib borishi uchun, har bir qutiga egasining familiyasi maxsus harfli stikerlar yordamida yoziladi. Biroq, elf dasturchilarning e'tiborsizligi sababli, ular familiyalarni bazan chalkashtirib yuboradigan dastur tuzib qo'yishdi! Dastur harflar bir xil sonli va turli bo'lsa ham, familiyalarni bir-biriga "o'xshash" deb qabul qiladi: masalan, ABCA va CAAB dastur uchun bir xil ko'rinadi, chunki har bir harfning soni bir xil. Ammo ABBC va ABCA – bunday emas.
Maxsus sovg'alarni to'g'ri egalariga yetkazishga shoshayotgan elflar, familiyalarni to'g'ri tartibga solish uchun, familiyada faqat qo'shni harflarning joyini almashtirishga ruxsat berilgan. Sizning vazifangiz — elflarga yordam berib, familiyani kerakli tartibga keltirish uchun minimal qo'shni harf almashtirish sonini topish!

Kiruvchi ma'lumotlar:

Kirish faylining dastalbki qatorida butun son \(n \ (1 \le n \le 10^6)\) - familyaning uzunligi kiritiladi.

Keyingi qatorda ingliz alifbosidagi haqiqiy familiya beriladi.

So'nggi qatorda esa, robot tomonidan "o'xshash" deb yozilgan familiya kiritiladi.

Chiquvchi ma'lumotlar:

Minimal nechta qo'shni harflar o'rnini almashtirish kerakligini aniqlang va ekranga chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 ABCA CAAB	3
2	2 AB BA	1

F. Qorboboning Sehrli Ustaxonasi

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Har yili bir xil ustaxonada ishlashdan charchagan Qorbobo nihoyat yangilik qilishga qaror qildi — u uchun ajoyib ustaxona quriladi! Lekin Qorbobo band: bolalarga sovg'alar ulashishi kerak, shuning uchun bu vazifani uning quvnoq elflari bajaradi. Yangi ustaxona uchun Qorbobo maxsus uzun yer tanladi: bu yer qator qilib joylashgan n ta bo'lakdan iborat. Har bir bo'lak o'z balandligiga ega va, afsuski, yer tekis emas. Ustaxonani mustahkam va zamonaviy qilish uchun elflar barcha bo'laklarni bir xil balandlikka keltirishlari kerak!

Elflarning sehrli kuchi bor! Ular ikki xil sehri ishlata olishadi: ketma-ket joylashgan bir yoki bir nechta bo'lak tanlanadi va ular ustida 2 ta sehrdan bittasi qo'llaniladi:

birinchi sehr yordamida tanlangan barcha maydonning balandligini a metrga oshirish yoki a metrga kamaytirish mumkin;
ikkinchi sehr esa bo'lak balandligini b metrga oshirish, yoki b metrga kamaytirish mumkin.

Sehr davomida qaysidir yer bo'laklari balandligi manfiy bo'lishi ham mumkin. Har bir sehr ishlatish 1 daqiqa vaqt oladi va bir vaqtda faqat bitta sehrni bajarish mumkin. Barcha bo'laklarning balandligini 0 ga tenglashtirish uchun, elflar eng kamida nechta sehr ishlatishlari — ya'ni, minimal nechta daqiqa vaqt kerak bo'lishini aniqlang!

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son n, a, b - bo'laklar soni, birinchi va ikkinchi sehr parametrlari kiritiladi.

Keyingi qatorda n ta butun son \(h_i\) - har bir bo'lak balandligi kiritiladi.

\(1 \le n \le 10^5\)

\(1 \le a, b \le 10^9\)

\(-10^9 \le h_i \le 10^9\)

Chiquvchi ma'lumotlar:

Barcha yerni bir xil balandlikka keltirish uchun eng kamida qancha vaqt sarflanishini chop eting. Agar buning iloji bo'lmasa, -1 ni chop eting.

Misollar:

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