A. Ichki burchaklar

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Sizga tekislikda joylashgan bitta to'rtburchakning koordinatalari beriladi. 

Siz ushbu to'rtburchakning ichki burchaklar yig'indisini topishingiz kerak.

Kiruvchi ma'lumotlar:

To'rtda qatorda to'rtburchak uchlarining koordinatalari kiritiladi. (1i4,1xi,yi100)(1\le i \le 4, 1\le x_i, y_i\le 100)

Chiquvchi ma'lumotlar:

Berilgan to'rtburchakning ichki burchaklari yig'indisini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
1 1
1 5
5 5
5 1
360

B. Sehrli Xazina Xaritasini Tiklash

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Qadim zamonlarda Mirzo Xoja ismli donishmand sulton o‘zining bebaho xazinasini cho‘lda yashirib, xarita chizib qoldirgan edi. Biroq, asrlar o‘tib, xaritaning bir qismi yo‘qolib ketdi va Mirzo Xojaning avlodlari xazinaning aniq joylashuvini aniqlashda qiyinchilikka duch kelishdi.

Xaritada to‘rt nuqta xazinani topish uchun kalit bo‘lib xizmat qiladi. Ushbu nuqtalar to‘g‘ri to‘rtburchak shaklida joylashgan bo‘lib, uning tomonlari koordinata o‘qlari bilan parallel bo‘lishi kerak. Mirzo Xojaning avlodlari uchta nuqtani topishga muvaffaq bo‘lishdi, lekin to‘rtinchi nuqtani aniqlashda muammo yuzaga keldi.

Sizga vazifa – ushbu yo‘qolgan nuqtani aniqlash va xazinani topishga yordam berish!

Kiruvchi ma'lumotlar:

Uchta satr beriladi, har birida ikkita butun son – xx va yy koordinatalari (1x,y1000)(1\le x, y\le 1000)
Bu nuqtalar xazina joylashgan to‘g‘ri to‘rtburchakning uchta burchagini bildiradi.

Chiquvchi ma'lumotlar:

Bitta satrda ikkita butun son – yo‘qolgan to‘rtinchi nuqtaning koordinatalari chiqarilsin.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
2 2
1 2
1 1
2 1

C. Crosswordagi sirli so‘z

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Azizbek crossword yechayotib o‘ziga qiziq bir mashg‘ulot topdi: crossworddagi eng kichik tartibda keladigan (leksikografik) so‘zni topish.

