A. TreeFactors

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Azimjon $N$ sonidan ildizi $N$ ga teng bo’lgan sikil mavjud bo’lmagan daraxt hosil qilishni ajoyib yo’lini o’ylab topdi, ya’ni u daraxni quyidagicha hosil qiladi.

$N$ sonining tub bo’luvchilari ichidan eng kichigini tanlab oladi ya’ni $P_i$ ni;
$N/P_i$ va $P_i$ sonlarini $N$ ga ulaydi;
$N$ ning yangi qiymati uchun $N=N/P_i$ ni oladi.

Bu jarayondi N soni tub son bo’lib qolguncha davom ettiradi. Sizning vazifangiz hosil bo’lgan daraxtning ildizidan tub qiymatli shoxlarining uchigacha bo’lgan masofalar yig’indisini hisoblash(ikki bog’langan tugunlarni o’rtasidagi masofa 1 ga teng deb hisoblang).

Misol: $N=8$ bo’lgan holat rasimda tasvirlangan.

Kiruvchi ma'lumotlar:

Kirish fayilida yagona natural son $N(2 \le N \le 10^{12})$.

Chiquvchi ma'lumotlar:

Сhiqish fayilida yagona son masalaning javobi.

Misollar:

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

B. Sonni top

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dastur 3 xonali $\overline{abc}$ son o’yladi va o’ylagan sonini raqamlari testkari tartibda yozib oldi $\overline{cba}$ hosil bo’lgan sondi dastur o’ylagan sondan ayirib modulini oldi ya’ni $\overline{xyz} = |\overline{abc} - \overline{cba}|$. Endi dastur $X = \overline{xyz} + \overline{zyx}$yig’indini hisoblab bo’lgach sizga $X$ sonini aytadi siz dastur dastlab qanday son o’ylagan ekanligini topishingiz kerak.

Kiruvchi ma'lumotlar:

Kirish fayilida yagona X butun soni berilgan.

Chiquvchi ma'lumotlar:

Chiqish fayilida dastur dastlab o’ylagan sondi chop eting agar bunday yechimlar bir nechta bo’lsa eng kichigini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1089	103

C. Svetafor soni

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Baytlandiya shaxrida yir osti tunnellari qurilmoqda hozirda jami $K$ ta tunnel mavjud bo’lib bu tunnellar jami $N$ ta chorraxada kesishadi(chorraxalar 1 dan $N$ gacha raqamlangan). Bu mamlakatning hukumdori har bir tunneling boshiga va oxiriga svetafor qo’yishni rejalashtirdi. Sizning vazifangiz har bir chorraxada jami nechtadan svetafor o’rnatish kerak ekanligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish fayilining birinchi satirida ikkita natural son $N, K (2 \le N, K \le 10^5)$ mos ravishda chorraxa va tunnellar soni. Kiyingi $K$ ta satirda $u,v (1\le u,v \le N)$ chorraxalarni bog’lanishlari.

Chiquvchi ma'lumotlar:

Har bir chorraxada jami nechtadan svetafor o’rnarish kerak ekanligini alohida satirlarda chop eting(chorraxa raqamlari kamayish tartibida $N$ - sidan boshlab chiqaring).

Misollar:

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

D. Sayohatchi Azimjon

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Azimjon Baytlandiya mamlakatiga sayohat qilmoqchi u mamlakatning barcha shaxarlariga borishni istaydi. Baytlandiyada jami $N$ ta shahar mavjud bo'lib shaxarlar 0 dan $N-1$ gacha raqamlangan va $N$ ta shaharni $K$ ta yo'llar bog'lab turadi. Azimjon Baytlandiya mamlakatining xaritasini ko'zdan kechirar ekan bir qiziqarli narsani sezib qoldi ya'ni $u_i$ va $v_i$ shaharlarni bog'lab turuvchi yo'l mavjud bo'lsa, $u_i$ dan $v_i$ shaharga borish mumkun lekin $v_i$ dan $u_i$ shaharga bu ikki shaharni bog’lab turuvchi yo’ldan qaytib bo’lmasligini sezdi. Endi Azimjon Baytlandiyaning barcha shaxarlariga sayohat qilishni istamaydi, u shunday bir shaxarni topishni hoxlaydiki u shaxardan istalgan bir shaxarga borish mumkun bo’lsin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida ikkita butun son $N, K (2 \le N+K \le 5*10^5)$ mos ravishda shaharlar soni va yo'llar soni. Kiyingi $K$ ta satirda $(u_i, v_i)$ $(0 \le u_i,v_i \le N-1)$ juftliklar $u_i$ shahardan $v_i$ shaharga borish mumkunligi.

