A. Fibonacci – oxirgi raqam

Xotira: 16 MB, Vaqt: 1000 ms

Masala

F₀ = 0, F₁ = 1, … , F_k = F_k-1 + F_k-2 (k > 1) sonlar ketma-ketligi Fibonacci ketma-ketligi deyiladi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida T(1 ≤ T ≤ 10⁵) testlar soni kiritiladi. Keyingi T ta qatorda bittadan butun son, N(0 ≤ N ≤ 10¹⁸) soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida bitta butun son, har bir testdagi N uchun alohida qatorda N-fibonacci sonining oxirgi raqami chop etilsin.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 4 5 6 7	2 3 5 8 3
2	8 12 16 34 18 23 36 35 35	4 7 7 4 7 2 5 5

B. Eng kichik katta

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga S satr beriladi. Siz bu satrning belgilarini o’rnini almashtirish orqali yangi satr hosil qilishingiz mumkin. Siz S satridan foydalangan holda S satrdan leksikografik katta bo’lgan, leksikografik eng kichik satrni hosil qiling.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10⁵) testlar soni kiritiladi. Keyingi T ta qatorning har birida bittadan S(1 ≤ |S| ≤ 100) satri kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda masala yechimini chop eting. Agar bunday yechim mavjud bo’lmasa no answer yozuvini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 ab bb hefg dhck dkhc	ba no answer hegf dhkc hcdk

C. Qirqilgan rasm

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Laziz va Adizda raqamlardan iborat NxM o’lchamli bir xildagi rasm mavjud. Laziz o’zidagi rasmdan nxm o’lchamli qismini qirqib oldi va xuddi shu o’lchamli o’z rasmlar orasiga joylashtirdi. Kunlardan bir kun Adiz Lazizning rasmlarini tomosha qilib turgan vaqtida uning rasmlari ichidan nxm o’lchamli bir rasmni oldi va o’zidagi NxM o’lchamli rasmning qaysidir bir qismimi yoki yo’qligini bilmoqchi. Siz Adizga buni aniqlashtirib olishda yordam bering.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 5) testlar soni kiritiladi. Keyingi qatordan har bir test uchun dastlab N va M(1 ≤ N, M ≤ 1000), keyingi N ta qatorda M tadan raqam, keyingi qatorida n(1 ≤ n ≤ N) va m(1 ≤ m ≤ M), keyingi n ta qatorida M tadan raqam kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda agar nxm o’lchamli rasm NxM o’lchamli rasmdan qirqib olingan bo’lsa YES aks holda NO so’zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 2 6 999999 121211 2 2 99 11	YES
2	1 4 4 1234 4321 9999 9999 2 2 12 21	NO

D. Arifmetik progressiya - 2

Xotira: 16 MB, Vaqt: 1000 ms

Masala

1, 2, 3, …, N sonlar ketma-ketligidan aynan K tasi tanlab olinganda, tanlab olingan qiymatlar arifmetik progressiyani tashkil etish variantlar sonini aniqlang, ya’ni tanlab olingan sonlar ketma-ketligi tartiblangan holda barcha qo’shni elementlar ayirmasi bir xil bo’lishi kerak.

Kiruvchi ma'lumotlar:

Kirish faylining yagona satrida ikkita butun son, N (3 ≤ N ≤ 10⁹) va K (3 ≤ K ≤ min(20, N))soni kiritiladi.

Chiquvchi ma'lumotlar:

Masalada so’ralgan javobni chop eting.

Misollar:

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

E. Chumoli 2

Xotira: 10 MB, Vaqt: 1000 ms

Masala

Chumolilar yozda qish uchun uyiga qishgi oziq ovqatlarni to’plashini bilamiz. Bu gal ham chumolilar galasi qish uchun oziq ovqat to’plashga yo’lga chiqishda. Ular doim o’zi uchun tekis ya’ni bir chiziqda harakatlanadigan yo’lni qidirishadi va ular yo’lda bir o’rmonni uchratishdi. Ular endi bu o’rmon orqali o’ta olishadimi yo’qmi aniqlamoqchi. O'rmonda barcha daraxtlar aylana shakilda va hech bir ikkitasi bir biriga tegmaydi, Chumolilar o’rmonga kirmasdan ixtiyoriy bir nuqtadan o’rmonga qaraydi va o’rmonning nargi tarafi ko’rinsa demak o’ta olamiz degan xulosaga kelishadi aks holda ular boshqa yo’l qidirishadi. Sizning vazifangiz chumolilar o’rmon ichidan nargi tarafga tekis bir chiziqda daraxtlarga tegmasdan o’ta olishadimi yo’qmi aniqlash.

