A. Kenguru

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Cho‘lda uchta kenguru o‘ynayapti. Ular to‘g‘ri chizig‘ida joylashgan va har biri turli koordinatada turibdi.

Bitta yurishda tashqi kengurulardan biri qolgan ikki kenguruning orasidagi bo‘sh joyga sakraydi. Hech qachon ikki kenguru bir xil pozitsiyada tura olmaydi.

Kengurular iloji boricha ko‘proq yurishlari uchun yordam bering.

Kiruvchi ma'lumotlar:

Uchta butun son $A, B, C$ beriladi — kengurularning boshlang‘ich pozitsiyalari.

$0 < A < B < C$

Chiquvchi ma'lumotlar:

Kengurular bajarishi mumkin bo‘lgan maksimal yurishlar sonini chiqaring.

Misollar:

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

B. Uch "mushketyor"

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Azizbek, Davlatbek va Shohruh dasturlash klubiga a’zo bo‘lishni xohlashdi. Biroq ular bu klubga kirish uchun imtihon topshirish kerakligini bilishmas edi.

Imtihon $N$ ta savoldan iborat, har bir savol uchun uchta javob varianti mavjud: A, B yoki C.

Afsuski, ular hattoki python va c++ ni farqlasholmagani uchun javoblarni taxmin qilishga qaror qilishdi.

Har birining o‘ziga xos strategiyasi bor:

Azizbek quyidagi ketma-ketlikni eng yaxshisi deb hisoblaydi:
$A, B, C, A, B, C, A, B, C, A, B, C ...$
Davlatbek esa quyidagicha deb o‘ylaydi:
$B, A, B, C, B, A, B, C, B, A, B, C ...$
Shohruh esa ulardan kulib, quyidagi ketma-ketlikni tanlaydi:
$C, C, A, A, B, B, C, C, A, A, B, B ...$

Sizga imtihondagi to'g'ri javoblar beriladi. Siz esa kim eng ko'p to'g'ri javob topganini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son $N$ — imtihondagi savollar soni $(1 \leq N \leq 100)$ kiritiladi.

Ikkinchi qatorda uzunligi $N$ bo‘lgan satr — har bir savolga mos to‘g‘ri javoblar ketma-ketligi beriladi, satr A, B yoki C belgilaridan iborat.

Chiquvchi ma'lumotlar:

Birinchi qatorda $M$ — bolalar ichidan eng ko‘p to‘g‘ri javob berganining to‘g‘ri javoblari soni.

Keyingi qatorda, alifbo tartibida, to‘g‘ri javoblar soni $M$ ga teng bo‘lgan bolalarning ismlarini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 BAACC	3 Davlatbek
2	9 AAAABBBBB	4 Azizbek Davlatbek Shohruh

C. Qadimgi Rim qoldiqlari

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Arxeologlar yaqinda qadimgi Rim me’morchiligiga oid yodgorliklarni topishdi. Bu joy $R \times C$ o‘lchamdagi katakli jadval (grid) ko‘rinishida modellashtirilgan.

Har bir katakda bino qoldiqlari topilgan yoki bu katak har doim bo‘sh bo‘lganini aniqlashgan.

Artefaktlarni batafsil o‘rganganlaridan so‘ng, bu joyda turli davrlarga oid ikkita bino qoldiqlari bor degan xulosaga kelishdi. Har ikkala bino kvadrat shaklida bo‘lgan.

Binolar turli davrlarda qurilgani sababli, bu binolar bir-biri bilan qisman ustma-ust tushgan bo'lishi mumkin.

Sizning vazifangiz: har bir binoning yuqori chap burchagining koordinatalari va kvadratning tomonlari uzunligini aniqlash.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son $R$ va $C$ — maydonning o‘lchami $(1≤R, C≤100)$ .

Keyingi $R$ ta qatorda har birida uzunligi $C$ bo‘lgan satr beriladi. Har bir belgining ma’nosi:

'.' — bu katak doimo bo‘sh bo‘lgan;
'x' — bu katakda bino qoldiqlari topilgan.

Chiquvchi ma'lumotlar:

Ikkita qatorda har bino uchun: binoning yuqori chap burchagi koordinatasi va binoning tomoni uzunligini chop eting.

Test ma’lumotlari har doim yechim mavjud bo‘lishini kafolatlaydi. Bir nechta yechim mavjud bo'lsa istalganini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 3 xx. xxx ...	1 1 2 2 3 1
2	4 6 xx.... xx.xxx ...xxx ...xxx	1 1 2 2 4 3
3	5 5 ..... xxx.. xxxx. xxxx. .xxx.	2 1 3 3 2 3