Chiquvchi ma'lumotlar:

Azimjon Baytlandiyaning istalgan bir shaxriga borish mumkun bo’lgan shaxar raqamini chop eting. Agar bunday shaharlar bir nechta bo'lsa eng kichikgini, mavjud bo'lmasa -1 ni chop eting.

Misollar:

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

E. Minimal xarajat

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Azimjon yashab turgan qishloqga elektir tok o’tkazilmagan shu sabab bu qishloqqa elektir toki o’tkazilish rejalashtirildi. Hozirda faqatgina Azimjonning uyigagina tok yetib keldi. Bu qishloqda jami $N$ ta uy mavjud bo’lib(uylar 1 dan $N$ gacha raqamlangan) va Azimjon yashaydigan uy raqami 1 ga teng. Endi bu qishloqning mahallakomi kerakli tashkilotga murojat qildi har bir xonadonga elektir tokini Azimjon yashaydigan uydan kabel tortish kerak ekenligini va tortiladigan kabel uzunligi minimal bo’lish kerak ekenligini aytdi chunki mahallakom imkon qadar kam harajat qilishni istaydi. Tashkilot xodimlari kelib bu qishloqni yaxshilab o’rganib chiqdi ya’ni $u_i$ uydan $v_i$ uylarga kabel tortish mumkun ekanligini va ular o’rtasidagi masofalarni qog’ozga yozib chiqdi. Kabelning metiri $X$ so’m tursa, tashkilot xodimlari yozib olgan ma’lumotlariga asosan barcha uylarga kabel tortish uchun mahallakom qancha mablag’ sarflashini aniqlang.

Misol: 3 ta uy uchun chizma tasvirlangan. 1-chizmada barcha bog’lanishlar va ular o’rtasidagi masofa tasvirlangan. 2-chizmada barcha uylarga elektir toki yetib borgandan so’ng holati tasvirlangan bu yerda qizil chiziqlar kabel hisoblanadi.

Kiruvchi ma'lumotlar:

Kirish fayilining birinchi satirida uchta son $N, K, X (2 \le N, K, X \le 5*10^6)$ mos ravishda xonadonlar soni, ikki xonadonni bog’lanishlar soni va bir metir kabel narxi. Kiyingi $K$ ta satirda uchtadan son $u,v,w(1 \le u,v,w \le N)$ bular $u$-raqamli uydan $v$-raqamli uyga kabel tortish mumkunligi yoki teskarisi va bu ikki uy o’rtasidagi masofa $w$ ga teng.

Chiquvchi ma'lumotlar:

Chiqish fayilida mahallakom eng kamida qancha harajat qilishi kerak ekanligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 3 1 2 4 1 3 10 2 3 7	33
2	4 6 6 1 2 1 2 4 3 4 3 4 3 1 2 1 4 2 2 3 2	30

F. Connect the Pipes

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Connect the Pipes mobil o'yini haqida bilasizmi. Mening eng sevimli o'yinlarimdan biri hisoblangan bu oyin shartlari quyidagicha.

1. O'yin 4 X 4 o'lchamli jadvalda bo'lib o'tadi.
2. Jadvalda quvurlarning boshi va oxiri joylashgan katakchalar beriladi.
3. Sizning vazifangiz quvurlar bir birini kesib o'tmaydigan va 4x4 jadvalda bo'sh joy qolmaydigan qilib bir turdagi quvurlarni tutashtirishingiz lozim.

Bu masalada eng kopi bilan 4 ta turli hil quvurlar qatnashishi mumkin.

Kiruvchi ma'lumotlar:

$4 \times 4$ jadvalda kuchukcha, panjara, dollar, yulduzcha va nuqtalar qatnashishi mumkin . Bu yerda . bilan berilgan joylar bo'sh joylar, qolgan belgilar esa quvurlarning boshi va oxirlari hisoblanadi.

Chiquvchi ma'lumotlar:

Siz $4 \times 4$ jadvalda quvurlarning birlashtirilgan holatini chiqaring. Masala yechimga ega ekanligi kafolatlanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	#$@ .... .... #$@	#$@ #$@ #$@ #$@
2	.. #..# $..$ @..@	**** #### $$$$ @@@@
3	.#. @... .@# $..$	## @# @@*# $$$$

