A. Matematik MOD

Xotira: 16 MB, Vaqt: 1000 ms

Masala

\(a\) mod \(b\) ning ikkilik sanoq sistemasidagi birlar soni topilsin.

Kiruvchi ma'lumotlar:

Ikkita butun son \(a\) va \(b\) sonlari beriladi. \((-10^{18} \le a, b \le 10^{18})\)

Chiquvchi ma'lumotlar:

Bitta butun son, masala yechimini chop eting. (Matematik mod ekanligini hisobga oling. )

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	17 3	1
2	21 34	3

B. Uchburchak

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga bor tayoqchalarning uzunliklaridan iborat bo’lgan to’plam beriladi. Siz shu tayoqchalarning ixtiyoriy uchtasidan foydalangan holda peremetri eng katta bo’lgan uchburchak yasashingiz kerak bo’ladi. Agar bunday uchburchak yasashning bir necha xil usuli bo’lsa, siz tanlagan tayoqchalarning uzunligi eng uzuni maksimal bo’lsin, agar buning ham bir necha xil usuli bo’lsa, siz tanlagan tayoqchalarning uzunligi eng qisqasi ham maksimal bo’lsing, agar buning ham bir necha xil usuli bo’lsa, siz ixtiyoriy birini tanlashingiz mumkin.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(3 ≤ N ≤ 50) tayoqchalar soni kiritiladi.

Ikkinchi satrda N ta [1, 10⁹] oralig’idagi butun son, har bir tayoqchaning uzunligi kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida agar yuqoridagi shartni qanoatlantiradigan uchburchak mavjud bo’lsa siz tanlagan tayoqchalarning uzunliklarini kamaymaydigan tartibda bitta qatorda bo’sh joy bilan ajratgan holda chop eting, agarda uchburchak yasashni imkoni bo’lmasa -1 ni chop eting.

Misollar:

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

C. Jimjimador sonlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Agarda N soni D xonali son bo’lsa M=N×N soni esa 2×D xonali son, yoki bo’lmasa 2×D-1 xonali son bo’ladi. M soninining oxiridan D xonasini R qiymat, qolgan qismini esa L qiymat deb qaraydigan bo’lsak va L+R=N shart qanoatlansa N soni Jimjimador son hisoblanadi.

Masalan:

N=9

M=N×N=9×9=81

L=8

R=1

L+R=N ya’ni 8+1=9 shart mos kelgani bois 9 soni ham jimjimador sonlardan biri hisoblanadi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining yagona satrida ikkita butun son, A va B(1 ≤ A ≤ B ≤ 10⁹) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida [A, B] butun sonlar oralig’ida joylashgan jimjimador sonlarning yig’indisini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 55	109
2	1 100	209

D. Kasalxona

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Baytlandiya davlatida jami N ta shahar bor va ular 1 dan N gacha sonlar bilan tartiblangan, hamda, har bir shaharda bittadan kasalxona mavjud, Baytlandiya davlatida shaharlarni ulab turuvchi jami M ta yo’l mavjud. To’satdan yuzaga kelgan tornado oqibatida Baytlandiya mamlakatidagi barcha kasalxonalar va shaharlarni bog’lab turguvchi yo’llar vayronaga aylandi. Baytlandiya prezidenti barcha shahar fuqarolari uchun zudlik bilan kasalxona muammosini hal qilishi kerak. Uning hisoblashi bo’yicha bitta kasalaxonani qayta qurish uchun A bitosum pul miqdori kerak bo’ladi, bitta yo’lni qayta tiklash uchun esa B bitosum pul miqdori kerak bo’ladi, yangi yo’l qurishning imkoni yo’q. Shahar fuqarosi uchun o’zi yashab turgan shaharda kasalxona mavjud bo’lsa yoki o’zi yashab turgan shahardan kasalxona mavjud bo’lgan qaysidir shaharga borish uchun yo’l mavjud bo’lsa(to’g’ridan to’g’ri bo’lishi shart emas, shaharma-shahar kezib ham borishi mumkin) kasalxonaga borishi mumkin bo’ladi. Mamlakatda iqtisodiy taqchillik bo’lgani bois prezidint bu muammoni imkon qadar kam pul sarflagan holda hal qilishi kerak, buning uchun unga yordam bering.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10) testlar soni kiritiladi.

Keyingi qatordan boshlab har bir test uchun quyidagi parametrlar kiritiladi:

Dastlabki satrda to’rtta butun son, N(1 ≤ N ≤ 10⁵), M(0 ≤ M ≤ min(10⁵, )), A, B(1 ≤ A, B ≤ 10⁵).

Keyingi satrdan boshlab M ta satrda u_i va v_i (1 ≤ u_i, v_i ≤ N, u_i ≠ v_i), mos ravishda u_i – shahar va v_i – shaharlar orasida ikki tomonlama yo’l mavjudligini anglatadi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda bittadan butun son, shaharlar fuqarolari uchun kasalxona muammosini hal qilishga eng kamida necha bitosum miqdorida pul kerakligini chop eting.

Misollar:

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

E. Hujum

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Baytlandiya aholisining barchasiga BitoBank o’z xizmatini ko’rsatib kelmoqda. BitoBank o’z foydalanuvchilariga uning hisob raqamiga hujum uyushtirilgan bo’lishi mumkinligi haqida xabar beruvchi tizim ishlab chiqdi. Bu tizim foydalanuvchining hisob raqamidan so’nggi D ta xarajatining medianasidan ikki barobar yoki undanda ko’p pul miqdori yechilayotgan vaqtda foydalanuvchiga uning hisob raqami hujumga uchragan bo’lishi mumkinligi haqida ogohlantiruvchi xabar jo’natadi, agarda xarajatlar miqdori hali D ta bo’lmagan bo’lsa hech qanday amal bajarilmaydi. Bizning MegaBoy ham xuddi shu bank xizmatidan foydalangan va u bankda ro’yxatdan o’tganidan buyon jami N marotaba o’z hisobidan mablag’ yechib olgan, va uning hisob raqami hech qachon hujumga uchramagan. Siz MegaBoy ga jami necha marotaba Bankdan hisob raqami hujumga uchragan bo’lishi mumkinligi haqida xabar kelganligini aniqlang.

Mediana – biror bir to’plamning medianasi to’plam elementlari kamaymaydigan yoki o’smaydigan qilib saralanganidan so’ng agar elementlar soni toq bo’lsa markaziy element qiymatiga, agar elementlar soni juft bo’lsa markaziy ikkita element o’rta arifmetik qiymatiga tengdir.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida ikkita butun son, N(1 ≤ N ≤ 2 × 10⁵) va D(1 ≤ D ≤ N) sonlari kiritiladi. Keyingi qatorda [0, 200] oralig’idagi N ta butun son, xarajatlar ro’yxati kiritiladi.

Chiquvchi ma'lumotlar:

MegaBoy ga necha marotaba hisob raqami hujumga uchragan bo’lishi mumkinligi haqidagi xabar kelganini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 10 20 30 40 50	1