A. So'z o'yini

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Uch nafar do'st — Ali, Vali va Vohid — qiziqarli so'z o'yini o'ynashmoqda. O'yin qoidasi oddiy: birinchi o'yinchi ixtiyoriy so'z aytadi, ikkinchi o'yinchi birinchi o'yinchining so'zi oxirgi harfi bilan boshlanadigan so'z aytishi kerak, uchinchi o'yinchi esa ikkinchi o'yinchining so'zining oxirgi harfi bilan boshlanadigan so'z aytishi kerak.

Ularning o'ynagan so'zlarini ko'rib, o'yin to'g'ri o'ynalganligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda uchta so'z \( a \), \( b \) va \( c \) beriladi — mos ravishda birinchi, ikkinchi va uchinchi o'yinchining so'zlari.

Har bir so'z faqat kichik lotin harflaridan iborat bo'lib, uzunligi \( 1 \le |s| \le 100 \) ga teng.

Chiquvchi ma'lumotlar:

Agar o'yin qoidalarga muvofiq to'g'ri o'ynalgan bo'lsa, "Yes" chop eting, aks holda "No" chop eting.

Izoh:

Birinchi testda: "olma" so'zining oxirgi harfi 'a', "anor" so'zi 'a' harfi bilan boshlanadi — to'g'ri. "anor" so'zining oxirgi harfi 'r', "rezavor" so'zi 'r' harfi bilan boshlanadi — to'g'ri. Shuning uchun javob "Yes".

Ikkinchi testda: "kitob" so'zining oxirgi harfi 'b', lekin "daftar" so'zi 'd' harfi bilan boshlanadi — noto'g'ri. Shuning uchun javob "No".

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
olma anor rezavor
 
Yes
2 
kitob daftar ruchka
 
No

B. Tog'ri to'rtburchak yasash

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Tekislikda to‘g‘ri to‘rtburchak shaklidagi panjara chizilgan. Panjara gorizontal va vertikal kesmalardan iborat bo‘lib, barcha kesmalar teng uzunlikda.

Panjara quyidagicha berilgan:

  • balandligi bo‘yicha \(n\) ta bo‘lak,
  • eni bo‘yicha \(m\) ta bo‘lak.

Har bir bo‘lak chegarasi kesmalar orqali hosil qilinadi va qo‘shni bo‘laklar umumiy kesmalarni bo‘lishadi.

Sizning vazifangiz — ushbu panjarani chizish uchun kerak bo‘ladigan jami kesmalar sonini topish.

Kiruvchi ma'lumotlar:

Yagona qatorda \(n,m(1 \le n,m \le 10^9)\) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Chizilgan to'g'ri to'rtburchakda nechta kesma borligini chiqaring.

Izoh:

Birinchi test uchun na'muna:

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
10 20
 
430

C. Teng Qismlar

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Aziz \(n\) ta butun sondan iborat massivga ega. U massivni aniq ikkita bo'sh bo'lmagan ketma-ket qismlarga bo'lishni xohlaydi, shunday qilib birinchi qismning elementlari yig'indisi ikkinchi qismning elementlari yig'indisiga teng bo'lsin.

Agar bunday bo'lish mavjud bo'lsa, bo'linish nuqtasini (ya'ni birinchi qismning oxirgi elementi indeksini) chop eting. Agar bir nechta javob mavjud bo'lsa, eng kichigini chop eting. Agar bunday bo'lish mavjud bo'lmasa, \(-1\) chop eting.

 

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(n\) \((2 \le n \le 2 \cdot 10^5)\) — massiv uzunligi. Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) \((-10^9 \le a_i \le 10^9)\) — massiv elementlari.

 

Chiquvchi ma'lumotlar:

Bitta butun son — bo'linish nuqtasi (1-indeksdan boshlab), yoki \(-1\).

Izoh:

Birinchi misolda massivni \([1, 3]\) va \([2, 2]\) qilib bo'lish mumkin. Ikkala qismning yig'indisi \(4\) ga teng. Bo'linish 2-indeksdan keyin amalga oshiriladi.

Ikkinchi misolda umumiy yig'indi \(7\) ga teng bo'lib, u toq son. Shuning uchun hech qanday bo'linish yig'indilarni teng qilmaydi.

