A. Uchburchak

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Sizga uchburchakning 3 ta tomoni \(A, B, C\) berilgan. Berilgan uchburchak to'g'ri burchakli uchburchak ekanligini aniqlang.

Uchburchak to'g'ri burchakli uchburchak deyiladi, agar uchburchakning ichki burchaklaridan biri \(90^0\) ga teng bo'lsa.

Kiruvchi ma'lumotlar:

Kirish faylida 3 ta butun son \(A, B, C\) berilgan.

\(1 \le A, B, C \le 100\)

Chiquvchi ma'lumotlar:

Agar berilgan uchburchak to'g'ri burchakli bo'lsa "YES", aks holatda "NO" ni chop eting.

Misollar:

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

B. O'n uch

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Bugungi Shohruh har xil ertaklarni yoqtirmaydi, sizga 1 dan \(N\) gacha sonlardan iborat tartiblangan massiv berilgan, siz shu massivdan shunday \(subset\) olingki undagi hech qaysi \(2\) ta sonning yig'indisi \(13\) ga qoldiqsiz \(bo'linmasin\). Sizning vazifangiz uzunligi eng katta bo'lgan \(subset\) ni topish va uning uzunligini ekranga chiqarish.

Subset, bu berilgan massivdagi ba’zi elementlarni tanlab olingan to‘plam. Unda faqat asl to‘plamda bor elementlar bo‘ladi, tartib va yonma yonlik muhim emas.

Kiruvchi ma'lumotlar:

Yagona qatorda \(N\ \ (1 \le N \le 10 ^ {18})\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini ekranga chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	37	19
2	78	37
3	88595901811831377	40890416220845253

C. Bog'bon

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Bahor kelishi bilan bog‘bon o‘z bog‘ida olma daraxti ko‘chatlarini parvarish qilishni boshladi. Qulaylik uchun bog‘ni \(1\) dan \(N\) gacha raqamlangan uzun chiziq deb qaraylik. Har bir \(i\) nuqtada bitta ko‘chat bor.

Boshlanishida barcha ko‘chatlarning bo‘yi \(0\) sm.

Bog‘bon har kuni bitta sug‘orish ishini bajaradi. Bunda u istalgan \([L,R]\) oraliqni tanlaydi \(1≤L≤R≤N)\) va shu oraliqdagi barcha ko‘chatlarning bo‘yini \(1\) sm ga o'sadi.

Bog‘bon \(i-\) ko‘chatning yakuniy bo‘yi aynan \(h_i\) sm bo‘lishini xohlaydi. Sizning vazifangiz, barcha ko‘chatlarni aynan kerakli balandlikka yetkazish uchun zarur bo‘lgan eng kam kunlar sonini topish.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(N (1 \le N \le 10^5)\) - bog'dagi daraxtlar soni kiritiladi.

Keyingi qatorda \(N\) ta butun son \(h_i (0 \le h_i \le 10^9)\) - har bir daraxtning bog'bon xohlagan balandligi kiritiladi.

Chiquvchi ma'lumotlar:

Bitta butun son chiqaring, barcha ko‘chatlarni \(h_i\) balandliklarga yetkazish uchun kerak bo‘ladigan eng kam sug‘orish kunlari soni.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 5 3 6 0 3 4	12

D. Formula 1

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Shohruh — mashhur Formula1 muhandisi va strateg! Bugun u va uning zukko shogirdi xalqaro ultrazamonaviy Formula1 musobaqasida qatnashmoqda. Musobaqa \(N\) ta aylana (lap)dan iborat. Shohruh shogirdi uchun \(M\) turdagi maxsus shinalarni olib kelgan, har birining o‘ziga xos kuchli va zaif tomonlari bor. Qiziq tomoni, yangi shina bilan aylana boshlash tezroq bo‘ladi, lekin har bir keyingi aylana o‘tgan sayin shina yemirilib boradi va vaqt ortadi. \(i\)-tur shina uchun 1-aylana \(t_i\) soniya, 2-aylana \(t_i + k_i\) soniya, 3-aylana \(t_i + 2\times k_i\) soniya va \(s\)-chi aylana uchun \(t_i + k_i \times (s - 1)\) soniya ketadi. Har bir aylanadan so‘ng shina almashtirishingiz mumkin, lekin shina almashtirish (pit-stop) to‘liq \(X\) soniya vaqt oladi.

