A. To’plam osti

Xotira: 16 MB, Vaqt: 1000 ms

Masala

N ta elementdan iborat to’plam berilgan. Sizning vazifangiz shu to’plamdan maksimum sondagi elementlarni shunday ajratib olishki, olingan elementlar ichida ixtiyoriy har xil ikkitasi tanlanganda yig’indi hech qachon K ga bo’linmasin.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida ikkita butun son, N(1 ≤ N ≤ 10⁵) va K(1 ≤ K ≤ 100), keyingi satrda N ta [1, 10⁹] oralig’idagi butun sonlar, to’plam elementlari kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida yagona son, masala shartiga muvofiq maksimum nechta element ajratib olinishi mumkinligini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 3 1 7 2 4	3
2	5 5 2 7 12 17 22	5

B. 0 va 1 lar soni

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Aziz juda katta B binar soni ustida ishlamoqda. Son juda katta bo’lganligi bois sizga bu son A butun sonli massivga ixchamlashtirilgan holatda beriladi, ixchamlashtirishda ketma-ketligi mos ravishda (A₀, A₂, A₄, …) juft indekslarda navbati kelgan 1 lar soni, (A₁, A₃, A₅, …) toq indekslarda navbati kelgan 0 lar soni saqlanadi. Aziz jami 0 lar soni va jami 1 lar soni B sonikiga teng bo’lgan, eng kichik C(>B) binar sonini hosil qildi. Siz Aziz hosil qilgan C sonining ixchamlashtirilgan shaklini D massivni hosil qiling.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 100) testlar soni kiritiladi.

Keyin har bir test uchun alohida ikkita qatorda ma’lumotlar quyidagicha kiritiladi:

Birinchi qatorda bitta butun N(1 ≤ N ≤ 10) soni, A massiv uzunligi
Ikkinchi qatorda N ta butun son, A massiv elementlari. (1 ≤ A_i ≤ 10¹⁸)

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida ikkita qatorda quyidagi shaklda javobni chop eting:

Birinchi qatorda bitta butun M soni, D massiv uzunligi
Ikkinchi qatorda M ta butun son, D massiv elementlarini bo’sh joy bilan ajratilgan holda chop eting, (1 ≤ D_i)

Har bir test uchun mos keluvchi javob borligi kafolotlanadi.

Misollar:

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

C. Qism satr

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Uzungligi \(N\) bo`lgan \(S\) satr beriladi, berilgan satrdan shunday eng uzun qism satrni topingki unda bir xil harf ko`pi bilan \(K\) marta qatnashgan bo`lsin.

Masalan:
\(N = 6, K = 1\)
\(S = “Husayn”\)bunda javob sifatida \(“Husayn”\) olinsa bo`ladi, chunki hamma harf bir martadan qatnashgan.
Ammo:
\(N = 7, K = 1 \newline S = “Hasanov”\)
bunda esa \(“Has”\) yoki \(“sanov”\) ni olish mumkin xolos shart bo`yicha eng uzuni “sanov” olinadi.

Bunday satrlar juda ham ko`p bo`lishi mumkin, sizning vazifangiz satrning uzunligi topish.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(K (1 \le K \le N \le 10^5)\) butun sonlari mos ravishda satr uzunligi va qism satr uzunligi.

Keyingi qatorda \(N\) uzunlikga ega lotin harflaridan iborat \(S\) satr beriladi

Chiquvchi ma'lumotlar:

Yagona butun son, shartni qanoatlantirishi mumkin bo`lgan qism satr uzunligini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	6 1 Husayn	6
2	7 1 Hasanov	5

D. Ajoyib sonlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Natural bo’luvchilar soni toq bo’lgan sonlar ajoyib sonlar deyiladi. Berilgan N soni ajoyib son yoki yo’qligini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T (1 ≤ T ≤ 1000) testlar soni kiritiladi. Ikkinchi satrdan boshlab har bir test uchun alohida satrda bitta butun son N (1 ≤ N ≤ 10¹⁸) soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida qatorda agar N soni ajoyib son bo’lsa YES aks holda NO so’zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 1 3 7 169	YES NO NO YES

E. Nisbat 2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Quyidagi formulani hisoblang:

\(\cfrac{a + a^2+a^3+\dots+a^n}{a^{-1}+a^{-2}+\dots+a^{-n}}\)

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining birinchi satrida ikkita natural son \(a \le 10^9, n \le 1000\) beriladi

Chiquvchi ma'lumotlar:

Masala javobini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 2	8

F. Rangli markerlar

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga kvadrat katakchalardan iborat cheksiz jadval beriladi. Dastlab, barcha katak oq rangda.