Uchinchi misolda massivni \([5]\) va \([5]\) qilib bo'lish mumkin. Ikkala qismning yig'indisi \(5\) ga teng.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
1 3 2 2
 
2
2 
3
1 2 4
 
-1
3 
2
5 5
 
1

D. Raqam Soni

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Matematika o'qituvchisi Hamid aka darsda o'quvchilarga qiziqarli topshiriq berdi. U taxtaga \(l\) dan \(r\) gacha bo'lgan barcha butun sonlarni ketma-ket yozdi. Endi u o'quvchilardan taxtadagi barcha sonlarda \(k\) raqami necha marta uchrashini sanashni so'radi.

Sinfda hamma xiralashib qoldi. Siz ularning yordamiga kelishingiz mumkinmi?

Kiruvchi ma'lumotlar:

Birinchi va yagona qatorda uchta butun son \(l\), \(r\) va \(k\) beriladi.

\(-10^5 \le l \le r \le 10^5\)

\(0 \le k \le 9\)

Manfiy sonlar uchun minus belgisi hisobga olinmaydi, faqat raqamlar sanaladi.

Chiquvchi ma'lumotlar:

\(k\) raqami taxtada necha marta uchraganini chop eting.

Izoh:

1-test holatida \(-3\) dan \(12\) gacha yozilgan sonlar: -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Bu sonlardagi 1 raqamlari: -1 da bitta, 1 da bitta, 10 da bitta, 11 da ikkita, 12 da bitta — jami 6 ta.

2-test holatida 0 dan 20 gacha yozilgan sonlardagi 0 raqamlari: 0 da bitta, 10 da bitta, 20 da bitta — jami 3 ta.

3-test holatida \(-15\) dan \(-10\) gacha yozilgan sonlar: -15, -14, -13, -12, -11, -10. Bu sonlardagi 1 raqamlari: 15 da bitta, 14 da bitta, 13 da bitta, 12 da bitta, 11 da ikkita, 10 da bitta — jami 7 ta.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
-3 12 1
 
6
2 
0 20 0
 
3
3 
-15 -10 1
 
7

E. Rasm Kodlash

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Rasmlar juda ko'p xotira egallashi mumkin, shuning uchun rasmlarni siqish usullari ixtiro qilingan. Bu masalada siz nisbatan oddiy kodlashni ochib, asl rasmni tiklashingiz kerak.

Bu yerda barcha rasmlar qora-oq bo'lib, qora piksellar X belgisi, oq piksellar esa . (nuqta) belgisi bilan ifodalanadi. Kodlash qoidasi oddiy: chapdan boshlab ketma-ket oq belgilar soni yoziladi. Bu son 0 dan 9 gacha bo'ladi — agar 9 tadan ko'p bo'lsa, keyingi belgilar alohida kodlanadi va ular oldiga _ belgisi qo'yiladi, bu davom etishini bildiradi. Keyin xuddi shunday tarzda ketma-ket qora belgilar soni yoziladi.

Sizning vazifangiz — kodlangan ma'lumotni ochib, asl rasmni chop etish.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(C\) va \(L\) bo'sh joy bilan ajratilgan holda beriladi. \(C\) (\(0 < C \le 100\)) — qatordagi belgilar soni, \(L\) (\(0 < L \le 50\)) — rasmdagi qatorlar soni.

keyingi \(L\) ta qatorda, ularning har biri o'sha qatordagi belgilarni ifodalovchi bir xonali raqamlar ketma-ketligidan iborat. _ belgisi 9 tadan ko'p ketma-ket bir xil belgilar bo'lgan joyda ishlatiladi (yuqoriga qarang). Raqamlar yig'indisi \(C\) ga teng bo'ladi.

Chiquvchi ma'lumotlar:

Kirishda berilgan rasmni dekodlab ekranga chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
20 22
9_9_2
9_9_2
419_6
329_6
21119_6
519_5
619_4
719_3
819_2
983
9211124
911111114
9211124
911111114
974
91514
91514
91514
91514
91514
9_9_2
9_9_2
 
....................
....................
....X...............
...XX...............
..X.X...............
.....X..............
......X.............
.......X............
........X...........
.........XXXXXXXX...
.........XX.X.XX....
.........X.X.X.X....
.........XX.X.XX....
.........X.X.X.X....
.........XXXXXXX....
.........X.....X....
.........X.....X....
.........X.....X....
.........X.....X....
.........X.....X....
....................
....................

