A. Ichki burchaklar
Xotira: 32 MB, Vaqt: 1000 msSizga tekislikda joylashgan bitta to'rtburchakning koordinatalari beriladi.
Siz ushbu to'rtburchakning ichki burchaklar yig'indisini topishingiz kerak.
To'rtda qatorda to'rtburchak uchlarining koordinatalari kiritiladi.
Berilgan to'rtburchakning ichki burchaklari yig'indisini chop eting.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
1 1 1 5 5 5 5 1 |
360 |
B. Sehrli Xazina Xaritasini Tiklash
Xotira: 32 MB, Vaqt: 1000 msQadim 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!
Uchta satr beriladi, har birida ikkita butun son – va koordinatalari
Bu nuqtalar xazina joylashgan to‘g‘ri to‘rtburchakning uchta burchagini bildiradi.
Bitta satrda ikkita butun son – yo‘qolgan to‘rtinchi nuqtaning koordinatalari chiqarilsin.
# | INPUT.TXT | OUTPUT.TXT |
---|---|---|
1 |
2 2 1 2 1 1 |
2 1 |
C. Crosswordagi sirli so‘z
Xotira: 32 MB, Vaqt: 1000 msAzizbek 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!
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.
Bitta qatorda crossworddagi leksikografik eng kichik so‘z chiqarilsin.
# | 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 msZarif katta korporatsiya bosh direktori bo‘ldi. Ushbu korporatsiya nafar xodimdan iborat bo‘lib, ular dan gacha raqamlangan, bunda ishchining yuvoshlik darajasi ga teng, Zarif esa -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 tanga to‘lanadi,
- uning rahbariga tanga,
- shu rahbarning rahbariga 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.
Birinchi qatorda ijobiy butun son — korporatsiya xodimlari soni (Mirko ham qo‘shilgan).
Keyingi qatorda ijobiy butun sonlari berilgan, har biri uchun ,
bu yerda — -chi xodimning rahbari.
Bitta qatorda ta sonni chop eting: son korporatsiyadagi xodim to‘plagan tanga miqdorini ifodalaydi.
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.
# | 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“… 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 karta tutadi, ularning ustida 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 va oxiri ) teskari aylantirish kerakki, aylantirishdan keyin o‘rinda qolgan kartalar soni maksimal bo‘lsin.
Birinchi qatorda ijobiy butun son — Shohruhning qo‘lidagi kartalar soni kiritiladi.
Ikkinchi qatorda ta butun son — chapdan o‘ngga qarab kartalardagi raqamlar permutatsiya ko‘rinishida, bitta bo‘sh joy bilan ajratilgan holatda beriladi.
Bitta qatorda ikkita butun son va — teskari aylantirilishi lozim bo‘lgan segmentning boshidagi va oxiridagi kartalarning indeksini chop eting. Agar bir nechta yechim bo‘lsa, istalgan bittasini chiqarish mumkin.
# | 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 msBir 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.
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.
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.
# | 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 msSizda ta karta mavjud. karta ustiga 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:
- kartadan pastda kamida ta yolg'on karta mavjud.
Sizga butun soni beriladi. Kartalarni shunday joylashtiringki, tartiblashdan so'ng, karta to'plamida aynan ta karta yolg'on ma'lumot saqlasin.
Birinchi qatorda ikkita butun son va berilgan .
Keyingi qatorning har birida bitta butun son yozilgan — bu chi kartadagi ma'lumot.
Agar masalani yechish mumkin bo‘lmasa, bitta chiqaring. Aks holda, bitta qatorda 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.
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.
# | 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 |