A. Yandex taxi

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Shohruh asosan avtobusdan foydalanadi. Lekin ba'zi payt Yandex taxiga murojaat qiladi, Bilamizki Yandex taxi da haydovchiga 1 dan 5 tagacha yulduzcha bilan baho qo'yish mumkin va Shohruh bu ishni doim amalga oshiradi. Bir kuni u ilova orqali necha marta safar qilgani va umumiy nechta yulduzcha qo'yganini ko'rib qoldi. Shohruh 5 ta yulduzcha qo'ygan taxi larning soni minimum va maksimum nechta bo'lishi mumkinligiga qiziqib qoldi.

Shohruhga u 5 ta yulduz qo'ygan taksilarning minimum va maksimum sonini hisoblashda yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita butun son N va M \((1 \le N, M \le 10^{18})\) - yulduzchalar va safarlar soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida ikkita sonni chop eting: minimum va maksimum son. Agar buning iloji bo'lmasa yoki hisoblashda xatolik mavjud bo'lsa \(“-1\ -1”\) (qo'shtirnoqlarsiz) ni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	14 4	0 2
2	100 1	-1 -1

B. Bomba

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Shohruh yaqinda R radiusli bomba ixtiro qildi. Katakcha bomba radiusida joylashgan deb ataladi, qachonki gorizontal va vertikal masofalar farqining minimali R dan oshmasa. Boshqacha aytganda, agar bomba (a, b) koordinatada, katakcha (c, d) koordinatada joylashgan va \(min(|a-c|, |b-d|) \le R\) bo'lsa, shu katakcha bomba radiusida joylashgan bo'ladi.

\(N*M\) maydon berilgan, har bir katakcha kamida bomba radiusida joylashishi uchun minimal nechta bomba kerak bo'ladi?

Kiruvchi ma'lumotlar:

Kirish faylining yagona qatorida 3 ta butun son - N, M\((1 \le N, M \le 1000)\) va R\((0 \le R \le 1000)\) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida kerak bo'ladigan minimal bombalar sonini chop eting.

Izoh:

1-test uchun koordinatalar:

(1,2)

2-test uchun koordinatalar:

(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)

(Aynan shu koordinatalar bo'lishi shart emas, muhimi minimal bo'lishi lozim).

Misollar:

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

C. Sayyohlar

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Robolandiyada M ta ketma-ket bog' mavjud va ular 1 dan M gacha raqamlangan. Bugun Robolandiyaga N ta sayyoh tashrif buyurgan va \(i-\)sayyoh \([A_i:B_i]\) oraliqdagi barcha bog'larni aylanib chiqadi. Agar ikki sayyoh bitta bog'da uchrashib qolishsa, ular do'stlashadi.

Har bir sayyoh uchun kun oxirida do'stlashishi mumkin bo'lgan sayyohlarning maksimal sonini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining 1-qatorida ikkita natural son - N va M \((1 \le N \le 2*10^5, 1 \le M \le 10^9)\) kiritiladi.

Keyingi N ta qatorning har birida ikkitadan butun son \(A_i\) va \(B_i \ (1 \le A \le B \le M)\) kiritiladi.

Chiquvchi ma'lumotlar:

Har bir sayyoh uchun alohida qatorda kun oxirida do'stlashishi mumkin bo'lgan sayyohlarning maksimal sonini chop eting.

Misollar:

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

D. Epik son

Xotira: 32 MB, Vaqt: 1500 ms

Masala

Shohruh epik sonlarni juda ham yaxshi ko'radi. Endi u N sonini epik usulda yaratmoqchi. N sonini epik usulda yaratishlar sonini hisoblang.

Agar sonni A+B*C ko'rinishida ifodalash mumkin bo'lsa, ushbu son epik deb ataladi. Bu yerda A, B, C - bir-biridan farq qiluvchi natural sonlardir.

Kiruvchi ma'lumotlar:

Kirish faylida \(N(1 \le N \le 2*10^6)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

N sonini epik usulda yaratishlar sonini hisoblang.

Izoh:

1 -test uchun:

(2, 1, 4), (2, 4, 1), (4, 1, 2), (4, 2, 1)

3-test uchun:

(1, 2, 3), (1, 3, 2)

(2, 1, 5), (2, 5, 1)

(3, 1, 4), (3, 4, 1)

(4, 1, 3), (4, 3, 1)

(5, 1, 2), (5, 2, 1)

Misollar:

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

E. Gullash

Xotira: 128 MB, Vaqt: 2000 ms

Masala

1 dan N gacha raqamlangan N ta vaza yonma-yon qo'yilgan. Eng chap va eng o'ng chekkalar cheksiz baland to'siq bilan berkitilgan. Vazalarning balandligi 1 dan N gacha oraliqda va istalgan ikkita vazaning balandligi bir biridan farq qiladi. Har bir vazaning ichida noyob gul bor. Gullarning balandligi 1 ga teng. Gul gullashi uchun u suv bilan to'liq qoplanishi kerak. Agar \(K-\) vaza ustidan suv quyishni boshlasak, gullarning gullash tartibini chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki qatorida N va K \((1\le K \le N \le 10^6)\) - vazalar soni va suv quyiladigan vaza raqami kiritiladi.

Keyingi qatorda N ta butun son - \(a_i (1 \le a_i \le N)\) kiritiladi. \(i-\)vazaning balandligi \(a_i\) ga teng,

\(1 < K < N\) uchun \(a_k < a_{k+1} \) yoki \(a_k < a_{k-1}\) bo'lishi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida gullash tartibini chop eting.

Misollar:

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