F. So'z o'yini - 2

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Uch nafar do'st — Ali, Vali va Vohid — qiziqarli so'z o'yini o'ynashmoqda. O'yin qoidasi oddiy: birinchi o'yinchi ixtiyoriy so'z aytadi, ikkinchi o'yinchi birinchi o'yinchining so'zi oxirgi ikki harfi bilan boshlanadigan so'z aytishi kerak, uchinchi o'yinchi esa ikkinchi o'yinchining so'zining oxirgi ikki harfi bilan boshlanadigan so'z aytishi kerak.

Ularning o'ynagan so'zlarini ko'rib, o'yin to'g'ri o'ynalganligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda uchta so'z \( a \), \( b \) va \( c \) beriladi — mos ravishda birinchi, ikkinchi va uchinchi o'yinchining so'zlari.

Har bir so'z faqat kichik lotin harflaridan iborat bo'lib, uzunligi \( 2 \le |s| \le 100 \) ga teng.

Chiquvchi ma'lumotlar:

Agar o'yin qoidalarga muvofiq to'g'ri o'ynalgan bo'lsa, "Yes" chop eting, aks holda "No" chop eting.

Izoh:

Birinchi testda: "olma" so'zining oxirgi ikki harfi 'ma', "malika" so'zi 'ma'  bilan boshlanadi — to'g'ri. "malika" so'zining oxirgi ikki harfi 'ka', "kamalak" so'zi 'ka'  bilan boshlanadi — to'g'ri. Shuning uchun javob "Yes".

Ikkinchi testda: "kitob" so'zining oxirgi ikki harfi 'ob', lekin "daftar" so'zi 'da'  bilan boshlanadi — noto'g'ri. Shuning uchun javob "No".

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
olma malika kamalak
 
Yes
2 
kitob daftar ruchka
 
No

G. FizzBuzz Hisobi

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Siz FizzBuzz o'yinini yaxshi bilasiz. 1 dan \( N \) gacha bo'lgan sonlarni ketma-ket aytasiz, lekin:

- agar son \( 3 \) ga bo'linadigan bo'lsa, o'rniga "Fizz" deysiz,
- agar son \( 5 \) ga bo'linadigan bo'lsa, o'rniga "Buzz" deysiz,
- agar son \( 15 \) ga bo'linadigan bo'lsa (ya'ni ham \( 3 \), ham \( 5 \) ga), o'rniga "FizzBuzz" deysiz.

Diqqat: agar son \( 15 \) ga bo'linsa, u faqat "FizzBuzz" hisoblanadi — "Fizz" ham, "Buzz" ham hisoblanmaydi.

\( N \) berilganda, nechta marta "Fizz", nechta marta "Buzz" va nechta marta "FizzBuzz" deganingizni toping.

Kiruvchi ma'lumotlar:

Birinchi va yagona qatorda bitta butun son \( N \) beriladi.

\( 1 \le N \le 10^9 \)

Chiquvchi ma'lumotlar:

Bitta qatorda uchta butun son chop eting: "Fizz" aytilgan marta soni, "Buzz" aytilgan marta soni va "FizzBuzz" aytilgan marta soni (probel bilan ajratilgan holda).

Izoh:

1-test uchun: \( N = 15 \).
Fizz: 3, 6, 9, 12 — 4 ta 
Buzz: 5, 10 — 2 ta 
FizzBuzz: 15 — 1 ta .

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
15
 
4 2 1
2 
100
 
27 14 6
3 
2
 
0 0 0

H. Juft Shirinlik

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Anvarning \(n\) ta konfeti bor. Har bir konfetning shirinlik darajasi \(a_i\) ga teng. Anvar bu konfetlardan aynan ikkitasini tanlab, do'stiga sovg'a qilmoqchi. Lekin Anvarning bitta sharti bor: tanlangan ikki konfetning shirinlik darajalarining yig'indisi juft son bo'lishi kerak.

Anvar sovg'a imkon qadar shirin bo'lishini xohlaydi. Shuning uchun u shartni qanoatlantiradigan barcha juftliklar orasidan yig'indisi eng katta bo'lganini topmoqchi. Agar bunday juftlik umuman mavjud bo'lmasa, (-1) chiqaring.

Eslatma: Ikki sonning yig'indisi juft bo'lishi uchun ikkala son ham juft yoki ikkala son ham toq bo'lishi kerak.

 

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) (\(1 \le t \le 1000)\) — test holatlar soni berilgan.

