A. Tub qadamlar

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Siz \(x\) sonidan \(y\) sonini hosil qilishingiz kerak, siz 2 xil turdagi amalni bajara olasiz. Ular:

\(X\) ga ixtiyoriy \(p\) tub sonini qo'shish.
\(X\) ga ixtiyoriy \(p\) tub sonini ko'paytirish.
Siz shu amallardan foydalangan holda \(Y\) sonini hosil qila olasizmi ? Agar hosil qila olsangiz \("YES"\), aks holda \("NO"\) so'zlarini chiqaring.

Tub son - faqatgina oziga va 1 ga bolinadigan son. 2, 5, 97 - tub sonlar, 1, 4, 100 - tub sonlar emas.

Kiruvchi ma'lumotlar:

\(T\) testlar soni, har bir test uchun \(X \ va \ Y\) sonlari kiritiladi.
\(1 \le T \le 100\)

\(1 \le X,Y \le 10 ^ 9\)

Chiquvchi ma'lumotlar:

Har bir test uchun masala javobini chiqaring

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 19 7 11 5 14 13 7 9 10 10	NO NO NO YES YES

B. Chiroyli naqsh

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Muhammadamin naqsh chizishga juda qiziqadi. Bu qiziqish unda endi qo'liga ruchka olishni boshlagan davrlardan bor, u o'shanda uydagi hamma devorlarga "chiroyli" qilib "naqsh"lar chizib chiqgan.

Hozir u katta bo'lgan. Shu sababli u endi devorlarga emas, millimetr qog'oziga naqshlar chizadi.

Faqatgina oq yoki qora kvadratchalardan iborat \(N \times M\) o'lchamli naqshda agarda hech bir qatorida, hamda, hech bir ustunida ketma-ket 3 ta bir xil rangli kvadratcha uchramasa bunday naqshni Muhammadamin chiroyli deb hisoblaydi, va bu naqshning chiroylilik darajasi undagi qora kvadratchalar soniga teng deb hisoblaydi.

Ayni vaqtda Muhammadaminda o'lchami \(A \times B\) millimetr qog'ozi bor. Muhammadamin bu qog'ozga naqsh chizmoqchi. Unga chizishi mumkin bo'lgan naqshning chiroylilik darajasi maksimal nechchi bo'lishini aniqlashda yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 10^5)\) - testlar soni kiritiladi.

Keyingi \(T\) ta qatorning har birida ikkitadan butun son, \(A(1 \le A \le 10^9)\) va \(B(1 \le B \le 10^9)\) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda bitta butun son, o'lchami \(A \times B\) bo'lgan naqshning maksimal chiroylilik darajasini chop eting.

Izoh:

\(2 \times 6\) uchun:

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 2 6 10 15 9 7 13241234 12345523 29 31	8 100 42 108979972596922 600

C. Aniq 4 ta

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Sizga \(N\) soni berilgan, \([1,N]\) oraliqdan tasodifiy tanlangan bitta sonning bo'luvchilari soni aniq 4 ta bo'lish ehtimolini \(998244353\) ga bo'lgandagi qoldiqni toping.

Kiruvchi ma'lumotlar:

\(N(1 \le N \le 10^5)\)

Chiquvchi ma'lumotlar:

Masala javobi.

Izoh:

\(p/q \% mod = p * q^{phi(mod) - 1} \%mod\)

Masaladagi Mod tub son bo'lganligi sababli \(phi(mod) = mod - 1\) ga teng.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6	166374059
2	2	0

D. 🐟 Piranilar Migratsiyasi

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Amazonka daryosining bir bo‘lagida \(N\) ta pirani istiqomat qiladi. Har bir \(i\)-piraniyaning vazni \(w_i\) ga teng.

Bahor fasli kelishi bilan ular yangi hududlarga ko‘chish uchun katta migratsiya to‘dalarini shakllantiradi. Ammo migratsiya payti — uzoq yo‘l, tez oqim va ovqat tanqisligi sabab — piraniyalar odatdagidan ham tajovuzkorroq bo‘lib qoladi.

