A. Labirint
Xotira: 32 MB, Vaqt: 1000 msSizga UTF-16 belgilaridan hosil qilingan labirint beriladi. Siz labirintning \(A\) nuqtasidan \(B\) nuqtasiga olib boradigan yo’lni chizishingiz kerak bo’ladi. Labiring o’z ichiga \(N×M\) yacheykani qamrab oladi va misollarda ko’rsatilgandek ifodalanadi. Har bir yacheykani ifodalash uchun balandligiga 1 ta belgi, eniga 3 ta belgidan foydalanilgan. Labirintda siz quyidagi belgilardan foydalanishingiz mumkin:
|
№ |
belgi |
UTF-16 |
|
1 |
SPACE |
0x0020 |
|
2 |
─ |
0x2500 |
|
3 |
│ |
0x2502 |
|
4 |
┌ |
0x250C |
|
5 |
┐ |
0x2510 |
|
6 |
└ |
0x2514 |
|
7 |
┘ |
0x2518 |
|
8 |
├ |
0x251C |
|
9 |
┤ |
0x2524 |
|
10 |
┬ |
0x252C |
|
11 |
┴ |
0x2534 |
|
12 |
┼ |
0x253C |
|
13 |
╴ |
0x2574 |
|
14 |
╵ |
0x2575 |
|
15 |
╶ |
0x2576 |
|
16 |
╷ |
0x2577 |
Siz labirintda \(A\) nuqtadan \(B\) nuqtaga borish yo’lini misollarda ko’rsatilgandek ifodalang. \(A\) nuqtadan chiqish va \(B\) nuqtaga yetib borishda siz faqatgina №13, №14, №15, №16 dagi belgilardan foydalanishingiz mumkin.
Kirish faylining dastlabki satrida ikkita butun son, \(N(0 < N < 50)\) va \(M(0 < M < 100)\) mos ravishda labirintning qatorlar soni va ustunlar soni kiritiladi. Keyingi \(2×N+1\) qatorda \(4×M+1\) tadan UTF-16 belgilari berilib labirint tasvirlanadi. Labirintning chekka qismi har doim yopiq hisoblanadi. \(A\) va \(B\) belgilar labirintning \(N×M\) yacheykalarining ixtiyoriy birida yacheyka markazida joylashganligi kafolotlanadi.
Chiqish faylida labirintda \(A\) nuqtadan \(B\) nuqtaga boradigan yo’lni misollarda ko’rsatilgan shaklda tasvirlang.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
8 8 ┌───┬───────────────────┬───────┐ │ A │ │ │ │ ╵ ┌───────────┐ ├───╴ │ │ │ │ │ │ ├───────┴───────╴ │ ╵ ╷ │ │ │ │ │ │ ╷ ┌───────┐ ├───────┤ │ │ │ │ B │ │ │ │ ├───┘ │ ╶───┤ │ ╷ │ │ │ │ │ │ │ │ │ │ ╶───┴───┐ ╵ └───┘ │ │ │ │ │ │ │ ╶───┐ ├───────────────┘ │ │ │ │ │ ├───╴ │ ╵ ╶───────────────┤ │ │ │ └───────┴───────────────────────┘ |
┌───┬───────────────────┬───────┐ │ A │ ┌───────────────┐ │ │ │ ╷ ╵ │ ┌───────────┐ │ ├───╴ │ │ └───┘ │ │ │ │ ┌───┐ │ ├───────┴───────╴ │ │ ╵ │ ╷ │ │ │ ┌───────────┐ │ └───┘ │ │ │ │ ╷ │ ┌───────┐ │ ├───────┤ │ │ │ │ │ │ ┌─╴ B │ │ │ │ │ │ ├───┘ │ │ │ ╶───┤ │ │ ╷ │ │ │ │ ┌───┘ │ └───┐ │ │ │ │ │ │ │ │ │ ╶───┴───┐ │ ╵ │ └───┘ │ │ │ │ └───────┐ │ └───┘ │ │ │ │ ╶───┐ │ ├───────────────┘ │ │ │ │ │ │ ┌───────────────┘ │ ├───╴ │ │ ╵ │ ╶───────────────┤ │ │ └───┘ │ └───────┴───────────────────────┘ |
| 2 |
8 8 ┌───┬───────────────────┬───────┐ │ A │ │ │ │ ╵ ┌───────────┐ ├───╴ │ │ │ │ │ │ ├───────┴───────╴ │ ╵ ╷ │ │ │ │ │ │ ╷ ┌───────┐ ├───────┤ │ │ │ │ │ │ │ │ ├───┘ │ ╶───┤ │ ╷ │ │ │ │ │ │ │ │ │ │ ╶───┴───┐ ╵ └───┘ │ │ │ │ │ │ │ ╶───┐ ├───────────────┘ │ │ │ │ │ ├───╴ │ ╵ ╶───────────────┤ │ │ B │ └───────┴───────────────────────┘ |
┌───┬───────────────────┬───────┐ │ A │ ┌───────────────┐ │ │ │ ╷ ╵ │ ┌───────────┐ │ ├───╴ │ │ └───┘ │ │ │ │ ┌───┐ │ ├───────┴───────╴ │ │ ╵ │ ╷ │ │ │ │ └───┘ │ │ │ │ ╷ ┌───────┐ ├───────┤ │ │ │ │ │ │ │ │ │ │ ├───┘ │ ╶───┤ │ ╷ │ │ │ │ │ │ │ │ │ │ │ │ ╶───┴───┐ ╵ └───┘ │ │ │ │ │ │ │ │ │ ╶───┐ ├───────────────┘ │ │ │ │ │ ┌───────────────┘ │ ├───╴ │ ╵ │ ╶───────────────┤ │ │ └─────────────╴ B │ └───────┴───────────────────────┘ |
| 3 |
4 3 ┌───────┬───┐ │ B │ │ ├───╴ │ │ │ │ │ │ ┌───┘ │ │ │ A │ │ └───╴ │ │ │ └───────────┘ |
┌───────┬───┐ │ B ╶─┐ │ │ ├───╴ │ │ │ │ ┌───┘ │ │ │ │ ┌───┘ │ │ │ │ A ╶─┐ │ │ │ └───╴ │ │ │ └───────┘ │ └───────────┘ |
| 4 |
13 8 ┌───┬───────┬───────────┬───────┐ │ │ │ │ │ │ ╵ ╷ │ ┌───╴ │ ╷ │ │ │ │ │ │ │ │ ├───────┤ ╵ │ ╶───┤ │ │ │ │ │ │ │ │ │ ╷ └───────┴───┐ ╵ │ │ │ │ A │ │ │ │ ├───────┬───┐ └───────┤ │ │ │ │ │ │ │ │ ╵ ╷ ╵ │ ╶───────┤ │ │ │ │ │ │ ├───────┴───┐ ├───────┐ ╵ │ │ │ │ │ │ │ ╶───┐ │ └───╴ ├───────┤ │ │ │ │ │ │ ╷ │ ├───────┐ ╵ ╷ │ │ │ │ │ B │ │ │ │ │ │ ╵ ┌───┴───────┤ │ │ │ │ │ │ │ ├───┘ ├───────┘ ╷ ╶───┘ │ │ │ │ │ │ ╶───┤ ┌───────┴───────┬───┤ │ │ │ │ │ │ ╷ ╵ └───────╴ ╷ ╵ │ │ │ │ │ └───┴───────────────────┴───────┘ |
┌───┬───────┬───────────┬───────┐ │ │ │ │ │ │ ╵ ╷ │ ┌───╴ │ ╷ │ │ │ │ │ │ │ │ ├───────┤ ╵ │ ╶───┤ │ │ │ ┌───┐ │ │ │ │ │ │ │ ╷ │ └───────┴───┐ ╵ │ │ │ │ │ └─╴ A │ │ │ │ │ ├───────┬───┐ └───────┤ │ │ │ │ ┌───┐ │ │ │ │ │ │ ╵ │ ╷ │ ╵ │ ╶───────┤ │ │ └───┘ │ └───┐ │ │ │ ├───────┴───┐ │ ├───────┐ ╵ │ │ ┌───────┐ │ │ │ │ │ │ │ ╶───┐ │ │ │ └───╴ ├───────┤ │ └───┐ │ │ │ └───────┐ │ ┌───┐ │ │ ╷ │ │ │ ├───────┐ │ ╵ │ ╷ │ │ │ │ │ │ │ │ B │ └───┘ │ │ │ │ │ │ │ │ ╵ ╷ ┌───┴───────┤ │ │ │ │ │ │ └───┘ │ ┌───┐ │ │ │ ├───┘ │ ├───────┘ │ ╷ │ ╶───┘ │ │ │ ┌───┘ │ ┌───────┘ │ └───────┘ │ │ │ ╶───┤ │ ┌───────┴───────┬───┤ │ └───┐ │ │ │ │ │ │ ╷ │ ╵ │ └───────╴ ╷ ╵ │ │ │ └───┘ │ │ └───┴───────────────────┴───────┘ |
B. Gugurt donalari va raqamlar №2
Xotira: 16 MB, Vaqt: 1000 ms
Yuqoridagi rasmda har bir raqamni gugurt donalari yordamida ifodalanishi ko’rsatilgan.
Kirish faylida bitta butun son beriladi, \(N (2 \le N \le 10^6)\)
N ta gugurt donasidan foydalanib hosil qilish mumkin bo'lgan eng kichik nomanfiy butun sonni toping(hosil qilingan sonda ortiqcha 0 lar bo'lmasligi shart).
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 |
2 |
| 2 |
8 |
10 |
C. Satr
Xotira: 16 MB, Vaqt: 1000 msQuyidagi shartlarni qanoatlantiruvchi S satrlar sonini toping:
- S satr uzunligi N ga teng;
- S satr elementlari faqatgina s,a,t,r harflaridan iborat;
- S satrdagi s harfi juft marotaba qatnashgan;
- S satrdagi t harfi juft marotaba qatnashgan.
DIQQAT: juft marotaba qatnashish deganda 0 marotaba qatnashish ham inobatga olinadi.
n=1 da S satr a yoki r bo`lishi mumkin. Ya`ni yuqoridagi shartlarni qanoatlantiruvchi 2 ta satr mavjud.
n=2 bo`lganda S satr quyidagilar bo’lishi mumkin ss, tt, ra, ar, aa, rr.
Demak n=2 da S satrlar soni 6 ta.
Kirish faylida bitta natural son N(1 ≤ N ≤ 109) kiritiladi.
Chiqish fayliga berilgan shartni qanoatlantiruvchi S satrlar sonining 109+7 ga bo’lgandagi qoldig’ini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 |
2 |
| 2 |
2 |
6 |
D. Kriptoqofiya
Xotira: 16 MB, Vaqt: 1000 ms\(\overline{sinus} + \overline{sinus} + \overline{kosinus} = \overline{tangens}\)
Yuqoridagi formuladagi har bir belgi qaysidir bir raqamni ifodalaydi, bir xil belgilar bir xil raqamni ifodalaydi, har xil belgilar har xil raqamni ifodalaydi. Sizga belgi beriladi, siz berilgan belgi yuqoridagi formulada qaysi raqamni ifodalashini aniqlang
Kirish faylida \(\{s,i,n,u,k,o,t,a,g,e\}\) belgilar to’plamidan bitta belgi kiritiladi.
Chiqish faylida kiritilgan belgi qaysi raqamni ifodalashini aniqlang.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
s |
5 |
E. O'rin almashtirishlar
Xotira: 16 MB, Vaqt: 1000 msA to'plam \(\{0, 1, \dots, n-1\}\) to'plam o'rin almashtirishidan hosil bo'lgan ixtiyoriy ketma-ketlik bo'lsin.
\(\displaystyle F(A) = \sum_{i=0}^{n-1}(A_i + A_{(i+1)\%n})^2\)
F(A) ning qabul qiladigan qiymatlar to'plami uzunligini aniqlang.
Misol uchun \(n=4\) da
\(A= \{0,1,2,3\} \space bo’lganda \space F(A) = 44 \\ A= \{0,1,3,2\} \space bo’lganda \space F(A) = 46 \\ A=\{0,2,1,3\} \space bo’lganda \space F(A) = 38 \\ A=\{0,2,3,1\} \space bo’lganda \space F(A) = 46 \\ A=\{0,3,1,2\} \space bo’lganda \space F(A) = 38 \\ \dots\)
\(A\) to’plamning har qanday ketma-ketligida \(F(A)\) ning qabul qiladigan qiymatlar to’plami \(\{38, 44, 46\}\)
Kirish faylida yagona butun son, \(n \space(1 ≤ n ≤ 10^6)\) soni kiritiladi.
Chiqish faylida yagona butun son, \(F(A)\) ning qabul qiladigan qiymatlar to'plami uzunligini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 |
1 |
| 2 |
4 |
3 |
F. Rekordlar soni
Xotira: 16 MB, Vaqt: 1000 msMarjona kollejning basketbol jamoasida o’ynaydi. Har bir o’yinda u o’zining jamoasi jamg’argan ballarni yozib boradi. U o’z jamoasining o’yinlardagi natijalaridan eng katta va eng kichik ballardagi rekordi necha marotaba almashganligini sanab oldi. Eng birinchi o’yindagi ball dastlabki rekord sifatida belgilanadi, keying o’yinlardagi record almashgani sanab boriladi.
Misol uchun uning jamoasi jamg’argan ballar = \(\{10,5,20,20,4,5,2,25,1\}\)
|
O’yin tartib raqami |
O’yindagi ball |
Minimal rekord |
Maksimal rekord |
Minimal rekordning o’zgarishlar soni |
Maksimal rekordning o’zgarishlar soni |
|
1 |
10 |
10 |
10 |
0 |
0 |
|
2 |
5 |
5 |
10 |
1 |
0 |
|
3 |
20 |
5 |
20 |
1 |
1 |
|
4 |
20 |
5 |
20 |
1 |
1 |
|
5 |
4 |
4 |
20 |
2 |
1 |
|
6 |
5 |
4 |
20 |
2 |
1 |
|
7 |
2 |
2 |
20 |
3 |
1 |
|
8 |
25 |
2 |
25 |
3 |
2 |
|
9 |
1 |
1 |
25 |
4 |
2 |
Berilgan ballardan foydalanib Marjonaning jamoasini maksimal rekordning o’zgarishlar soni va minimal rekordning o’zgarishlar sonini aniqlang
Kiruvchi faylning dastlabki satrida bitta butun son, \(n(1 ≤ n ≤ 1000)\) jami o’yinlar soni, keying qatorda \(n\) ta butun son, \(ball (0 ≤ ball_i ≤ 10^8)\) har bir o’yindagi ballar kiritiladi.
Chiqish faylining yagona satrida bo’sh joy bilan ajratilgan holda ikkita butun son, Marjonaning jamoasini maksimal rekordning o’zgarishlar soni hamda minimal rekordning o’zgarishlar sonini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
9 10 5 20 20 4 5 2 25 1 |
2 4 |
G. Do’st ketma-ketlik
Xotira: 16 MB, Vaqt: 1000 ms\(\begin{Bmatrix} a_n = 2^{2n+1}-2^{n+1}+1 \\ b_n = 2^{2n+1}+2^{n+1}+1 \end{Bmatrix}\)
\(n\) ning ixtiyoriy nomanfiy butun qiymatida bu ikki ketma-ketlikdan aynan bittasi 5 ga qoldiqsiz bo’linadi.
Kirish faylida bitta butun son beriladi, \(n (0 ≤ n ≤ 10^9)\) soni kiritiladi.
Chiqish faylida agar a ning n – hadi 5 ga bo’linsa A harfini, agar b ning n – hadi 5 ga bo’linsa B harfini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
0 |
B |
| 2 |
1 |
A |
H. Ayniyat
Xotira: 16 MB, Vaqt: 1000 ms\(a^{10}+1=0 (mod \space 10)\)
Sizga bitta butun son, \(n\) soni beriladi, siz yuqoridagi ayniyatni qanoatlantiruvchi \(a \space (0 ≤ a ≤ n)\) ning butun qiymatlari sonini aniqlang.
Kirish faylida bitta butun son, \(n \space (0 ≤ n ≤ 10^9)\) soni kiritiladi
Chiqish faylida bitta butun son, masala javobini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
15 |
3 |
| 2 |
42 |
8 |
I. Teng sonli belgilar to’plami
Xotira: 16 MB, Vaqt: 1000 msAgar satrda barcha simvollar bir xil sonda qatnashgan bo’lsa bu satr teng sonli belgilar to’plami deyiladi.
Sizga lotin alifbosining kichik harflaridan tashkil topgan S satri beriladi. Siz bu satrdan ko’pi bilan 1 ta simvolni o’chirgan holda(hech qanday simvol o’chirilmasligi ham mumkin) S satrdan teng sonli belgilar to’plami hosil qilish mumkin yoki yo’qligini aniqlang.
Kirish faylining yagona satrida \(S (1 ≤ |S| ≤ 100000)\) satri kiritiladi.
Chiqish faylining yagona satrida agar S satridan teng sonli belgilar to’plami hosil qilish mumkin bo’lsa YES aks holda NO so’zini chop eting.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
aabbcd |
NO |
| 2 |
aabbccddeefghi |
NO |
| 3 |
abcdefghhgfedecba |
YES |