A. Ping Pong Bumm

Xotira: 256 MB, Vaqt: 1000 ms

Dasturchi Sardor o'zi yozgan maxsus sonlar o'yinini sinovdan o'tkazmoqda. O'yin qoidasi quyidagicha: \( 1 \) dan \( N \) gacha bo'lgan sonlarni ketma-ket ko'rib chiqiladi. Agar son \( 4 \) ga bo'linsa — "ping" deyiladi, agar \( 7 \) ga bo'linsa — "pong" deyiladi, agar \( 28 \) ga bo'linsa esa — "bumm" deyiladi.

Shuni esda tuting: agar son \( 28 \) ga bo'linsa, u faqat "bumm" deb hisoblanadi (ya'ni u "ping" ham, "pong" ham hisobiga qo'shilmaydi). Xuddi shunday, agar son \( 4 \) ga bo'linsa-yu, \( 28 \) ga bo'linmasa — faqat "ping" hisoblanadi. Agar \( 7 \) ga bo'linsa-yu, \( 28 \) ga bo'linmasa — faqat "pong" hisoblanadi.

\( N \) berilganda, nechta marta "ping", "pong" va "bumm" deyilganini toping.

28

6 3 1

100

22 11 3

2

0 0 0

B. Shifr Jadvali

Xotira: 256 MB, Vaqt: 1000 ms

Harbiy razvedka bo'limi maxfiy aloqa uchun shifr jadvali tizimidan foydalanadi. Shifr jadvalida har bir harf \(1\) dan \(26\) gacha bo'lgan son bilan kodlangan. Jadval \(S \times S\) o'lchamli to'rtburchak ko'rinishida bo'lib, ba'zi kataklar bloklangan (qiymati \(0\)).

Shifr jadvali foydalanishga tayyor deb topiladi faqat va faqat unda \(1\) dan \(26\) gacha bo'lgan barcha kodlar kamida bir marta ishlatilgan bo'lsa. Aks holda jadval qayta ishlash uchun kriptografga qaytariladi.

Sizga bir nechta shifr jadvallari beriladi. Har birini tekshirib, natijani aniqlang.

13
1 2 3 1 4 5 6 7 0 0 5 0 7
8 0 9 0 9 0 9 0 7 5 10 11 12
6 9 13 4 11 9 4 12 14 0 11 0 9
2 0 13 0 15 0 4 0 2 0 5 11 15
1 8 15 16 0 17 5 18 15 11 10 0 15
0 0 2 0 17 0 13 0 15 0 0 0 5
19 11 7 2 4 7 0 15 9 6 13 5 6
11 0 0 0 9 0 21 0 12 0 9 0 0
21 0 15 11 13 19 8 7 0 11 15 15 7
13 2 9 0 11 0 9 0 22 0 15 0 2
8 0 23 0 24 9 25 5 8 4 11 13 2
4 2 2 1 16 0 2 0 7 0 2 0 26
2 0 7 0 0 6 4 5 13 2 7 13 7
13
5 7 9 25 20 10 4 0 16 2 16 16 3
21 0 2 0 2 0 13 0 25 0 4 0 7
25 23 23 2 18 0 14 25 26 26 25 11 10
26 0 26 0 12 0 15 0 26 0 5 0 4
26 21 2 13 4 20 10 23 0 15 25 23 20
7 0 0 0 2 0 23 0 9 0 9 0 0
26 19 13 10 25 4 0 1 23 7 10 22 10
0 0 12 0 20 0 25 0 2 0 0 0 8
1 7 4 10 0 5 4 25 16 9 23 25 16
10 0 13 0 17 0 9 0 7 0 25 0 4
6 25 5 5 7 12 10 0 5 25 23 11 2
10 0 24 0 6 0 23 0 25 0 10 0 20
23 21 3 14 10 0 26 16 4 13 23 11 10
0

Rad etildi
Tasdiqlandi

C. Sensor yo'li

Xotira: 256 MB, Vaqt: 1000 ms

Robot har soniyada o'z balandligini yozib boradi. Natijada sizga \(n\) ta son beriladi: \(a_1, a_2, \ldots, a_n\).

Yozuv to'g'ri deb hisoblanadi, agar har bir qo'shni juftlik uchun

\[|a_i - a_{i+1}| = 1\] sharti bajarilsa.

Ma'lum bo'lishicha, sensor ko'pi bilan bitta joyda xato qilgan bo'lishi mumkin. Siz istalgan bitta elementni istalgan butun songa almashtira olasiz. Almashtirmaslik ham mumkin.

Vazifa: yozuvni to'g'ri qilish mumkinmi yoki yo'qligini aniqlang.