Crossword R × C o‘lchamli jadval sifatida tasvirlangan. Har bir katakda bir harf yoki bo‘shliq (#) mavjud.
So‘zlar faqat gorizontal (chapdan o‘ngga) yoki vertikal (yuqoridan pastga) yo‘nalishda ketma-ket joylashgan bo‘ladi.

Azizbekning qoidalari shunday:

  • U kamida 2 ta harfdan iborat bo‘lgan so‘zlarnigina so‘z deb hisoblaydi.
  • U eng kichik leksikografik tartibdagi so‘zni izlaydi.

Azizbekka ushbu so‘zni topishda yordam bering!

Kiruvchi ma'lumotlar:

Birinchi qatorda R va C butun sonlari (2 ≤ R, C ≤ 20) — crosswordning satr va ustunlar soni.

Keyingi R qatorda uzunligi C ta belgidan iborat matn beriladi. Har bir belgi kichik lotin harfi yoki # (bo‘sh joy) bo‘lishi mumkin.

Kiritish shunday bo‘ladiki, har doim kamida bitta yaroqli so‘z mavjud bo‘ladi.

Chiquvchi ma'lumotlar:

Bitta qatorda crossworddagi leksikografik eng kichik so‘z chiqarilsin.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
4 5
o#dnp
zji#f
v#d#a
e#a##
dida
2
13 13
deserve#sumup
r#t#a#dip#a#r
ironing#issue
f#o#n#yen#c#e
tape#t##ago#m
##snorkel#top
s##d#i#v#o##t
mar#polecat##
o#eau##n#firm
c#c#nip#m#d#i
khaki#edition
e#n#sae#s#l#c
ditch#restyle
ago

D. Korporatsiya

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Zarif katta korporatsiya bosh direktori bo‘ldi. Ushbu korporatsiya NN nafar xodimdan iborat bo‘lib, ular 11 dan NN gacha raqamlangan, bunda ii- ishchining yuvoshlik darajasi ii ga teng, Zarif esa 11-raqamga ega. Korporatsiya tuzilishi shundayki, Zarifdan tashqari har bir xodimning o‘z rahbari bor va biz ushbu xodimni o‘sha rahbarning yordamchisi deb ataymiz. Har bir rahbarga bir nechta yordamchi bo‘lishi mumkin, lekin ular ham o‘z navbatida o‘z rahbariga hisob beradi. Mirko esa piramidaning eng yuqori pog‘onasida turgan holda rahbariga ega emas, lekin uning ko‘plab yordamchilari bor.

Investorlar Zarifga topshiriq berganida, u uni eng yuvosh yordamchisiga uzatadi. Keyin bu yordamchi o‘zining eng yuvosh yordamchisiga topshiriqni uzatishni davom ettiradi va jarayon, yordamchisi bo‘lmagan (ya’ni “baxtsiz”) xodimga yetguncha davom etadi. Topshiriq bajarilgandan so'ng haq to‘lash sxemasi quyidagicha:

  • Topshiriqni bajaruvchi xodimga 11 tanga to‘lanadi,
  • uning rahbariga 22 tanga,
  • shu rahbarning rahbariga 33 tanga,
  • … va shu tariqa Zarifgacha davom etadi; Zarif esa ushbu ketma‑ketlikdagi odamlar soniga teng tanga oladi.

Topshiriq bajarib bo‘lingach, uni amalga oshirgan xodim tizim adolatsizligini anglab, ishidan voz kechadi. Keyingi topshiriqni bajarishda korporatsiyada bir kishi kam qolgan bo‘ladi, shuning uchun to‘lovlar ham ozroq bo‘lishi mumkin, lekin ish jarayoni davom etadi. Yuqoridagi jarayon (yangi topshiriq berish, uni bajarish, to‘lovlarni taqsimlash va bajaruvchi xodimning ketishi) Zarif yolg‘iz qolguncha takrorlanadi. Albatta, shu vaqtgacha Mirko katta boylik to‘plagan bo‘ladi, lekin u har bir xodim qancha pul ishlaganini ham bilishni xohlaydi.

Kiruvchi ma'lumotlar:

Birinchi qatorda ijobiy butun son N(2N2×105)N (2 \le N \le 2\times10^5) — korporatsiya xodimlari soni (Mirko ham qo‘shilgan).
Keyingi qatorda a2,a3,,aNa_2, a_3, \dots, a_N​ ijobiy butun sonlari berilgan, har biri uchun 1ai<i1 \le a_i < i,

bu yerda aia_iii-chi xodimning rahbari.

Chiquvchi ma'lumotlar:

Bitta qatorda NN ta sonni chop eting: ii-son korporatsiyadagi ii-xodim to‘plagan tanga miqdorini ifodalaydi.

Izoh:

2-test uchun izoh:

Zarif birinchi topshiriqni 2‑xodimga topshirdi, u esa uni 3‑xodimga uzatdi va 3‑xodim bajarib qo‘ydi. Shu uchun 3‑xodimga 1 tanga, 2‑xodimga 2 tanga, 1‑xodimga (Zarifga) 3 tanga to‘landi. Keyin 3‑xodim ishni tugatgach, iste’foga chiqdi.

Zarif ikkinchi topshiriqni yana 2‑xodimga berdi. 3‑xodim ketganligi sabab, 2‑xodim uni 4‑xodimga uzatdi, 4‑xodim esa 5‑xodimga topshiriqni yubordi va 5‑xodim bajarib berdi. Bu safar 5‑xodimga 1 tanga, 4‑xodimga 2 tanga, 2‑xodimga 3 tanga va 1‑xodimga 4 tanga to‘landi. So‘ng 5‑xodim ham iste’foga chiqdi.

Ushbu jarayon jami 5 ta topshiriq uchun takrorlandi.
Natijada, Zarifga 13 tanga, 2‑xodimga 8 tanga, 4‑xodimga 3 tanga, 3‑xodim va 5‑xodimga esa har biriga 1 tanga to‘landi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
3
1 1
5 1 1
2
5
1 2 2 4
13 8 1 3 1

E. Permutatsiya go'zalligi

Xotira: 128 MB, Vaqt: 1000 ms
Masala

“… Va xonim shunday dedi: ‘Men o‘n besh yildan beri ot minaman va otni teskari minish imkonsiz!’

Davlatbek esa Shohruhnning qo‘lidagi kartalarga qarab pichirlaydi: ‘Ha, bu kartalar teskari turibdi’. Qulaylik uchun Shohruh chapdan o‘ngga qarab ma’lum bir tartibda qo‘lida NN karta tutadi, ularning ustida 1,2,,N1,2,\dots,N raqamlari yozilgan. (Har bir raqamdan faqat bittadan.) U ixtiyoriy ravishda kartalarning ketma‑ketligini o‘zgartira olmaydi.

Davlatbek Shohruhga kartalarning ketma‑ket segmentini ko‘rsatadi (kamida bitta karta). Keyin Shohruh ko‘rsatilgan segmentdagi kartalarni “teskari” aylantirib, qayta joyiga qo‘yadi. (“Teskari aylantirish” deganda, o‘sha segmentdagi barcha kartalarni 180° ga burish, ya’ni birinchi kartani oxirgisi bilan, ikkinchisini ikkinchi oxirgisi bilan almashtirish tushuniladi.)

Davlatbek esa “o‘rinda qolgan” kartalarni juda yaxshi ko‘radi: agar kartadagi raqam uning hozirgi pozitsiyasi (chapdan boshlab) bilan bir xil bo‘lsa, bu karta o‘rinda qolgan hisoblanadi. Davlatbek xohlaydiki, aylantirishdan so‘ng o‘rinda qolgan kartalar soni maksimal bo‘lsin.

Berilgan kartalar tartibida qaysidir segmentni (ya’ni, boshi AA va oxiri BB) teskari aylantirish kerakki, aylantirishdan keyin o‘rinda qolgan kartalar soni maksimal bo‘lsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda ijobiy butun son N(1N500000)N (1 \le N \le 500\,000) — Shohruhning qo‘lidagi kartalar soni kiritiladi.
Ikkinchi qatorda NN ta butun son — chapdan o‘ngga qarab kartalardagi raqamlar permutatsiya ko‘rinishida, bitta bo‘sh joy bilan ajratilgan holatda beriladi.

Chiquvchi ma'lumotlar:

Bitta qatorda ikkita butun son AA va BB — teskari aylantirilishi lozim bo‘lgan segmentning boshidagi va oxiridagi kartalarning indeksini chop eting. Agar bir nechta yechim bo‘lsa, istalgan bittasini chiqarish mumkin.

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

F. Oqsoqol va Qishloq Yigitlari

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Bir zamonlar bir qishloqda oqsoqol yashardi. U juda dono edi va har qanday murakkab muammoni hal qila olardi. Barcha qishloq ahli unga maslahat so‘rab kelardi.

Kunlarning birida, qishloq katta muammoga duch keldi — tog‘ yo‘llari yomonlashib, odamlar shaharga bora olmay qoldi. Oqsoqol esa bu ishni yolg‘iz o‘zi uddalay olmasligini tushundi. Shuning uchun u qishloqning eng kuchli va epchil yigitlarini chaqirdi va ularga vazifa yukladi.

Har bir yo‘lni ochish uchun bir yigitni tayinlash kerak edi, lekin har bir yigitning o‘ziga yarasha imkoniyati bor edi: ba’zilari qiyin yo‘llarni yaxshi ochsa, boshqalari faqat oson yo‘llarni tozalashda yaxshi natija ko‘rsatardi.

Oqsoqol sizdan yordam so‘raydi: yo‘llarni ochish uchun yigitlarni qanday taqsimlash kerakki, natijada qishloqdan shaharga borish imkoniyati eng yuqori bo‘lsin?

Izoh: Barcha yo‘llarning muvaffaqiyatli ochilish ehtimoli — har bir yo‘lning ochilish ehtimollarining ko‘paytmasiga teng.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son N (1 ≤ N ≤ 20) — qishloq yigitlari va yo‘llar soni.
Keyingi N ta qatorning har birida N ta butun son (0 dan 100 gacha) bo‘lib, i-chi qatorning j-chi soni yigit i ning j-yo‘lni muvaffaqiyatli ochish ehtimoli (foizlarda) ekanini bildiradi.

Chiquvchi ma'lumotlar:

Barcha yo‘llar muvaffaqiyatli ochiladigan maksimal ehtimolni foizlarda aniqlang.

Natijada ruxsat etilgan xatolik ±0.01 doirasida bo‘lsa, to‘g‘ri javob sifatida qabul qilinadi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
1
0
0.000000000000
2
2
38 65
82 30
53.300000000000

G. Rost/Yolg'on o'yini

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Sizda NN ta karta mavjud. ii- karta ustiga aia_i soni yozilgan. Kartani joylashtirishga qarab, karta o'zida rost yoki yolg'on ma'lumot saqlashi mumkin. Har bir kartaning rost yoki yolg'on ma'lumot saqlashi quyidagiga ko'ra aniqlanadi:

  • ii- kartadan pastda kamida aia_i ta yolg'on karta mavjud.

Sizga KK butun soni beriladi. Kartalarni shunday joylashtiringki, tartiblashdan so'ng, karta to'plamida aynan KK ta karta yolg'on ma'lumot saqlasin.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son NN va KK berilgan (1N5105,0KN)(1 \le N \le 5\cdot10^5, 0 \le K \le N).
Keyingi NN qatorning har birida bitta butun son aia_i​ yozilgan (0ai5105)(0 \le a_i \le 5\cdot10^5) — bu ii-chi kartadagi ma'lumot.

Chiquvchi ma'lumotlar:

Agar masalani yechish mumkin bo‘lmasa, bitta 1−1 chiqaring. Aks holda, bitta qatorda NN ta kartaning raqamlarini bo‘yicha bo‘shliq bilan ajratib yozing — bu kartalarni yuqoridan pastga qarab qanday tartibda qo‘yish kerakligini ko‘rsatadi. Agar bir nechta yechim bo‘lsa, istalgan bittasini chiqarishingiz mumkin.

Izoh:

Ikkinchi test uchun izoh:
Soddalashtirish uchun kartalarni ularning da’volariga qarab rost/soxta deb belgileymiz.

  • Beshinchi kartaning ostida 0 ta soxta karta bor, shuning uchun u soxta.
  • To‘rtinchi kartaning ostida 1 ta soxta karta bor, shuning uchun u rost.
  • Uchinchi kartaning ostida 1 ta soxta karta bor, shuning uchun u rost.
  • Ikkinchi kartaning ostida 1 ta soxta karta bor, shuning uchun u soxta.
  • Birinchi kartaning ostida 2 ta soxta karta bor, shuning uchun u soxta.

Demak, jami 3 ta soxta karta mavjud.

Misollar:
# INPUT.TXT OUTPUT.TXT
1
4 2
1
2
2
3
2 3 1 2
2
5 3
2
1
3
0
3
3 3 0 1 2
3
6 4
0
2
5
2
0
1
-1
Kitob yaratilingan sana: 06-Jul-25 03:08