Kiruvchi ma'lumotlar:

Kirish fayilining dastlabki satirida \(N (1\leq N\leq 100)\) jami o'rmondagi daraxtlar soni.

Kiyingi \(N\) ta satirda uchtadan son \(x,y, r(-1000\leq x, y\leq 1000, 1\leq r\leq 1000)\) daraxtning markazini koordinatasi va daraxtning radusi berilgan.

Chiquvchi ma'lumotlar:

Chiqish fayilida agar chumolilar galasi o'rmondan bir tekis chiziqda kesib o'tishning imkoni bo'lsa Yes aks holda No so'zini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 0 10 2 5 11 2 12.04 7 2	Yes
2	3 0 0 1 2.05 0 1 1.02 -1.9 1	No

F. Sumalak toshlari

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Dasturchialr Klubi jamoasi har yili birgalikda sumalak tayyorlash uchun bir joyga yig'ilishadi. Bu yil ham sumalak tayyorlash ishlari avjida. Ammo sumalakka solinadigan \(M\) ta toshlar yo'q edi. \(N\) ta bola tosh keltirish uchun jo'nab ketishdi va har biri \(a_i\) ta tosh keltirdi.
Sizning vazifangiz sumalakka \(M\) ta tosh solish uchun eng kamida nechta bolaning tergan toshlari tanlanadi?

Kiruvchi ma'lumotlar:

Birinchi qatorda \(M\) va \(N\) natural sonlari. Ikkinchi qatorda esa mos ravishta \(N\) ta bolaning keltirgan \(a_i\) toshlari soni. \((1 \le M, N, a_i \le 1000)\)

Chiquvchi ma'lumotlar:

Yagona qatorda sumalakka \(M\) ta tosh solish uchun kamida nechta boladan toshlar olinishini chiqaring. Agar toshlar yetarli bo'lmasa -1 chiqaring

Misollar:

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

G. Mul & add

Xotira: 10 MB, Vaqt: 1000 ms

Masala

Sizga ikkita A va B sonlar berilgan bo'lib, sizning vazifangiz agar bu ikki son bitta satrda berilgan bo'lsa \(A+B\) ni hisoblang, agarda alohida satrlarda berilgan bo'lsa \(A*B\) ni hisoblang.

Kiruvchi ma'lumotlar:

Kirish faylida ikkita \(A, B (-10^9\leq A, B\leq 10^9)\) butun sonlar berilgan (bitta satrda probel bilan ajratilgan holda yoki alohida satrlarda bo'lishi mumkin).

Chiquvchi ma'lumotlar:

Chiqish faylida masalaning javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	7 7	14
2	7 7	49

H. 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

I. Pifogor soni

Xotira: 128 MB, Vaqt: 3000 ms

Masala

Dasturchilar Klubi a'zosi Azimjon geometriyaga juda qiziqadi. Ayniqsa u Pifogor teoremasini juda yaxshi ko'radi.
Azimjon yaqinda o'zi uchun yangi qiziqarli sonlarni kashf qildi va ularni "Pifagor son"lari deb nomladi.
Pifagor soni deb (a²+b²) ko'rinishida yozish mumkin bo'lgan tub songa aytiladi. Misol uchun 5 = 1²+2² demak 5 pifagor soni, 25 = 3²+4² lekin 25 tub son emas shuning uchun ham u pifagor soni bo'la olmaydi.
a va b sonlari ixtiyoriy musbat sonlar hisoblanadi.

Kiruvchi ma'lumotlar:

Bitta qatorda X va Y sonlari berigan,
(1 ≤ X, Y ≤ 3·10⁸)

Chiquvchi ma'lumotlar:

Bitta qatorda [X,Y] oraliqda nechta Pifagor sonlari borligini ekranga chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 10	2
2	1 3	1

J. Ketma-ketlik oxirgi raqam

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Jahongir ketma-ketliklarga qiziqadi. Bir kuni u ustozi bergan ketma-ketlik qaysi qonuniyat asosida ketishini aniqlash va shu ketma-ketlikning n-hadini oxirgi raqamini topish kerak edi. Jahongir qonuniyatni topdi! Qonuniyat shundan iborat ediki ketma-ketlikning dastlabki 3ta hadi beriladi. keyingi har bir had o'zidan oldingi 3ta hadning yig'indisiga teng. Endi sizning vazifangiz shu qonuniyat asosida ketma-ketlikning n-hadini topib Jahongirga yordam berishdan iborat

Kiruvchi ma'lumotlar:

Birinchi qatorda probel bilan ajratilgan holda 3ta butun son a, b, c va keyingi qatorda q butun sonlari kiritiladi. Keyingi qatorda probel bilan ajratilgan holda q ta butun son probel bilan ajratilgan holda kiritiladi. \((1 \leq a, b, c \leq 10^{18}, 0 < q \leq 1000, 1 \leq n \leq 10^{18})\)

Chiquvchi ma'lumotlar:

Chiqish faylida bitta qatorda q ta so'rov uchun ketma-ketlikning n-hadning oxirgi raqami probellar bilan ajratilgan holda chiqarilsin.

Izoh:

a-had ketma-ketlikning 0-hadi hisoblanadi

Misollar:

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

K. Karta

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Suhrobjon pullarini kartada saqlaydi. U uyida kuniga qancha vaqt chiroq ishlatsa, shunga qarab bank uning hisobidan pul yechib oladi. Ammo uning baxtiga agar bir nechta chiroqlar bir vaqtda yonib turgan taqdirda ham, bittasi yonib tursa qancha olsa, shuncha miqdor talab qilinadi. Bugun uning N so'm puli bor. Suhrobjon ertaga ertalab turib kartasiga qaraganda qancha puli qolganini ko'radi!?

Kiruvchi ma'lumotlar:

Birinchi qatorda N, S va M mos ravishta kartadagi puli (so'mda), Har bir daqiqa uchun ketadigan pul (so'mda) va ishlatilgan chiroqlar soni. (1 ≤ N ≤10⁹ , 1 ≤ S ≤ 10³, 1 ≤ M ≤10)

Keyingi M ta qatorda har bir chiroqning qachondan qachongacha ishlatilgani beriladi(masalan 12:00-13:30)

Chiquvchi ma'lumotlar:

Yagona qatorda masalaning javobini chop eting!

Izoh:

Karta hech qachon minusga chiqmasligini inobatga oling.Agar mablag' yetarli bo'lmasa Kartada bor pulni yechib oladi!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	120 1 2 12:00-13:30 12:30-13:30	30

L. G'aroyib yig'indi

Xotira: 16 MB, Vaqt: 1000 ms

Masala

Sizga ikkita natural son beriladi. Sizning vazifangiz shu sonlar orasidagi 3ga bo'linadigan ammo 7 bo'linmaydigan sonlar yigindisini topish. Bunda ikkala chegara ham kiradi.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining yagona qatorida ikkita manfiy bo'lmagan butun sonlar berilgan, sonlar 10⁹ dan oshmaydi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylining yagona satrida yig'indisini chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	26 443	27696
2	41 743	78402
3	67 542	41412

M. Oxirgi yig'indi

Xotira: 256 MB, Vaqt: 2000 ms

Masala

Bu masalada sizga \(N\) o'lchamli \(A\) massiv berilgan. Siz esa uni oxirgi elementi qolguncha quyidagi amalni bajarishingiz kerak bo'ladi. Misol uchun sizga 5 ta elementdan iborat quyidagi massiv berilsa\( [1,2,3,4,5]. [1+2,2+3,3+4,4+5]\) va keyin\( [3,5,7,9] \)massivi hosil qilinadi. So'ng yana\( [3+5,5+7,7+9] = [8,12,16]\). Bu amal toki massiv elementi bitta qolguncha davom etadi. \([8+12,12+16] = [20,28]\) va oxirida \([20+28]\) qoladi. Shunda natija \(48\)teng bo'ladi. Siz ham sizga berilgan massivni oxirgi elementi qolguncha shu amallarni ketma - ket bajarib borasiz. Eng oxirida qolgan elementni ekranga chiqarishingiz kerak bo'ladi.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) soni \(N(3≤N≤10^6).\)

Ikkinchi qatorda \(N \) ta sondan iborat \(A\) massiv \(A[i] (1≤ A[i]≤10^9).\)

Chiquvchi ma'lumotlar:

Yagona qatorda masala yechimini ekranga chiqaring.

Izoh:

Masala yechimi juda katta bo'lib ketishi mumkin shuning uchun uni \(10^9+7\) ga bo'lgandagi qoldiqni ekranga chiqarishingiz kerak bo'ladi.

Misollar:

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