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