Har bir test holat ikki qatordan iborat:

  • Birinchi qatorda \(n\) \((1 \le n \le 200,000)\) — konfetlar soni.
  • Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n  (1 \le a_i \le 10^9)\) — har bir konfetning shirinlik darajasi.

Barcha test holatlar bo'yicha \(n\) larning yig'indisi (200,000) dan oshmasligi kafolatlanadi.

 

Chiquvchi ma'lumotlar:

Har bir test holat uchun bitta butun son chiqaring: yig'indisi juft bo'lgan ikki konfetning eng katta yig'indisi. Agar bunday juftlik mavjud bo'lmasa, (-1) chiqaring.

 

Izoh:

Birinchi test holatda: juft sonlar — (2, 4), toq sonlar — (3, 5, 7). Juft juftlik: (2+4=6). Toq juftlik: eng kattasi (7+5=12). Javob: (12).

Ikkinchi test holatda: barcha sonlar toq — (1, 3, 5, 7). Eng katta juftlik: (7+5=12).

Uchinchi test holatda: barcha sonlar juft — (2, 4, 6). Eng katta juftlik: (6+4=10).

To'rtinchi test holatda: (1) toq, (2) juft. Faqat bitta juftlik bor va (1+2=3) — toq. Javob: (-1).

Beshinchi test holatda: faqat bitta konfet bor, ikki konfet tanlash mumkin emas. Javob: (-1).

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
5
2 3 5 7 4
4
1 3 5 7
3
2 4 6
2
1 2
1
5
 
12
12
10
-1
-1

I. Shifr

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Harbiy razvedka bo'limi maxfiy aloqa kanallarini himoya qilish uchun \(4\) raqamli shifrlash tizimidan foydalanadi. Tizim quyidagicha ishlaydi:

Dastlab \(4\) ta maxfiy son \((a_1, a_2, a_3, a_4)\) tanlanadi. Har bir tsiklda sonlar bir vaqtning o'zida quyidagi qoida bo'yicha almashtiriladi:

\((a_1, a_2, a_3, a_4) \to (|a_1 - a_2|,\; |a_2 - a_3|,\; |a_3 - a_4|,\; |a_4 - a_1|)\)

Bu jarayon barcha sonlar nolga aylangunicha, ya'ni \((0, 0, 0, 0)\) holatiga yetguncha takrorlanadi. \(4\) ta son uchun bu jarayon har doim tugashi kafolatlangan.

Razvedka ofitseri shifrlash tizimini tahlil qilmoqda: berilgan boshlang'ich \(4\) ta son uchun, necha tsiklda barcha sonlar nolga aylanishini aniqlash kerak.

Kiruvchi ma'lumotlar:

Bitta qatorda \(4\) ta butun son beriladi: \(a_1, a_2, a_3, a_4\)   \((1 \le a_i \le 10^6)\)

Chiquvchi ma'lumotlar:

Bitta butun son — barcha sonlar \((0, 0, 0, 0)\) ga aylanishi uchun kerak bo'lgan tsikllar soni.

Izoh:

1-misol

\( (5, 2, 8, 1) \to (3, 6, 7, 4) \to (3, 1, 3, 1) \to (2, 2, 2, 2) \to (0, 0, 0, 0)\). Jami\(4\) tsikl.

2-misol

\((7, 7, 7, 7) \to (0, 0, 0, 0)\). Jami \(1\) tsikl.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 2 8 1
 
4
2 
7 7 7 7
 
1

J. Lampalar

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Bobur qorong'i xonada \(n\) ta lampa qatoriga ega. Har bir lampa dastlab yoniq \((1)\) yoki o'chiq \((0)\) holatda bo'ladi.

Har soniyada quyidagi jarayon sodir bo'ladi: agar o'chiq lampaning kamida bitta qo'shnisi (chapda yoki o'ngda turgan lampa) yoniq bo'lsa, u ham yonib ketadi. Yoniq lampalar yoniq bo'lib qolaveradi.

\(k\) soniya o'tgandan keyin nechta lampa yoniq bo'ladi?

 

Kiruvchi ma'lumotlar:

Birinchi qatorda \(t\) \((1 \le t \le 10^4)\) — testlar soni beriladi.

Har bir test uchun:

Birinchi qatorda \(n\) va \(k\) \((1 \le n \le 2 \cdot 10^5), (0 \le k \le 2 \cdot 10^5)\) — lampalar soni va soniyalar soni.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) \((a_i \in {0, 1})\) — lampalarning boshlang'ich holati. \(1\) yoniq, \(0\) o'chiq.

Barcha testlar bo'yicha \(n\) larning yig'indisi \(2 \cdot 10^5\) dan oshmasligi kafolatlanadi.

 

Chiquvchi ma'lumotlar:

Har bir test uchun bitta butun son — \(k\) soniyadan keyin yoniq lampalar soni.

Izoh:

Birinchi testda: dastlab lampalar holati [1, 0, 0, 0, 1]. \(1\) soniya o'tgandan keyin, \(1\)-lampa \(2\)-lampani yoqadi (chapdan qo'shni), va \(5\)-lampa \(4\)-lampani yoqadi (o'ngdan qo'shni). Natija: [1, 1, 0, 1, 1] — \(4\) ta yoniq lampa.

Ikkinchi testda: hech qanday lampa yoniq emas, shuning uchun hech narsa yonmaydi. Javob \(0\).

Uchinchi testda: dastlab [0, 1, 0, 0, 1, 0]. \(1\) soniyadan keyin \(2\)-lampa \(1\)- va \(3\)-lampalarni yoqadi, \(5\)-lampa \(4\)- va \(6\)-lampalarni yoqadi. Natija: [1, 1, 1, 1, 1, 1] — \(6\) ta yoniq lampa.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
5 1
1 0 0 0 1
4 2
0 0 0 0
6 1
0 1 0 0 1 0
 
4
0
6

K. Ping Pong Bumm

Xotira: 256 MB, Vaqt: 1000 ms
Masala

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.

Kiruvchi ma'lumotlar:

Birinchi va yagona qatorda butun son \( N \) beriladi.

\( 1 \le N \le 10^9 \)

Chiquvchi ma'lumotlar:

Uchta butun sonni chop eting — mos ravishda "ping", "pong" va "bumm" deyilgan sonlar soni.

Izoh:

1-test uchun ( \( N = 28 \) ):
4, 8, 12, 16, 20, 24 — "ping" (6 ta)
7, 14, 21 — "pong" (3 ta)
28 — "bumm" (1 ta)
Javob: 6 3 1

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
28
 
6 3 1
2 
100
 
22 11 3
3 
2
 
0 0 0

L. Shifr Jadvali

Xotira: 256 MB, Vaqt: 1000 ms
Masala

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.

Kiruvchi ma'lumotlar:

Kirish bir nechta jadvallardan iborat. Har bir jadval birinchi qatorda \(S\) soni bilan boshlanadi — jadvalning o'lchami \((10 \le S \le 20)\)

Keyin \(S\) ta qator keladi, har birida \(S\) ta butun son bo'lib, ular bo'sh joy bilan ajratilgan. Har bir son \(0\) dan \(26\) gacha. \(0\) — bloklangan katak, \(1-26\) — shifr kodi.

\(S = 0\) bo'lsa, kirishning oxiri — bu jadvalni qayta ishlamang.

Chiquvchi ma'lumotlar:

Har bir jadval uchun bitta qator chiqaring:

- Tasdiqlandi — agar barcha \(26\) ta kod kamida bir marta ishlatilgan bo'lsa

- Rad etildi — aks holda

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
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

M. Sehrli Kartalar

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Dilnoza \(n\) ta kartani ketma-ket qatorga yoydi. Har bir kartaning ustida musbat butun son yozilgan.

Dilnoza \(i\)-kartani "oltin" deb ataydi, agar quyidagi shartlardan biri bajarilsa:

  • \(i = 1\) bo'lsa (ya'ni karta birinchi bo'lsa), yoki
  • \(a_i > a_1 + a_2 + \ldots + a_{i-1}\) bo'lsa (ya'ni kartadagi son, undan oldingi barcha kartalardagi sonlar yig'indisidan qat'iy katta bo'lsa).

Dilnoza nechta oltin karta borligini bilmoqchi. Unga yordam bering!

Kiruvchi ma'lumotlar:

Birinchi qatorda \(n\) — kartalar soni \((1 \le n \le 2 \cdot 10^5)\) beriladi.

Ikkinchi qatorda \(n\) ta musbat butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).

Chiquvchi ma'lumotlar:

Bitta butun son — oltin kartalar sonini chiqaring.

Izoh:

1-misol: \(n = 5\), kartalar: \([3,\ 5,\ 2,\ 11,\ 4]\).

  • \(1\)-karta: \(3\) — birinchi karta, shuning uchun oltin ✓
  • \(2\)-karta: \(5\) — oldingi yig'indi \(= 3\), \(5 > 3\) — oltin ✓
  • \(3\)-karta: \(2\) — oldingi yig'indi \(= 3+5 = 8\), \(2 > 8\)? — yo'q ✗
  • \(4\)-karta: \(11\) — oldingi yig'indi \(= 3+5+2 = 10\), \(11 > 10\) — oltin ✓
  • \(5\)-karta: \(4\) — oldingi yig'indi \(= 3+5+2+11 = 21\), \(4 > 21\)? — yo'q ✗

Jami oltin kartalar: \(3\).

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
3 5 2 11 4
 
3
2 
4
1 2 4 8
 
4

N. Front Qurollari

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Harbiy bazada front chizig'iga qurollar jo'natish uchun maxsus koridor mavjud. Koridorda uch turdagi qurollar ketma-ket joylashgan:

 Tur 0: Pistol (yengil qurol)
 Tur 1: Avtomat (o'rta qurol)
 Tur 2: Pulemyot (og'ir qurol)

General koridordan o'tib, qurollarni frontga jo'natish tartibini belgilaydi. Qoidalar quyidagicha:

- Agar general pistolni (0) ko'rsa, u shunchaki davom etadi.
- Agar general avtomatni (1) ko'rsa, u orqaga qaytib, shu avtomatdan oldin turgan barcha pistollarni (0) frontdan olib tashlaydi (ular yetarlicha kuchli emas). Keyin avtomatning yoniga qaytib, yo'lida davom etadi. Avtomatning o'zi qoladi.
- Agar general pulemyotni (2) ko'rsa, u orqaga qaytib, shu pulemyotdan oldin turgan barcha pistollar (0) va avtomatlarni (1) frontdan olib tashlaydi. Keyin pulemyotning yoniga qaytib, yo'lida davom etadi. Pulemyotning o'zi qoladi.

General koridordan o'tib bo'lgach, frontda qolgan qurollar turlarini tartib bilan chiqaring.
 

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son N — koridordagi qurollar soni.
Ikkinchi qatorda N ta butun son — qurollarning turlari (0, 1 yoki 2), ketma-ketlikda.

\(1 \le N \le 10^5\)
Har bir element \({0, 1, 2}\) to'plamdan.
 

Chiquvchi ma'lumotlar:

Frontda qolgan qurollar turlarini tartib bilan, bo'sh joy bilan ajratib chiqaring.
 

Izoh:

Birinchi test uchun izoh.

- 0 (pistol) kiradi.
- 1 (avtomat) keladi → oldidagi pistolni (0) olib tashlaydi. Qoldi: [1]
- 2 (pulemyot) keladi → oldidagi avtomatni (1) olib tashlaydi. Qoldi: [2]
- 2 (pulemyot) keladi. Oldida faqat pulemyot bor, hech narsa olib tashlanmaydi. Qoldi: [2, 2]
- 0 (pistol) kiradi. Qoldi: [2, 2, 0]
- 1 (avtomat) keladi → oldidagi pistolni (0) olib tashlaydi. Qoldi: [2, 2, 1]
- 1 (avtomat) keladi. Oldida avtomat bor, hech narsa olib tashlanmaydi. Qoldi: [2, 2, 1, 1]
- 0, 0 (pistollar) kiradi. Qoldi: [2, 2, 1, 1, 0, 0]
 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
9
0 1 2 2 0 1 1 0 0
 
2 2 1 1 0 0

O. Mudofaa Kengashi

Xotira: 256 MB, Vaqt: 1000 ms
Masala

O'zbekiston Mudofaa kengashi yangi zobitlar to'plamini shakllantirmoqda. Har bir nomzod xizmat tajribasi va jangovar mahoratiga qarab quyidagi ikki unvondan biriga tayinlanadi:

- Mayor — tajribali, yuqori malakali zobit

- Leytenant — yosh yoki tajribasi yetarli bo'lmagan zobit

Mayor unvonini olish uchun nomzod quyidagi ikkala shartni bir vaqtda qanoatlantirishi kerak:

- yoshi kamida \(55\) bo'lishi kerak

- jangovar mahorat darajasi kamida \(8\) bo'lishi kerak

Mudofaa kengashida mahorat darajasi \(-2\) dan \(26\) gacha bo'lgan shkala bo'yicha belgilanadi. 

Agar shartlardan kamida bittasi bajarilmasa, nomzodga Leytenant unvoni beriladi.

Har bir nomzodning ma'lumotlari asosida unga beriladigan unvonni aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(N\) beriladi — nomzodlar soni.

Keyingi \(N\) qatorda har birida ikkita butun son beriladi: \(A\) va \(H\) — nomzodning yoshi va jangovar mahorat darajasi.

- \(1 \le N \le 50\)

- \(1 \le A \le 110\)

- \(-2 \le H \le 26\)

Chiquvchi ma'lumotlar:

Har bir nomzod uchun bitta qatorda Mayor yoki Leytenant so'zini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
18 20
45 2
61 12
58 4
 
Leytenant
Leytenant
Mayor
Leytenant

P. Sensor yo'li

Xotira: 256 MB, Vaqt: 1000 ms
Masala

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.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(n\) (\(2 \le n \le 2 \cdot 10^5\)) beriladi — yozuv uzunligi.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(-10^9 \le a_i \le 10^9\)) beriladi.

Chiquvchi ma'lumotlar:

Agar yozuvni ko'pi bilan bitta elementni almashtirib to'g'ri qilish mumkin bo'lsa, YES chiqaring. Aks holda NO chiqaring.

Izoh:

1-misol uchun: \(7\) ni \(3\) ga almashtirsak, ketma-ketlik \(1, 2, 3, 4, 5\) bo'ladi. Endi barcha qo'shni elementlar farqi \(1\) ga teng.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5
1 2 7 4 5
 
YES
2 
4
1 2 6 7
 
NO
3 
4
4 5 4 3
 
YES

Q. Snayper va harakatlanuvchi nishon

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Maxsus operatsiya vaqtida snayper yashirin pozitsiyada joylashgan. Uning oldida esa harakatlanayotgan nishon bor. Snayper va nishon orasidagi boshlang‘ich masofa D metrga teng.

Operatsiya boshlanishi bilan snayper o‘q uzadi va ayni paytda nishon ham harakatlanishda davom etadi. Har ikkala harakat vaqtga bog‘liq murakkab qonuniyat asosida berilgan.

t soniyadan keyin:

  • Snayper o‘qi bosib o‘tgan masofa quyidagicha:

    \(o_3 * t^3 + o_2 * t^2 + o_1 * t\)

  • Nishon bosib o‘tgan masofa quyidagicha:

    \(m_4 * t^4 + m_3 * t^3 + m_2 * t^2 + m_1 * t\)

Snayper o‘qi va nishon bir-biriga qarama-qarshi yo‘nalishda harakatlanadi va ma’lum bir vaqtda ular bir nuqtada uchrashadi.

Snayper o‘qi va nishon qachon uchrashishini aniqlang, ya’ni shunday t vaqtni topingki:

\(o_3 * t^3 + o_2 * t^2 + o_1 * t + m_4 * t^4 + m_3 * t^3 + m_2 * t^2 + m_1 * t = D\) tenglik to'g'ri bo'lsin.

Kiruvchi ma'lumotlar:
  • Birinchi qatorda bitta butun son beriladi:
    D — snayper va nishon orasidagi boshlang‘ich masofa.
  • Ikkinchi qatorda uchta butun son beriladi:
    o3, o2, o1 — o‘q harakati koeffitsiyentlari.
  • Uchinchi qatorda to‘rtta butun son beriladi:
    m4, m3, m2, m1 — nishon harakati koeffitsiyentlari.

Cheklovlar

  • \(1 ≤ D ≤ 10^9\)
  • \(0 ≤ o1, o2, o3 ≤ 10^6\)
  • \(0 ≤ m1, m2, m3, m4 ≤ 10^6\)
  • Uchrashish vaqti mavjud va yagona deb kafolatlanadi
Chiquvchi ma'lumotlar:
  • Snayper o‘qi va nishon uchrashadigan vaqtni (sekundlarda) chiqaring.
  • Natijani verguldan keyin aniq 2 ta raqam bilan chiqaring.
Izoh:

Vaqt oshgani sari o‘q ham, nishon ham ma’lum masofani bosib o‘tadi. Ular bir nuqtada uchrashganda, ularning bosib o‘tgan masofalari yig‘indisi boshlang‘ich masofaga teng bo‘ladi.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
100
1 2 3
0 1 2 5
 
2.83

R. Deyarli silliq massiv

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Azizbek saralash sohasidagi ko'p yillik tajribasi orqali ikki bosqichli saralash dasturini ishlab chiqdi.

Birinchi bosqich - silliqlash fazasi, ikkinchi bosqich esa - saralash fazasi.

Silliqlash fazasining samaradorligini o'lchash uchun Azizbek silliqlik koeffitsienti tushunchasini kiritgan edi. Endi Azizbek bu tushunchani yanada kengaytirmoqchi.

\( a_1, a_2, \ldots, a_n \) ko'rinishidagi massiv va \( k \geq 0 \) butun son berilgan bo'lsin.

\( a_p, a_{p+1}, \ldots, a_q \) quyi massivi deyarli silliq deyiladi, agar unda

\(p < i \leq q \quad \text{bo'lgan va} \quad a_{i-1} > a_i\)

shartini qanoatlantiruvchi \( i \) indekslar soni \( k \) dan oshmasа - ya'ni pasayish (descent) soni ko'pi bilan \( k \) ta bo'lsa.

Azizbek endi o'zining yangi metrikasini sinab ko'rmoqchi: berilgan massiv va \( k \) parametri asosida eng uzun deyarli silliq qism-massivning (subarray) uzunligini topish kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son \(n\) va \(k\) - massiv uzunligi va koeffitsient kiritiladi.

Keyingi qatorda \(n\) ta butun son - \(a\) massiv elementlari beriladi.

\(0 \le k < n \le 10^5\)

\(1 \le a_i \le 10^9\)

Chiquvchi ma'lumotlar:

Bitta qatorda \( a \) massivining eng uzun deyarli silliq qism-massivining (subarray) uzunligini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
8 1
1 2 1 2 1 2 3 1
 
5
2 
8 2
1 2 1 2 1 2 3 1
 
7
3 
8 0
1 2 1 2 1 2 3 1
 
3

S. Uyg'un Uchlik

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Dizayner \(n\) ta bezak elementi tayyorladi. Har bir elementning \(4\) ta xususiyati bor va har bir xususiyat \(1\), \(2\) yoki \(3\) qiymatini oladi.

Dizayn nazariyasiga ko'ra, uchta element uyg'un uchlik hosil qiladi, agar har bir xususiyat bo'yicha uchala qiymat yoki hammasi bir xil, yoki hammasi farqli bo'lsa. Bu qoida to'liq birlik yoki to'liq kontrast yaratadi.

Agar biror xususiyatda ikkita element bir xil qiymatga ega, lekin uchinchisi farqli bo'lsa — bu vizual nomutanosiblik hosil qiladi va uchlik uyg'un hisoblanmaydi.

Masalan:

- \((1,1,1,1)\), \((1,1,1,2)\), \((1,1,1,3)\) — uyg'un: birinchi uch xususiyat hammasi bir xil, to'rtinchisi hammasi farqli.

- \((1,1,1,1)\), \((1,1,1,2)\), \((2,2,2,2)\) — uyg'un emas: birinchi xususiyatda ikkitasi \(1\), bittasi \(2\).

Berilgan \(n\) ta element ichidan nechta turli uyg'un uchlik tanlash mumkinligini aniqlang.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son \(n\) — elementlar soni. \((1 \le n \le 10^5)\)

Keyingi \(n\) ta qatorda har birida \(4\) ta butun son berilgan — elementning xususiyatlari.

Chiquvchi ma'lumotlar:

Bitta butun son — uyg'un uchliklar soni.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4
1 1 1 1
1 1 1 2
1 1 1 3
2 2 2 2
 
1
2 
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
 
4
Kitob yaratilingan sana: 26-Apr-26 21:56