A. Qizlar ICPC musobaqasida

Xotira: 16 MB, Vaqt: 1000 ms

Masala

O'zbekistonda IT ga bo'lgan e'tibor shunchalik kuchaydi-ki, xatto O'zbekiston Jahon tillari universitetidan ham talabalar ICPC musobaqasiga qatnashishni boshlashdi. Ammo muammo shundaki u yerda o'g'il bolalar soni qizlarga qaraganda bir qancha kam. Shu uchun o'g'il bolalar ishtirokini har bir jamoada ta'minlash maqsadida 1 jamoada 2 ta qiz bola va 1 ta o'g'il bola bo'lishi majburiy etib belgilandi. Yozgi almashinuv doirasida \(K\) nafar talaba chet elga o'qishga jo'natilishi kerak. K nafar talabani shunday jo'natingki maksimal sondagi jamoalar qurib bo'lsin.

Kiruvchi ma'lumotlar:

Kirish faylida 1 qatorda 3 ta nomanfiy butun son Q - qiz bolalar soni (\(0 \le Q \le 10^{15}\) ), B - o'g'il bolalar soni (\(0 \le B \le 10^{15}\) ) va K - chet elga jo'natiluvchi talabalar soni (\(0 \le K \le Q + B\)) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida K ta talaba jo'natilgandan so'ng maksimal nechta jamoa qurish mumkinligini chop eting.

Misollar:

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

B. Tub Summa

Xotira: 16 MB, Vaqt: 1000 ms

Masala

″Agar matematika go’zal bo’lmaganda edi, ehtimol matematikaning o’zi ham mavjud bo’lmasdi″.

O'zaro tub sonlar deb eng katta umumiy bo'luvchisi 1 ga teng bo'lgan ikki songa aytiladi.
Sizga n soni beriladi, agar N sonini ikkita 1 dan katta o'zaro tub sonlarning qo'shilmasi sifatida hosil qilish mumkin bo'lsa, shu ikki sonni chop eting. Agarda bu ish imkonsiz bo'lsa -1 chop eting.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida T\(\ \le 1000\)

Keyingi T ta qatorda N soni ( N\(\le 10^{18}\))

Chiquvchi ma'lumotlar:

Chiqish faylida berilgan topshiriqqa yechimni chop eting. Agar N soniga bir nechta javoblar bo'lsa xohlaganingizni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 9 10	4 5 3 7

C. Kitob o'qish

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Bir kuni Shohruh sovg'a sifatida o'zga sayyoraliklar haqidagi kitobni oldi va uni o'qishga qaror qildi. Ushbu kitob c sahifalardan iborat edi.

Birinchi kuni Shohruhning o'qish tezligi \(v_0\) sahifa, keyingi kunlari u oldingisidan ko'ra a sahifa ko'proq o'qiydi (birinchi kuni u \(v_0\) sahifalarni, ikkinchi - \(v_0 + a\), uchinchi kun - \(v_0 + 2a\) ... larni o'qiydi). Shu bilan birga, qanchalik harakat qilmasin, Shohruh kuniga \(v_1\) betdan ortiq o'qiy olmaydi.

Shuningdek, asar mazmunini yo‘qotmaslik uchun Shohruh har kuni oxirgi o'qigan l ta sahifalarini qayta o‘qishi kerak. Shohruh kitobning oxirgi sahifasini o‘qib bo'lishi bilanoq o‘qishni tugatadi.

Shohruh kitobni to'liq o'qib tugatishi uchun necha kun kerakligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining yagona qatorida boʻsh joydan ajratilgan beshta butun son mavjud: \(c, v_0, v_1, a\) va \(l\) \((1 ≤ c ≤ 1000, 0 ≤ l < v_0 ≤ v_1 ≤ 1000, 0 ≤ a ≤ 1000)\) — sahifalar soni, minimal o'qish tezligi, maksimal o'qish tezligi, har kungi varaqlar sonining o'sib borish farqi va Shohruh har kuni qayta o'qiydigan sahifalar soni.

Chiquvchi ma'lumotlar:

Chiqish faylida bitta butun sonni chop eting — Shohruh kitobni toʻliq oʻqib bo'lishi uchun kerak boʻladigan kunlar soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 6 10 5 4	1
2	15 4 12 4 1	3
3	30 2 100 0 0	15

D. Shohruh va mango daraxtlari

Xotira: 32 MB, Vaqt: 2000 ms

Masala

Bir kuni Shohruhning g'ayrioddiy tajribalari uchun mango mevalari zarur bo'lib qoldi.Shuning uchun u o'rmonga mango terish uchun yo'l oldi.

Tekislikdagi \((x, y)\) nuqtani ko'rib chiqaylik, x va y butun sonlar va 0 ≤ x, y bo'lsin. Bunday nuqtada daraxt o'sadi, unda x + y mango bor. Boshqa joylarda daraxtlar yo'q. Shohruh \(y = -{x \over m} + b\) tenglama bilan to'g'ri chiziq chizdi. Shohruh tomonlari koordinata o'qlariga parallel bo'lgan bitta to'rtburchakni tanlashi mumkin, uning barcha nuqtalari chiziq ostida yoki chiziqda yotadi va to'rtburchak ichidagi va chegarasidagi barcha daraxtlarni kesib, ulardagi barcha mangolarni yig'adi.

Shohruhga to'rtburchakni optimal tanlasa, olishi mumkin bo'lgan mangolarning maksimal sonini topishga yordam bering.

Shohruh ishonchi komilki, javob \(10^{18}\) dan oshmaydi. Unga ishonishingiz mumkin.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita butun son m va b sonlari kiritiladi \((1 \le m \le 1000, 1 \le b \le 10000)\).

Chiquvchi ma'lumotlar:

Chiqish faylida Shohruh kesgan daraxtlardan oladigan mangolarning maksimal sonini chop eting.

Izoh:

Yuqoridagi rasm ikkinchi misolga mos keladi. Optimal to'rtburchak qizil rangda ko'rsatilgan va 30 ta mangoni o'z ichiga oladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 6	273
2	1 5	30

E. Robolandiya poyezdlari

Xotira: 256 MB, Vaqt: 3000 ms

Masala

Robolandiya mamlakatida \(N\) ta shahar mavjud. Har bir shahar ketma-ket joylashgan va har biri tartib bilan raqamlangan. Bundan tashqari, ushbu shaharlar orasida qatnovchi \(M\) ta poyezd bor. \(i-\)poyezd \(L_i\) - \(R_i\) shaharlari orasida qatnaydi \((1 \le L_i \le R_i \le N)\).

Robolandiya qiroli ushbu poyezdlarga qiziqib qoldi va endi u vazirlaridan so'ramoqda: ″\(p_i\) va \(q_i\) shaharlari orasida qatnovchi nechta poyezd bor?″.

Sizning vazifangiz quyidagi shartni qanoatlantiruvchi poyezdlar sonini topishdir.

\(p_i \le L_j \le R_j \le q_i\).

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida uchta butun son - N, M, Q - shaharlar, poyezdlar va so'rovlar soni \((1 \le N \le 500, 1 \le M , Q \le 2*10^6)\).

Keyingi M ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(L_i\) va \(R_i\) mavjud.

Keyingi Q ta qatorning har birida bo'shliq bilan ajratilgan ikkita butun son - \(p_i\) va \(q_i\) mavjud.

Chiquvchi ma'lumotlar:

Chiqish faylining Q ta qatorida, har bir so'rov uchun ushbu oraliqda harakatlanuvchi poyezdlar sonini chop eting.

Misollar:

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