5
1 2 7 4 5

YES

4
1 2 6 7

NO

4
4 5 4 3

YES

D. Teskari masala

Xotira: 256 MB, Vaqt: 1000 ms

Dasturlashni endi boshlagan o'quvchilar eng birinchi ishlagan masalasi ikki sonning yig'indisini hisoblash bo'lsa kerak. Bu masalada ushbu masalaning teskarisini topish talab qilinadi, ya'ni butun son \(X\) beriladi, shunday \(A\) va \(B\) ni topingki, yig'indisi \(X\) ga teng bo'lsin. Faqat bir shart bor, \(A\) ning ham, \(B\) ning ham absolyut qiymati \([L, R]\) oralig'ida bo'lishi kerak, boshqacha aytganda, \(L \le |A|, |B| \le R\) bo'lsin. 

6
10 2 8
-15 5 10
0 10 20
100 10 20
1 10 20
0 0 10

5 5
-7 -8
15 -15
impossible
11 -10
0 0

E. Yangi Shahar

Xotira: 256 MB, Vaqt: 1000 ms

Cho'l o'rtasida yangi shahar qurilmoqda. Reja bo'yicha \(n\) ta inshoot qurilishi kerak. Ba'zi inshootlar boshqalariga bog'liq — masalan, suv tarmog'i qurilmagunicha, fontanni o'rnatib bo'lmaydi.

Jami \(m\) ta bog'liqlik berilgan. Har bir bog'liqlik "\(a\) inshoot \(b\) inshoatdan oldin qurilishi shart" degan ma'noni bildiradi. Bog'liqliklar sikl hosil qilmasligi kafolatlangan — ya'ni barcha inshootlarni qurish doimo mumkin.

Bir vaqtda faqat bitta inshoot quriladi. Agar bir nechta inshootning barcha bog'liqliklari bajarilgan bo'lsa, raqami eng kichik bo'lgani birinchi quriladi.

Barcha \(n\) ta inshootni to'g'ri tartibda qurish rejasini tuzing.

4 3
4 1
4 2
4 3

4 1 2 3

5 4
3 1
3 2
5 4
2 4

3 1 2 5 4

F. Kompaniya siri

Xotira: 256 MB, Vaqt: 1000 ms

Sardor katta bir kompaniyaning rahbari bo'lib, u sohadagi yetakchi kompaniya hisoblanadi. Kompaniyaning muvaffaqiyat siri — ichki boshqaruv tizimida. Kompaniyadagi har bir xodimga \(1\) dan \(N\) gacha bo'lgan alohida raqam berilgan bo'lib, har bir xodimning bevosita bo'limi boshlig'i ma'lum (1-raqamli xodim — bu Sardorning o'zi va uning hech qanday boshlig'i yo'q). Xodimlar o'rtasidagi munosabatlar ildizi 1-tugundan boshlanadigan daraxt tuzilmasini hosil qiladi.

Kompaniya xalqaro ko'rgazmaga taklif qilindi. Ko'rgazmada kompaniya ma'lum miqdordagi jamoalar (Sardor tomonidan belgilanadi) bilan qatnashadi, har bir jamoada ikkita xodim bo'ladi. Sardorga jamoalarning soni emas, ularning qiymati muhim. Shu sababli u quyidagi qoidani belgiladi: \(x\) va \(y\) xodimlar jamoani tashkil eta oladi, agar \(x\) — \(y\) ning bevosita rahbari bo'lsa, yoki ikkalasi ham bir xil rahbarga ega bo'lsa. Bunday jamoaning qiymati \(|x - y|\) ga teng. Shuningdek, Sardor (1-raqamli xodim) hech qanday jamoaga kirmaydi — u kompaniya menedjeri sifatida alohida turadi. Jamoalarning umumiy qiymati barcha jamoalar qiymatlarining yig'indisiga teng.

Har bir xodim faqat bitta jamoaga kirishi mumkin.

Shunday jamoalar tarkibini toping-ki, jamoalarning umumiy qiymati maksimal bo'lsin.

5
1
4
2
4

4

G. Muntazam uchburchak

Xotira: 256 MB, Vaqt: 1000 ms

Muntazam uchuburchak bu - hamma tomonlari va burchaklari bir xil bo'lgan uchburchakdir.
Sizga uzunligi 1 ga teng bo'lgan \(n\) ta muntazam uchburchak berilgan. 
Siz berilgan uchburchaklarni birlashtirish orqali nechta turli xil qavariq ko'pburchak yasash mumkinligini topishingiz kerak ? 
Shakllar aylantirilsa yoki akslantirilsa ham bir xil hisoblanadi.

16

5