Sizda qizil va ko'k marker bor. Siz jami a ta katakni qizil marker bilan, b ta katakni ko’k marker bilan bo'yashingiz mumkin. Bitta katakni bir vaqtda har ikkala rangda bo’yash mumkin emas. Ikkala markerni ham to’liq ishlatishingiz kerak, buning uchun jadvalda jami a ta katak qizil rangda, b ta katak ko’k rangda bo’lishi kerak.

Siz jadvalni quyidagi qonuniyat asosida bo’yashingiz kerak:

Jadvalda yuzasi a + b ga teng bo’lgan, bo’yalgan to’rtburchak hosil bo’lishi kerak;
kamida bitta rangdagi barcha kataklar ham to'rtburchak hosil qilsin .

To'g'ri bo’yashga ba'zi misollari:

Noto’g’ri bo’yashga ba’zi misollar:

Berilgan a va b dan foydalanib to’g’ri bo’yash hisoblanadigan to’rtburchaklar ichidan perimetri eng kichik bo’lgan to’rtburchakning perimetrini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida ikkita butun son, \(a\) va \(b(1 \le a,b \le 10^{14})\), qizil va ko’k markerda bo’yalishi kerak bo’lgan kataklar soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son, masala yechimini chop eting!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4 4	12
2	3 9	14
3	9 3	14
4	3 6	12

G. Fibonacci - qoldiq

Xotira: 16 MB, Vaqt: 1000 ms

Masala

\(F(0)=0 , F(1)=1 , \space \dots \space, F(n) = F(n-1) + F(n-2) ( n > 1 )\) ketma-ketlik Fibonacci ketma-ketligi deyiladi. Sizni vazifanggiz \(i\) - fibonacci sonini \(j\) - fibonacci soniga bo'linishini tekshirish.

Kiruvchi ma'lumotlar:

Dastlabki qatorda \(T ( T ≤ 10 )\) testlar soni kiritiladi. Keyingi qatorda har bir test uchun 2 tadan butun son \(i\) va \(j\) sonlari kiritiladi \(( 1 ≤ i , j ≤ 10^{18} )\)

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida \(F(i) \space F(j)\) ga qoldiqsiz bo'linsa YES aks holda NO so'zi chop etilsin

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 5 3	NO

H. Murakkab tenglama

Xotira: 16 MB, Vaqt: 1000 ms

Masala

\(ax^3+bx^2+cx+d=0\) ko'rinishidagi tenglama berilgan bo'lsin. Biz 3-darajali tenglamani kamida bitta butun ildizga ega bo'lgan paytida Murakkab tenglama deb atashimiz mumkin.Sizga \(a,b,c,d\) sonlar berilgan bo'lsa \((a ≠ 0)\), ushbu matematik ifoda Murakkab tenglama bo'la oladimi yoki yo'qligini aniqlashdan iborat.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida \(4\) ta butun sonlar \((-10^{12} ≤ a,b,c,d ≤ 10^{12})\) kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida agar tenglama "Murakkab tenglama" bo'lsa "Yes", aks holda "No" so'zini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2 3 2	Yes
2	1 0 0 0	Yes

I. Rangli kataklar.

Xotira: 24 MB, Vaqt: 1000 ms

Masala

Mironshoh \(N*N\) to'rga va qizil bo'yoqga ega. U to'r chiroyli bo'lishi uchun \((i,j)\) katakni bo'yashi kerak agar \(i+j\) tub bo'lsa \((0 \le i,j \le n-1)\). U shunaqa tartibda kataklarni bo'yab chiqdi.

U bo'yagandan keyin nechta rangli kataklar bo'lganini topish.

Kiruvchi ma'lumotlar:

Bir qatorda \(N(1 \le N \le 1000000)\) soni.

Chiquvchi ma'lumotlar:

Bo'yalgan kataklar sonini \(10^9+7\) ga bo'lgandagi qoldiq.

Izoh:

n=3 bo'lganda

0-bo'sh kataklar 1-bo'yalgan kataklar.

000 001

000 011

000 110

\((0,2) (1,1) (1,2) (2,0) (2,1)\) shu kataklar bo'yaladi chunki i+j larni yig'indisi tub.

Misollar:

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

J. Uy ishi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Quvonchbek matematkani yaxshi bilganligi uchun ustozi unga "expression module" ga oid bo'lgan misol berdi. Misol quydagicha edi:

\((1^n+2^n+3^n+4^n) \space mod \space5\)

Quydagi ifodani natijasini olishda Quvonchbekga yordam bering.

Kiruvchi ma'lumotlar:

Yagona qatorda n(\(0\leq n \leq 10^{10^5}\) butun son kiritiladi.

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Izoh:

\((1^4+2^4+3^4+4^4) \space \text{mod} \space 5 \text{=}(1+16+81+256) \space \text{mod}\space =354 \space \text{mod} \space 5 = 4\)

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4	4