D. Asilbekning tipratikani

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Asilbek o‘zining tomorqasida juda g‘alati o‘yin taxtasini topdi. Ajablanarlisi shundaki, bu taxta $R \times C$ o‘lchamdagi kvadrat kataklardan iborat ekan.
Qatorlar yuqoridan pastga $0$ dan $R−1$ gacha, ustunlar esa chapdan o‘ngga $0$ dan $C−1$ gacha raqamlangan.

Bu taxtani g‘alati qiladigan jihat — bu kataklarning bo‘yalish tartibi. Har bir katak quyidagi qoidalarga ko‘ra oq yoki kulrang bo‘yalgan:

Agar qator raqamini $x$ va ustun raqamini $y$ deb olsak, $x \ \& \ y ≥ 1$ bo'lsa, ushbu katak oq rangga bo'yalgan. Bu yerda $\&$ - bitwise and operatori.
Masalan, $(4,5)$ katagi — oq rangda bo‘ladi.
Aks holda katak kulrang bo‘ladi.
Masalan, $(2,5)$ katagi — kulrang rangda bo‘ladi.

Quyidagi rasmda $10 \times 10$ o‘lchamdagi taxta ko‘rsatilgan.

Asilbekning tipratikani ushbu g‘alati taxtada yurishni juda yoqtiradi va yurish uslubi ham noodatiy.

Tipratikan o‘z yurishini $(0,0)$ katakdan boshlaydi va yuqoridagi rasmda ko‘rsatilgandek zig-zag tartibda harakat qiladi.

Tipratikan harakatlanayotganda Asilbek, tipratikan bosib o‘tgan kulrang kataklar sonini sanaydi.

Tipratikan $K$ ta katakdan o‘tganidan so‘ng charchaydi va uxlab qoladi. Asilbek ham, kulrang kataklar sonini hisoblashga ulgurganidan hursand bo‘lib, uxlashga yotadi.

Sizning vazifangiz — taxta o‘lchami va $K$ qiymati ma’lum bo‘lsa, tipratikan o‘tgan kulrang kataklar sonini hisoblab beruvchi dastur tuzish.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son $R$ va $C$ $(1 \leq R, C \leq 1\,000\,000)$ — taxtaning o‘lchamlari beriladi.

Ikkinchi qatorda bitta butun son $K$ $(1 \leq K \leq R \times C)$ — tipratikan bosib o‘tgan kataklar soni beriladi.

Chiquvchi ma'lumotlar:

Bitta butun son chiqaring — tipratikan bosib o‘tgan kulrang kataklar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 10 6	5
2	3 5 11	8
3	10 10 100	51

E. Tunnellar saltanati

Xotira: 128 MB, Vaqt: 2000 ms

Masala

Ko'rsichqonlar — tartibni yaxshi ko‘radigan va mehnatkash hayvonlardir. Bizning ko'rsichqon esa o‘z yer osti uyini juda tartibli holatda saqlashni yoqtiradi, shunda u yerda yashovchi har bir kishi kerakli narsani oson topa oladi.

Shu maqsadda, ko'rsichqon xonalarni shunday tunnellar bilan bog‘ladiki, har qanday ikkita xona orasida faqat bitta yagona yo‘l mavjud.

Ikki xona orasidagi masofa — ular orasidagi yo‘lda o‘tilgan tunnel soni sifatida aniqlanadi.

Shuncha mehnatga qaramay, ko'rsichqonning ba’zi mehmonlari ayrim xonalar orasida yurish juda uzoq vaqt olishini aytib shikoyat qilmoqda.

Shuning uchun ko'rsichqon uyini qayta qurishga qaror qildi:

bir tunnelni yopadi,
yangi bir tunnelni ochadi,
shunda ikki eng uzoq joylashgan xona orasidagi masofa imkon qadar kichik bo‘ladi.

Barcha xonalar hali ham bir-biriga bog‘langan bo‘lib qolishi kerak (ya’ni, har bir xonadan har bir boshqa xonaga yetib borish mumkin bo‘lishi kerak).

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son $N (1 \le N \le 3 \times 10^5)$ — xonalar soni beriladi. Xonalar $1$ dan $N$ gacha raqamlangan.

Keyingi $N−1$ ta qatorda har birida ikkita butun son beriladi — bu sonlar o‘zaro tunnel bilan bog‘langan xonalar raqami.

Chiquvchi ma'lumotlar:

Uchta qator chiqaring:

Eng uzoq joylashgan xonalar orasidagi yangi masofa (rekonstruksiyadan so‘ng).
Yopilishi kerak bo‘lgan tunnelni bildiruvchi ikkita xona raqami.
Yangi ochilishi kerak bo‘lgan tunnelni bildiruvchi ikkita xona raqami.

Eslatma: Yechim yagona bo‘lmasligi mumkin. Har qanday rekonstruksiya rejasi qabul qilinadi, agar u masofani minimal qilsa.

Misollar:

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