A. Nolsiz son

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Tarkibida $0$ (nol) raqami ishtirok etmagan $N$ - natural sonni aniqlang.

Kiruvchi ma'lumotlar:

Bitta butun son, $N (1 \le N \le 10^{18})$ soni kiritiladi.

Chiquvchi ma'lumotlar:

Tarkibida $0$ (nol) raqami ishtirok etmagan $N$ - natural sonni chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	9	9
2	10	11
3	89	98
4	12345	17836

B. Palindrom massiv

Xotira: 32 MB, Vaqt: 1000 ms

Masala

M ta elementdan iborat $A$ massiv palindrom massiv deyiladi, qachonki $0 \le i < M$ bo'lgan ixtiyoriy $i$ uchun $A_i = A_{M-1-i}$ shart bajarilsa.

Sizga $N$ ta sondan iborat $A$ massiv berilgan, siz shu massivni palindrom massivga aylantirishingiz kerak. Buning uchun siz bir amalda massivdan ixtiyoriy qo'shni bo'lgan ikki sonni o'chirib, ularning yig'indisini shu sonlarning o'rniga yozishingiz mumkin, bunda sizning massivingiz uzunliga bittaga kamayadi.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, $N(1 \le N \le 10^6)$ soni kiritiladi. Ikkinchi satrda $N$ ta butun son, $A (1 \le A \le 10^9)$ massiv elementlari bo'sh joy bilan ajratilgan holda kiritiladi.

Chiquvchi ma'lumotlar:

Berilgan $A$ massivni palindrom massiv qilish uchun yuqoridagi amaldan eng kamida necha marotaba foydalanish kerakligini aniqlang!

Misollar:

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

C. Tug'ilgan kun sovg'asi va so'rovlar

Xotira: 256 MB, Vaqt: 5000 ms

Masala

Bugun Mirzohidning bugun tug‘ilgan kuni, va uning yaqin do‘sti Jamshid unga maxsus sovg‘a tayyorlagan. Jamshid Mirzohidga katta qiziqarli topshiriq berdi: N ta tabiiy sonlardan iborat massiv va Q ta savol. U shunday dedi:

"Mirzohid, agar sen ushbu savollarga to‘g‘ri javob bersang, tug‘ilgan kuning uchun tayyorlagan sovg‘amni olasan! Savollar oddiy: har bir savolda men bir intervalni ko‘rsataman, va sen shu intervalda aynan ikki marta uchraydigan turli sonlarning sonini topishing kerak."

Jamshid kulib qo‘shib qo‘ydi: "Bu unchalik qiyin emas, ammo sovg‘ani olmoqchi bo‘lsang, savollarning hammasini hal qilishing kerak!"

Mirzohidning qiziqishi oshdi va u topshiriqni bajarishga kirishdi. Endi u Jamshidning barcha savollariga javob berib, sovg‘ani qo‘lga kiritishi kerak. Bu ish juda ko'p vaqt olishi mumkin va u bayramni nishonlashi kerak. Shu sababli bu vazifani sizga topshirdi.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi satrida $N$ va $Q$ - massiv uzunligi va so'rovlar soni kiritiladi.

Keyingi satrda $N$ da butun son - $A$ massiv elementlari kiritiladi.

Keyingi $Q$ ta satrning har birida ikkitadan butun son $L_i$ va $R_i$ kiritiladi.

$1 \le N, Q \le 5 \times 10^5$

$1 \le A_i \le 10^9$

$1 \le L_i \le R_i \le N$

Chiquvchi ma'lumotlar:

Har bir so'rov uchun yangi satrda shu oraliqdagi aynan ikki marta uchragan elementlar sonini chop eting.

Misollar:

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

D. Navbat

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Siz dasturlash bo'yicha musobaqada ishtirok etish uchun navbatda turibsiz. Sizga ma'lumki navbatda siz bilan birgalikda jami $N$ ta ishtirokchi bor. Shu ishtirokchilardan kamida $X$ tasi sizdan oldinda, hamda ko'pi bilan $Y$ tasi sizdan orqada turibdi. Shu ma'lumotlardan foydalanib siz navbatning nechta turli xil o'rinlarida bo'lishingiz mumkinligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida bo'sh joy bilan ajratilgan holda uchta butun son, $N(1 \le N \le 10^9)$ , $X(0 \le X < N)$ hamda $Y(0 \le Y < N)$ sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Berilgan ma'lumotlarga asoslanib siz navbatning nechta turli xil o'rinlarida bo'lishingiz mumkinligini chop eting.

Izoh:

1-testda siz [3, 4, 5] o'rinlarda bo'lishingiz mumkin

Misollar:

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

E. Hamma yo'llar Toshkentga

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Alisher sayohatga chiqib, O‘zbekistonning barcha yirik shaharlarini o‘rganishga qaror qildi. Uning qo‘lida xarita bor edi, unda shaharlar orasidagi barcha yo‘nalgan yo‘llar ko‘rsatilgan, lekin shaharlarning nomlari emas, faqat raqamlari yozilgan edi. Shuningdek, shaharlar orasida bir necha yo‘nalgan yo‘l bo‘lishi ham mumkin edi. Xaritada shunday ma’lumot bor ediki, barcha shaharlar Toshkent bilan bog‘langan, lekin Toshkentdan boshqa shaharlarga yo‘l yo‘q edi. Alisherga Toshkent shahrining raqamini topishda yordam bering yoki agar bunday shahar yo‘q bo‘lsa, -1 raqamini chiqaring.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida $n$ va $m$ - shaharlar soni va yo'llar soni kiritiladi.

Keyingi $m$ ta satrning har birida ikkitadan butun son $u$ va $v$ sonlari kiritiladi. Bu $u$ shahardan v shaharga boruvchi yo'l mavjud ekanligini anglatadi.

$2 \le n \le 10^5$

$1 \le m \le 2 \times 10^5$

$1 \le u, v \le n$

Chiquvchi ma'lumotlar:

Toshkent shahrining raqamini chop eting, agar mavjud bo'lmasa -1 ni chop eting.

Misollar:

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

F. Parvoz vaqti

Xotira: 32 MB, Vaqt: 1000 ms

Masala

ICPC ishtirokchilari tayyorgarlik uchun chet elga yo‘l olishdi. Ular har daqiqadan unumli foydalanishni xohlagani uchun samolyotda uchish davomida masalalar yechmoqchi. Ularda masalalar ustida ishlash uchun eng kamida qancha vaqt borligini aniqlang.

Kiruvchi ma'lumotlar:

Kirishning dastlabki satrida samolyotning uchish vaqti $hh:mm$ ko'rinishida kiritiladi.

Keyingi satrda qo'nish vaqti $hh:mm$ formatida kiritiladi.

Uchinchi satrda mintaqalar orasidagi soatlar farqi kiritiladi. Farq -12 dan +12 gacha bo'lishi mumkin.

$00 \le hh \le 23$

$00 \le mm \le 59$

Chiquvchi ma'lumotlar:

Minimum parvoz vaqtini $hh:mm$ formatida chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	12:00 13:00 0	01:00
2	23:00 01:00 0	02:00
3	01:50 12:50 +1	10:00

G. Bog'bon

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Bog'bon o'z bog'idan N kg olma terib oldi. Endi bog'bon ularni yashikka solishi kerak. Bitta yashikka M kg olma sig'adi. Bog'bonga nechta yashik kerak?

Kiruvchi ma'lumotlar:

Kirish qismi yagona satrda $N$ va $M$ butun sonlari kiritiladi. $1\le N, M \le 10^5$

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	25 4	7
2	13 14	1