A. Keyingi darsga tayyorgarlik.

Xotira: 20 MB, Vaqt: 250 ms

Masala

Anvar darsda EKUB haqida o'rgandi. Uyga vazifada ustozi unga EKUK ni o'rganib kelishini aytdi. Keyingi darsda ularga ustozi EKUK ga oid misol bermoqchi edi.

Misolda ustozi unga \(N\)ta son beradi \(\{A_1,A_2,A_3, ..., A_N\}\).

Fib to'plam = \(\{F_{A1},F_{A2}, F_{A3}, ..., F_{AN}\}\).

U shu Fib to'plamni umumiy EKUKini topishi kerak.

Fn - Fibonacci ketma-ketligining n - hadi.

Sizning vazifangiz Anvar misolga tayyorlanishga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N(1 \le N \le 100)\) soni kiritiladi.

Keyingi \(N\) ta qatorda \(A\) to'plam elementlari beriladi.

To'plam elementlari \(10^9\) dan oshmaydigan natural sonlardir.

Chiquvchi ma'lumotlar:

Fib to'plamning umumiy EKUKi ni \(1000000007\) ga bo'lgandagi qoldiqni chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 1 3 3 6 9	136

B. Eng yaqin yig'indi

Xotira: 20 MB, Vaqt: 250 ms

Masala

Sizga \(n\) ta elementdan iborat to'plam va summa beriladi. sizning vazifangiz shu to'plam elementlaridan istalgancha (0 ta ham) foydalanib summa ga eng yaqin lekin undan oshmaydigan yig'indi hosil qilish.

Kiruvchi ma'lumotlar:

Bir qatorda \(t\) testlar soni \(( 1 \le t \le 10)\)

Har bir test uchun birinchi qatorida \(n\) va summa, ikkinchi qatorda \(n\) ta son.