G. Snake game

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Eski telefonlarda "Iloncha" oyinini o'ynaganmisiz? Agar o'ynamagan bo'lsangiz hozir sizga o'yin qoidalarini tanishtiraman.
1. Dastlab iloncha 1 birlik uzunlikka ega bo'ladi.
2. Har bir yeyilgan olmachalar uchun uning uzunligi 1 birlikka oshib boradi.
3. Yangi qo'shiladigan ilonchaning bo'lagi, uning oxirgi bo'lagining harakat yo'nalishiga mos ravishta va shu bo'lak ketidan joy oladi.
4. Iloncha yo'lida to'siq bo'lmagan hollarda o'ngga, chapga, yuqoriga va pastga harakat qila oladi.
Iloncha o'yini $8 \times 8$ maydonida bo'ladi va iloncha $1 \times 1$ katakchadan o’yinni boshlaydi. Sizga mos ravishta ketma-ket paydo bo'luvchi N ta olmachalarning kordinatalari beriladi. Ilonchaning vasifangiz barcha olmachalarni yeb bitirish, ammo buning uchun ilonchaning boshi eng kam masofani bosib o’tishi kerak bo'ladi. (Ilonchaning tanasi va maydonning chetki qismlari to'siqlar hisoblanadi)

Kiruvchi ma'lumotlar:

Birinchi qatorda olmachalar soni $N$. Keyingi $N$ ta qatorda esa ketma-ket paydo bo'luvchi olmachalarning kordinatalari $x_i,y_i$. $(1 \le N \le 10, 1 \le x_i,y_i \le 8)$

Chiquvchi ma'lumotlar:

Barcha olmachalarni yeyish uchun ilonchaning boshi sarflaydigan eng qisqa yo'lning uzunligini toping. (masala yechimga ega ekanligi kafolatlanadi.)

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 8 8 8 8 1	21
2	2 8 1 2 1	15
3	2 2 1 8 1	7

H. Robocontest

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Robocontest.uz sayti hozirda dasturlash borasida contestlar o’tkaziladigan eng ommabop saytlardan biri. Robocontest saytida contestlar davomida 1-o’rinni egallash uchun bir nechta shartlar bor.

Siz boshqalarga qaraganda ko’proq masala ishlagan bo’lishingiz kerak.
Agar siz ishlagan masalalar soni boshqalar bilan bir xil bo’lsa, u holda siz masalalarni yechish uchun boshqa ishtirokchilarga qaraganda kamroq urinish qilishingiz kerak. Chunki har bir muvaffaqiyatsiz urinish uchun 20 daqiqa jarima bali beriladi.
Agar masalalar soni va urinishlar soni ham bir xil bo’lsa, u holda siz masalalarni boshqalarga qaraganda ertaroq yechgan bo’lishingiz kerak. Chunki har bir siz yechgan masala uchun sizga contest boshlanganidan keyin masala yechishga qancha daqiqa ketgan bo’lsa, shuncha daqaqa jarima bali beriladi.
Har bir birinchi bo’lib yechilgan masala uchun sizning jarima ballaringizda 10 ball olib tashlanadi.
Eng ko’p masala yechgan ishtirokchi g’olib bo’ladi. Agar masalalar soni teng bo’lib qolsa, eng kam jarima bali to’plagan ishtirokchi g’olib bo’ladi.

Bugungi contestga jami $n$ ta ishtirokchi qatnashdi, masalalar soni esa $m$ ta. Birinchi ishtirokchi m ta masalalarni $a_i$ vaqtlarda ishlaydi. Keyingi har bir j o’rindagi ishtirokchi $j-1$ o’rindagi ishtirokchidan masalalarni nos ravishta 5 daqiqa kech yechadi. Ishtirokchilarning barchasi contestdagi hamma masalalarni yechishadi va masalalar uchun bir hil urinishlar soni qilishadi.

Sizning vazifangiz berilgan contestda qaysi ishtirokchi 1-o’rinni olganini hisoblovchi dastur tuzishdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda contest ishtirokchilari soni $n$ va masalalar soni $m$ natural sonlari. Ikkinchi qatorda esa birinchi ishtirokchining $m$ ta masalani yechish uchun sarflagan vaqtlari $a_i$ (daqiqalarda). $(1 \le n,m \le 100; 0 \le a_i \le 239)$

Chiquvchi ma'lumotlar:

Contestda 1-o’rinni egallagan ishtirokchining tartib raqamini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 5 1 1 1 1 1	1

I. Number game

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dasturchilar Klubining a’zosi Azimjon sonlar bilan bo’gliq o’yinlarga juda qiziqadi. Bir kuni Azimjon do’sti Maqsud bilan ajoyib o’yin oynamoqchi bo’ldi. Azimjon o'zi o’ylagan a sonini Maqsud o’ylagan b soniga aylantirish uchun quyidagi amallarni bajarishini aytdi.

Sondan 1 ni olib tashlash.
2 dan k gacha bo'lgan har qanday butun x sonini tanlab, a sonidan (a mod x) ayirish.
(a mod x) operatsiyasi - a sonini x soniga bo'lganda qolgan qildiqni anglatadi.

Azimjon bir soniyada yuqoridagi amallardan birini bajaradi va u o’ylagan a soni ham o’zgarib boraveradi. U o’zining oylagan soni Maqsudning soniga aylanmaguncha, har soniyada o’zi istagan amallardan birini bajaraveradi. Azimjon juda aqilli dasturchi bo’lgani uchun, bu ishni eng kam vaqtda bajaradigan dastur yordamida amalga oshirmoqchi. Siz ham Azimjonga yordam berishga urinib ko’ring

E'tibor bering: ikkinchi amaldagi x raqamlari har safar bir-biridan mustaqil ravishda yangidan tanlanadi.

Kiruvchi ma'lumotlar:

Bitta qatorda Azimjon o’ylagan son, Maqsud o’ylagan son va $k$ soni. $(1 ≤ b ≤ a ≤ 10^{18} ; 2 ≤ k ≤ 15)$.

Chiquvchi ma'lumotlar:

Azimjon eng kamida necha soniya ichida o’z sonini Maqsud o’ylangan songa aylantirishini aniqlang.

Misollar:

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

J. Paxta terimi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Masala sharti to’qima voqeyliklarga asoslangan.
Bir paytlari PAXTA TERIMIga OTM talabalari ham yuborilardi. Ex o'sha damlar - boshqacha davrlar edi.
Ha mayli misolga qaytamiz. Hullas bo'lgan voqeani aytib beraman sizlarga.
Paxtaga olib ketish uchun 1 ta avtobus universitetga kelgan va u avtobus m ta 1-kurs va m ta 4-kurslarni olib ketishi kerak edi. Agar avtobusda joy yetarli bo'lmasa qolgan talabalarni 2-reys bilan, yana yetmasa 3-4-5- ... reyslar bilan olib ketishgan. Ammo o'sha paytlar TATUSFning 1-kurs va 4-kurs talabalari orasida biroz sovuqchilik bo'lgan ekan. Shuning uchun direktor avtobuschiga tayinlabdi :
Na universiyet yonida, na avtobusda va na paxta dalasida 4-kurslar soni 1-kurslar sonidan ziyod bo'lmasin, aks holda janjal chiqishi mumkin.
Avtobus haydovchisi direktorning gapida amal qilgan holda, eng kamida nechta reys bilan barcha talabalarni paxta dalasiga olib boradi.
Universitetdan paxta dalasiga va paxta dalasidan universitetga - bular alohida alohida Reyslar hisoblanadi.
Avtobusda har bir reysda kamida 1 ta talaba (farqi yo'q nechanchi kursligi) bo'lishi shart, aks holda avtobuschi zerikib qoladi.
Har bir reysdan keyin avtobus to'liq bo'shatiladi va qaytadan odam oladi.

1-test uchun izoh:
1-reys borish : 4-kurs 4-kurs
2-reys qaytish: 4-kurs
3-reys borish : 4-kurs 4-kurs
4-reys qaytish: 4-kurs
5-reys borish : 1-kurs 1-kurs
6-reys qaytish: 1-kurs 4-kurs
7-reys borish : 1-kurs 1-kurs
8-reys qaytish: 4-kurs
9-reys borish : 4-kurs 4-kurs
10-reys qaytish: 4-kurs
11-reys borish: 4-kurs 4-kurs

Kiruvchi ma'lumotlar:

Bitta qatorda m na n natural sonlari. $1 \le m , n \le 10^5$.
$m$ - har bir kursdagi talabalar soni.
$n$ - avtobusning sig'imi. (haydovchi hisobga olinmaydi).

Chiquvchi ma'lumotlar:

Minimal reyslar sonini chiqaring. Agar bu tariqa ularning hammasini olib borishning iloji bo'lmasa -1 ni chiqaring.

Misollar:

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

#	INPUT.TXT	OUTPUT.TXT
1	#$@ .... .... #$@	#$@ #$@ #$@ #$@
2	.. #..# $..$ @..@	**** #### $$$$ @@@@
3	.#. @... .@# $..$	## @# @@*# $$$$