Shohruh shogirdini eng tez finishga yetkazish uchun bosh qotiryapti. Siz ham eng qisqa va aniq strategiyani topa olasizmi? Minimal umumiy vaqtni hisoblang, shu vaqt ichida mashina finishga yetadi.

Eslatma: Har bir aylana(lap) dan keyin o'zingizda bor bo'lgan \(M\) xil turdagi shinalardan istalgan birini olishingiz mumkin.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N,\; M,\; X\) beriladi.

Keyingi \(M\) ta qatorda \(t_i,\; k_i\) sonlari kiritiladi.

\(1 \leq N,\; M \leq 5 \times 10^3\)
\(1 \leq t_i,\; k_i,\; X \leq 10^9\)

Chiquvchi ma'lumotlar:

Shohruhning o'quvchisi minimal necha sekundda poygani tugatishini ekranga chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2 17 10 3 5 100	5
2	2 10 13 16 14 11 3 11 7 3 2 18 9 9 19 16 5 6 1 9 16 20 13	8

E. Guruh nazorati

Xotira: 256 MB, Vaqt: 1000 ms

Masala

RoboContest Telegram guruhida taqiqlangan so‘zlar ro‘yxati mavjud. Moderator bot xabarlarni tekshiradi.

Har bir foydalanuvchi uchun quyidagi qoida amal qiladi.
Agar foydalanuvchining barcha xabarlarida taqiqlangan so‘zlarning umumiy substring uchrashlari soni \(K\) yoki undan ko‘p bo‘lsa, u foydalanuvchi bloklanadi.

Substring uchrashni sanash qoidasi
Taqiqlangan so‘z \(s\) va matn \(t\) berilgan bo‘lsin. Agar \(t\) ning \(i\) pozitsiyasidan boshlab \(|s|\) ta belgi aynan \(s\) ga teng bo‘lsa, bu bitta uchrash hisoblanadi. Uchrashlar ustma ust tushishi mumkin va har biri alohida hisoblanadi.
Foydalanuvchi uchun umumiy uchrashlar soni uning barcha xabarlaridagi barcha taqiqlangan so‘zlar uchrashlari yig‘indisiga teng. Turli xabarlar orasidan substring “o‘tib ketmaydi”, ya’ni har bir xabar alohida tekshiriladi va so‘ngra yig‘iladi.

Sizga guruhdagi xabarlar va taqiqlangan so‘zlar ro‘yxati beriladi. Qaysi foydalanuvchilar bloklanishini aniqlang.

Kiruvchi ma'lumotlar:

irinchi qatorda uchta butun son \(N, M, K\) beriladi \((1 \le N \le 10^3, 1 \le M \le 10^5, 1 \le K \le 10^5)\).
Keyingi \(N\) qatorda xabarlar quyidagi formatda beriladi:
@username: message

Bu yerda:
username faqat kichik lotin harflaridan iborat.
message faqat kichik lotin harflaridan iborat.

Keyingi \(M\) qatorda \(M\) ta taqiqlangan so‘z \(s_1, s_2, ..., s_M\) beriladi. Ularning barchasi kichik lotin harflaridan iborat va o‘zaro turlicha.

Qo‘shimcha cheklovlar:
username uzunligi 5 dan 20 gacha.
Turli foydalanuvchilarning username lari turlicha.
Bitta foydalanuvchi bir nechta xabar yuborishi mumkin.
Har bir message uzunligi 1 dan 500 gacha.
Har bir taqiqlangan so‘z uzunligi 1 dan 500 gacha.
Barcha taqiqlangan so‘zlar uzunliklari yig‘indisi \(5 \times 10^5\) dan oshmaydi.

Chiquvchi ma'lumotlar:

Bloklanadigan foydalanuvchilarni leksikografik tartibda chiqaring, har birini alohida qatorda, @ belgisi bilan birga.
Har bir username ko‘pi bilan bir marta chiqarilsin.
Agar hech kim bloklanmasa, “No blocks” chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 4 2 @behruz: ratedcontestplease @ahror: ratedcontestplease @rshohruh: spamqilmanglariltimos @behruz: spamspamratedcontest @anusrat: bugunemas @shokir: iltimosratedcontestqoyilar @rshohruh: gptbilanishlaysizmi @shokir: chatgptgeminibilanishlayman @anusrat: suniyintellektmumkinmas @abdulla: ratedcontestplease rated gpt gemini contest	@abdulla @ahror @behruz @shokir
2	2 1 3 @user: badbad @user: bad bad	@user
3	3 2 1 @useraa: hello @userbb: world @useraa: abcdef zzz qqq	No blocks

