A. Ajoyib satr
Xotira: 16 MB, Vaqt: 1000 msdistance(S) funksiyasi S satrning barcha qo’shni belgilari ASCII qiymatlari ayirmasining modulidan tashkil topgan massivni qaytaradi. Ya’ni agarda S = “acxz” satr berilganda \([|97-99|, |99-120|, |120-122|] = [2,21,2]\) massivini qaytaradi.
Ajoyib satr deb distance(S) = distance(reverse(S)) bo’ladigan satrga aytiladi. Bu yerda reverse satrning teskarisini ifodalaydi.
Kirish faylining dastlabsi satrida bitta butun son, \(T(1 \le T \le 10)\) testlar soni kiritiladi. Keyingi \(T\) ta satrda \(S (2 \le S \le 10000)\)satr kiritiladi.
Chiqish faylida har bir test uchun alohida qatorda satr ajoyib satr bo’lsa “Ajoyib satr” aks holda “Oddiy satr” so’zini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 acxz bcxz |
Ajoyib satr Oddiy satr |
B. Sayohatchi
Xotira: 32 MB, Vaqt: 1000 ms
Abdullajon yerga sayohatidan so’ng o’z ona sayyorasiga qaytdi va u yerda oz muddat yashaganidan so’ng yana sayohatga chiqqisi kelib qoldi. Endigi gal u o’z sayohatini shaharlar orasidagi yo’llar daraxtsimon bo’lgan bir sayyoraga borishga qaror qildi. Bu sayyorada jami N ta shahar bor, shaharlar aro jami N-1 ta ikki tomonlama harakat qiladigan poyezdlar mavjud. Abdullajon bu sayyoraga sayohatini ixtiyoriy shahardan boshlashi mumkin. Afsuski bu sayyorada Abdullajonning noyob qobiliyatlari ishlamas ekan, ya’ni, u ketmon yoki boshqa buyumni uchira olmas, pul ishlab chiqara olmas ekan. Shu sababli Abdullajon bir shahardan boshqa shaharga borish uchun poyezddan foydalanishga qaror qilibdi, cho’ntagidagi pul jami K ta poyezd chiptasiga yetarli ekanligini bilganidan so’ng Abdullajon ko’pi bilan nechta shaharni aylanishi mumkinligini bilmoqchi. Buni aniqlashda Abdullajonga yordam bering.
Eslatma: Abdullajon sayohatni ixtiyoriy shahardan boshlashi va ixtiyoriy shaharda to’xtatishi mumkin. 1 ta poyezd chiptasi bir shahardan unga qo’shni (orasida poyezd bor) shaharga o’tish imkonini beradi.
Kirish faylining dastlabki satrida ikkita butun son, \(N (1 \le N \le 10^5)\) va \(K(0 \le K \le 10^6)\) sonlari kiritiladi.
Keyingi N-1 ta qatorda poyezd bilan ulangan shaharlar juftliklari kiritiladi (Shaharlar 1 dan N gacha nomerlangan holda ifodalangan).
Chiqish faylida Abdullajon sayohat davomida ko’pi bilan nechta shaharda bo’la olishini aniqlang.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 2 1 2 1 3 |
3 |
| 2 |
7 5 2 6 1 3 1 5 3 4 1 2 6 7 |
6 |
| 3 |
7 6 1 2 1 3 6 3 3 7 4 2 2 5 |
6 |
C. Juda toq son
Xotira: 16 MB, Vaqt: 1000 msNatural sonning yozilishida barcha raqamlari toq bo’lgan sonlar juda toq sonlar hisoblanadi.
Kirish faylida yagona butun son, \(N (1 \le N \le 10^{18})\) soni kiritiladi.
Chiqish faylida yagona butun son, N-juda toq sonni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 |
5 |
| 2 |
4 |
7 |
D. O'yin
Xotira: 16 MB, Vaqt: 1000 msAli va G'ani o'yin o'ynashmoqda. O'yin quyidagicha. Dastlab o'yin doskasida 1 dan N gacha nomerlangan toshlar mavjud, har bir o'yinchi o'z navbati kelganida ketma-ket nomerlangan ikkita toshni o'yin doskasidan olib tashlashi kerak, yurish amalga oshirolmaganlaridan so'ng o'yin tugaydi. O'yin tugagan vaqtda doskada qolgan toshlarning soni toq bo'lsa Ali g'olib chiqadi, aks holda G'ani g'olib bo'ladi. O'yinni Ali boshlab beradi va o'yin navbatma - navbat o'ynaladi. Har ikkala o'yinchi ham optimal o'ynaganida kim g'olib bo'lishini aniqlang.
Kirish faylida yagona butun son, \(N(1 \le N \le 10^7)\) soni kiritiladi
Chiqish faylida kim g'olin chiqqanligini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 |
Ali |
| 2 |
4 |
G'ani |
E. ab satr
Xotira: 16 MB, Vaqt: 1000 msSizga faqatgina ‘a’, ‘b’ va ‘?’ dan tashkil topgan S satr beriladi. Bu yerda ‘?’ belgisi ‘a’ yoki ‘b’ ekanligini ifodalaydi. Shunday ekan satrda jami k ta ‘?’ belgisi mavjud bo’lsa ‘?’ lar o’rniga ‘a’ yoki ‘b’ ni qo’yish variantlar soni 2k tani tashkil etadi. Siz barcha variantlar uchun (i < j and Si = ‘b’ and Sj = ‘a’) shartni qanoatlantiradigan (i, j) juftliklar sonining umumiy summasini toping.
Kirish faylida yagona satr, \(S (1 \le |S| \le 500000)\) satri kiritiladi.
Sizdan so’ralgan natijani \(1000000007 (10^9+7)\) ga bo’lgandagi qoldiqni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
ababa |
3 |
| 2 |
b?? |
5 |
| 3 |
a?b????a |
256 |
F. Permutatsiyalar soni №3
Xotira: 16 MB, Vaqt: 1000 ms\(A\) ketma-ketlik 1 dan \(N\) gacha bo'lgan sonlarning shunday permutatsiyasiki unda \(A_1 = 1, |A_i - A_{i-1}| < 3, (2 \le i \le n)\) bo'ladi. Sizga \(N\) soni beriladi, \(A\) ketma -ketlikni hosil qilish variantlar sonini aniqlang!
Kirish faylida yagona butun son, \(N (1 \le N \le 10^{18})\) soni kiritiladi
Chiqish faylida yagona butun son, so’ralgan natijaning \(1000000007 (10^9+7)\) ga bo’lgandagi qoldiqni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 |
2 |
| 2 |
4 |
4 |
G. Ketma-ketlik 1*2
Xotira: 16 MB, Vaqt: 1000 ms\(A_n = \begin{cases} 1 & \text{agar} \space n = 0 \\ 2 & \text{agar} \space n = 1 \\ A_{n-1} * A_{n-2} & \text{agar} \space n > 1 \end{cases}\)
Kirish faylida yagona butun son, \(N (0 ≤ N ≤ 10^{18})\) soni kiritiladi.
Chiqish faylida yagona butun son, \(A_N\) ning qiymatini \(1000000009\) ga bo’lgandagi qoldiqni chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
8 |
2097152 |
| 2 |
4 |
8 |
| 3 |
6 |
256 |
H. Chiroyli naqshlar
Xotira: 32 MB, Vaqt: 1000 ms\(N \times M\) o’lchamli naqsh deb faqatgina 0 va 1 lardan iborat bo’lgan \(N \times M\) o’lchamli matritsaga aytiladi.
Naqsh ichida hech qayerda \(2\times2\) o’lchamli faqat bir xil raqamlardan iborat bo’lgan qism bo’lmasa bu naqsh chiroyli naqsh deyiladi.
Kirish faylining yagona satrida ikkita butun son, \(N\) va \(M (1 \le N \times M \le 121)\) sonlari bo’sh joy bilan ajratilgan holda kiritiladi.
Chiqish faylida yagona butun son, \(N \times M\) o’lchamli chiroyli naqshlar sonini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
2 2 |
14 |
| 2 |
3 3 |
322 |