(\(n\) , summa va to'plam elementlari 2000 dan oshmaydiga musbat son)

Chiquvchi ma'lumotlar:

Har bir test uchun eng yaqin yig'indi.

Misollar:

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

C. Satr anagrammalari.

Xotira: 20 MB, Vaqt: 250 ms

Masala

Sizga \(S\) satr beriladi. Sizning vazifangiz \(S\) satr anagrammalari ichidan palindrom satr nechta ekanligini topish.

Kiruvchi ma'lumotlar:

Bir qatorda \(S(1 \le |S| \le 10^5)\) kiritiladi.

Chiquvchi ma'lumotlar:

Palindrom satrlar sonini \(1000000007\) ga bo'lgadagi qoldiq.

Izoh:

bbbbhh bu satr uchun palindromlar.

bbhhbb, bhbbhb, hbbbbh.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	bbbbhh	3

D. G'alati sonlar #1

Xotira: 20 MB, Vaqt: 1000 ms

Masala

\(n\) xonali g'alati son 2 ta shartni bajarishi kerak.

1. Boshidan \(n\over2\)raqami yig'indisi oxiridan \(n\over2\) ta raqamini yig'indisini teng bo'lishi kerak.
2. Juft o'rinda turgan raqamlar yigindisi toq o'rinda turgan raqamlar yig'indisiga teng bo'lishi kerak.

Sizning vazifangiz \(n\) xonali g'alati sonlar nechtaligini topish. \(n\) juft sonligi kafolatlanadi.

Kiruvchi ma'lumotlar:

Birinchi qatorda yagona \(n(2 \le n \le 6)\) soni

Chiquvchi ma'lumotlar:

\(n\) xonali g'alati sonlar sonini chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2	10

E. G'alati sonlar #2

Xotira: 20 MB, Vaqt: 250 ms

Masala

\(n\) xonali g'alati son 2 ta shartni bajarishi kerak.

1. Boshidan \(n \over 2\) raqami yig'indisi oxiridan \(n\over2\) ta raqamini yig'indisini teng bo'lishi kerak.
2. Juft o'rinda turgan raqamlar yigindisi toq o'rinda turgan raqamlar yig'indisiga teng bo'lishi kerak.

Sizning vazifangiz \(n\) xonali g'alati sonlar nechtaligini topish. \(n\) juft sonligi kafolatlanadi.

Kiruvchi ma'lumotlar:

Bir qatorda \(n(2 \le n \le 200000)\).

Chiquvchi ma'lumotlar:

\(n\) xonali g'alati sonlar sonini 998 244 353 ga bo'lgandagi qoldiq.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	4	100
2	2	10

F. Murakkab vazifa

Xotira: 20 MB, Vaqt: 500 ms

Masala

Anvar matematikadan juda yaxshi edi. Buni ustozi ham bilar edi. Lekin u faqat ifodani juft yoki toqligini aniqlashda adashar edi. buni bilgan ustozi unga misol bermoqchi bo'ldi. Misol quyidagilardan iborat edi. Ustozi unga \(x\) va \(y\) ni toq yoki juftligini aytadi va bir ifoda \(x\) va \(y\) lardan tashkil topgan ifoda beradi. Anvarning vazifasi esa ifoda toq yoki juftligini topishdan iborat. Anvarga bu misollarni yechishda yordam bering.

Kiruvchi ma'lumotlar:

\(x\) va \(y\) dan tashkil topga ifoda.

ikkita qatorda mos ravishda \(x\) va \(y\) ni toq yoki juftligi.

Chiquvchi ma'lumotlar:

Ifoda toq bo'lsa "toq" aks holda "juft" deb chiqarsin.

Izoh:

Eslatma ifodada \(x\) va \(y\) qatnashmagan bo'lishi ham mumkin.
2 - misolga qarang.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	x-y*2 toq toq	toq
2	2+2 toq toq	juft

G. Deyarli palindrom

Xotira: 20 MB, Vaqt: 1000 ms

Masala

Palindrom bo'lishi uchun ko'pida bitta raqamini o'zgartirish kerak bo'lgan sonlar deyarli palindrom deyiladi.

Sizga \(n\) soni beriladi. Sizning vazifangiz \([1,n]\) oralig'ida nechta deyarli palindrom borligini topish.

Kiruvchi ma'lumotlar:

Kirish faylida \(n(0 \le n \le 10^{18})\) 0 bo'lgangacha \(n\) son alohida qatorda kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir \(n\) son uchun deyarli palindromlarni alohida qatorlarda chiqaring.

Izoh:

1234311 shundan bitta raqam ni o'zgartirsak palindrom bo'ladi.

1 ham deyarli palindrom chunki shartda ko'pida bitta deyilgan. Demak raqam o'zgartirmasak ham bo'ladi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	10 1000 1000000 0	10 1000 45010

H. Tub sonlar to'plami

Xotira: 25 MB, Vaqt: 500 ms

Masala

Sizga \(n\) ta tub sondan iborat tartiblangan to'plami beriladi. Sizning vazifangiz barcha tub buluvchilari shu tuplamda bulgan \(k\) - eng kichik sonni topish.

Kiruvchi ma'lumotlar:

Ikki qatorda \(n(1 \le n \le 16)\) soni va tub sonlardan iborat to'plam \((2 \le a_i \le 100)\)
Uchinchi qatorda \(k (1 \le k)\) soni.

Chiquvchi ma'lumotlar:

K-son chiqarish.

Izoh:

Har doim 1-son 1 ga teng.
k-son \(10^{18}\)dan oshmasligi kafolatlandi.
1-test uchun. { 2 , 3 , 5 }
shu to'plam uchun 7-son 8
{ 1, 2, 3, 4, 5, 6, 8 ... }

Misollar:

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

I. Qism massiv #1

Xotira: 20 MB, Vaqt: 500 ms

Masala

Sizga \(n\) va \(k\) beriadi. \(n\) ta elementdan iborat \(a\) to'plam elementlari beriladi. To'plam elementlari \(k\) dan oshmaydigan musbat son. Siz shunday minimal uzunlikga ega qism massiv topishingiz kerakki \([1,k]\) oralg'idagi barcha son qatnashgan bo'lsin.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t (1 \le t \le 10)\) testlar soni.

Har bir test uchun birinchi qatorda \(n (1 \le n \le 100000)\), \(k (1 \le k \le 10000)\). Ikkinchi qatorda \(a\) to'plam elementlari.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda topilishi kerak bo'gan qismmassiv uzunligi.

Misollar:

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

J. Qism massiv #2

Xotira: 20 MB, Vaqt: 1000 ms

Masala

Sizga \(n\) ta elementdan iborat \(a\) to'plam berilgan. Sizning vazifangiz \(a\) to'plam elementlari ichidan maksimal uzunlikga ega kamaymaydigan tartibdagi qism massiv uzunligini chiqarish.

Kiruvchi ma'lumotlar:

Bir qatroda \(n (1 \le n \le 10^5)\).
Ikkinchi qatorda \(a (1 \le a_i \le 10^9)\) to'plam elementlari

Chiquvchi ma'lumotlar:

Qism massiv uzunligi.

Misollar:

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