#

INPUT.TXT

OUTPUT.TXT

1

10 4 2
@behruz: ratedcontestplease
@ahror: ratedcontestplease
@rshohruh: spamqilmanglariltimos
@behruz: spamspamratedcontest
@anusrat: bugunemas
@shokir: iltimosratedcontestqoyilar
@rshohruh: gptbilanishlaysizmi
@shokir: chatgptgeminibilanishlayman
@anusrat: suniyintellektmumkinmas
@abdulla: ratedcontestplease
rated
gpt
gemini
contest

@abdulla
@ahror
@behruz
@shokir

2

2 1 3
@user: badbad
@user: bad
bad

@user

3

3 2 1
@useraa: hello
@userbb: world
@useraa: abcdef
zzz
qqq

No blocks

F. Yana bir LIS topshirig'i

Xotira: 256 MB, Vaqt: 1000 ms

Masala

Azizbek yaqinda eng uzun o‘suvchi qism ketma-ketlik (Longest Increasing Subsequence, LIS) mavzusini o‘rgandi.

Butun sonlardan iborat \(A = (a_1, a_2, …, a_k)\) massiv berilgan bo‘lsin. \(A\) ning qism ketma-ketligi deb \(A\) dan ayrim elementlarni o‘chirib tashlash (hech birini o‘chirmaslik ham, hammasini o‘chirish ham mumkin) orqali, qolgan elementlarni dastlabki tartibda qoldirib hosil qilingan ketma-ketlikka aytiladi.

Agar ushbu qism ketma-ketlik elementlari chapdan o‘ngga qat’iy o‘suvchi bo‘lsa \((b_i < b_{i+1}, \ 1 \le i < n)\), u A ning o‘suvchi qism ketma-ketligi deyiladi. Elementlari soni eng ko‘p bo‘lgan o‘suvchi qism ketma-ketlik \(A\) ning eng uzun o‘suvchi qism ketma-ketligi hisoblanadi.

Masalan, (2,4,5,6) va (1,4,5,6) ketma-ketliklari (2,1,1,4,7,5,6) massivining eng uzun o‘suvchi qism ketma-ketliklari bo‘lib, ularning uzunligi 4 ga teng.

Endi Azizbek quyidagi savolga duch keldi:
\(B = (b_1, b_2, …, b_m)\) ketma-ketlik berilgan bo‘lsin. \(C\) — \(B\) ning biror qism ketma-ketligi bo‘lsin va \(C\) ning eng uzun o‘suvchi qism ketma-ketligi uzunligi \(k\) dan oshmasin. Shu shart ostida \(C\) ning maksimal uzunligi nechaga teng bo‘lishi mumkin?

Azizbek bu savolni juda oson deb hisoblab, yanada qiyinroq masala o‘ylab topdi. U sizga \(B = (b_1, b_2, …, b_n)\) ketma-ketligini va bir nechta so‘rovlarni beradi. Har bir so‘rovda ikkita butun son \(m\) va \(k\) beriladi. Siz B ketma-ketligining dastlabki m ta elementidan tashkil topgan massiv uchun yuqoridagi savolga javob berishingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(n\) va \(q\) beriladi. Bu yerda \(n\) — \(B\) massivining uzunligi, \(q\) — so‘rovlar soni.
Ikkinchi qatorda bo‘shliqlar bilan ajratilgan \(n\) ta musbat butun son \(b_1, b_2, …, b_n\) beriladi.
Keyingi \(q\) qatorda, \(i-\) qatorda ikkita butun son \(m_i\) va \(k_i\) beriladi.

\(1 \le n ≤ 10^5\)

\(1 \le q \le 2 \times 10^5\)

\(1 \le b_i \le n\)

\(1 \le k_i \le m_i \le n\)

Chiquvchi ma'lumotlar:

Jami q ta qatorda, har bir so‘rov uchun javobni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	20 10 5 12 7 3 9 15 2 8 6 4 11 14 1 10 13 18 16 17 20 19 5 1 5 2 8 2 10 3 12 1 12 2 15 3 18 4 20 1 20 5	3 4 6 9 5 8 12 14 6 16