Faqat migratsiya vaqtida, agar to‘da ichida eng og‘ir va eng yengil piraniyalar vaznlari orasidagi farq \(K\) dan oshsa, kichik(kuchsiz)lari xavf ostida qoladi, chunki yirik piranilar ularni yeb qo‘yishi mumkin.
Doimiy yashab turgan hududlarida esa bunday xavf yo‘q — ular tinch-totuv yashashadi.

Shu sababli, har bir piraniya o‘ziga qulay bo‘lgan eng katta xavfsiz to‘da kattaligini bilmoqchi. Ya’ni, \(i\)-piraniya qatnashadigan, va undagi eng og‘ir hamda eng yengil piraniyalar vaznlari farqi eng ko‘pi bilan \(K\) ga teng bo‘lgan maksimal migratsiya to‘dasining o‘lchamini topish kerak.

Vazifa

Har bir \(i (1 \le i \le N)\) uchun:

\(i\)-piraniya xavfsiz ravishda qo‘shila oladigan maksimal migratsiya to‘dasi kattaligini aniqlang.

Eslatma: Hali hech qanday guruhlar shakllantirilmagan. Guruh shakllantirilsa men maksimal nechta piranilik guruhga tushishim mumkin deb har bir pirani o'ylayapti.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikki butun son: \(N (1\le N \le 2 \times10^5)\) va \(K(0 \le K \le 10^9)\).

Ikkinchi qatorda \(N\) ta butun son: \(W (1 \le W_i \le 10^9)\) - massivi, ya'ni har bir piranining vazni kiritiladi.

Chiquvchi ma'lumotlar:

\(N\) ta son chiqaring — har bir \(i\) uchun u ishtirok eta oladigan eng katta xavfsiz migratsiya to‘dasi o‘lchami.

Misollar:

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

E. Imperatorning vasiyati

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Imperator tashkil qilgan imperiyada \(N\) ta shahar bor, shaharlar \(1\) dan \(N\) gacha sonlar bilan belgilangan, va bu shaharlarni bog'lab turadigan \(N\) ta yo'l bor. Bu yo'llar orqali barcha shaharlar o'zaro bog'langanligi kafolatlanadi.

Imperiyaning barcha aholisi shaharlarda istiqomat qilishadi, \(i(1 \le i \le N)\) - shaharda \(A_i\) ta aholi (soliq to'lovchi) istiqomat qiladi.

Imperatorning ikki o'g'li bor. Imperator vafotidan so'ng o'g'illari taxt uchun talashmasin degan maqsadda vafotidan oldin ularga vasiyat yozib qoldirmoqda.

Uning vasiyati quyidagicha:

O'g'illarim imperiyani kelishgan holda ikkiga bo'lib oling, ya'ni, ayrim shaharlar katta o'g'limga, qolgani esa kichik o'glimga bo'lsin.

Shaharlarni shunday taqsimlangki har biringiz o'zingizga ajratilgan ixtiyoriy bir shahardan boshqa bir shaharingizga o'zingizga tegishli shaharlar orasidagi yo'llar orqali bora oling.

Bo'linish adolatli bo'lishi uchun har ikkalangizning umumiy soliq to'lovchilaringiz soni orasidagi farq mumkin qadar kichik bo'lsin, tabbiiyki bu farqni nol tenglashtirishning imkoni bo'lmasa katta o'g'limga ko'proq soliq to'lovchi qolsin.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(N (3 \le N \le 10^5)\) soni, imperiyadagi shaharlar soni kiritiladi.

Ikkinchi satrda \(N\) ta butun son, \(A(1 \le A_i \le 10^9)\)-har bir shahardagi soliq to'lovchilar soni kiritiladi.

Keyingi \(N\) ta satrda ikkitadan butun son, navbatdagi yo'l qaysi ikki shaharni bog'lab turishi kiritiladi.

Chiquvchi ma'lumotlar:

Imperatorning o'g'illari shaharlarni otasining vasiyati asosida bo'lib olishsa o'g'illarning soliq to'lovchilari soni orasidagi farq eng kamida nechchi bo'lishini aniqlang.

Misollar:

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