A. Toshlar o’yini

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Ikki o’yinchi N ta tosh orqali o’yin o’ynayapti. O’yinni birinchi o’yinchi boshlab beradi, va har bir o’yinchi navbati bilan o’z harakatini amalga oshiradi. O’yin quyidagicha o’ynaladi.

  • Navbati kelgan o’yinchi maydonda turgan toshlardan ixtiyoriy birini o’ziga oladi.
  • O’z navbatida tosh ololmagan o’yinchi o’yinda yutqazadi.

O’yinda kim g’olib bo’lishini aniqlang.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylida yagona butun son, N(1 ≤ N ≤ 109) soni kiritiladi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida agar o’yinda birinchi o’yinchi g’olib bo’lsa “First player” aks holda “Second player” so’zini qo’shtirnoqsiz chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
 
Second player
2 
3
 
First player
3 
4
 
Second player

B. Mevalar

Xotira: 16 MB, Vaqt: 1000 ms
Masala

To’g’ri chiziqning \(a\) nuqtasida olma daraxti, \(b\) nuqtasida apelsin daraxti joylashgan. Har bir to’kilgan meva daraxtdan \(d\) masofaga qulaydi, agar \(d\) musbat bo’lsa daraxtdan o’ng tomonga, agar manfoy bo’lsa daraxtdan chap tomonga, nolga teng bo’lsa daraxt ostiga tushganligini ifodalaydi. Mevaxo’r xo’tikchaning uyi \([s,t]\) oraliqda joylashgan. Daraxtlardan to’kilgan har bir meva uchun \(d\) qiymat berilganida xo’tikchaga nasib qiladigan olmalar va apelsinlar sonini toping.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining birinchi satrida \(s\) va \(t\) sonlari kiritiladi. Ikkinchi satrda \(a\) va \(b\) sonlari kiritiladi. Uchinchi satrda \(m\) va \(n\) mos ravishda daraxtdan to’kilgan olmalar va apelsinlar soni kiritiladi. To’rtinchi satrda \(m\) ta olmaning har biri uchun \(d\) qiymatlar kiritiladi. Beshinchi satrda \(n\) ta apelsinning har biri uchun \(d\) qiymatlar kiritiladi. Kiritilgan barcha sonlar butun.

Chegaralar:
\(1 ≤ s, t, a, b, m, n ≤ 10^5\)
\(-10^5 ≤ d ≤ 10^5\)
\(a < s < t < b\)

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylining birinchi satrida xo’tikchaga nasib qilgan olmalar soni, ikkinchi satrida esa xo’tikchaga nasib qilgan apelsinlar sonini chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
7 11
5 15
3 2
-2 2 1
5 -6
 
1
1

C. Matritsani burish

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizda N x M o’lchamli matritsa mavjud. Siz bu matritsa elementlarini K marotaba soat strelkasiga qarshi burganingizda qanday matritsa hosil bo’lishini aniqlang!

Quyida 4x5 o’lchamli matritsaning soat strelkasiga qarshi 1 marotaba buralishida har bir elementning qaysi indeksga o’tishi ko’rsatilgan.

Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida uchta butun son, N, M(2 ≤ N, M ≤ 300, min(N,M)%2==0) va K(1 ≤ K ≤ 109) sonlari bo’sh joy bilan ajratilgan holda kiritiladi. Keyingi N ta satrning har birida M tadan [1, 108] oralig’idagi butun son bo’sh joy bilan ajratilgan holda kiritiladi va bu sonlar matritsaning dastlabki holatini ifodalaydi.

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida kirishda berilgan matritsani K marotaba soat strelkasiga qarshi burganda hosil bo’lgan matritsani chop eting.

Izoh:

1

2

3

4

→

2

3

4

8

→

3

4

8

12

5

6

7

8

1

7

11

12

2

11

10

16

9

10

11

12

5

6

10

16

1

7

6

15

13

14

15

16

9

13

14

15

5

9

13

14
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
 
2 3 4 8
1 7 11 12
5 6 10 16
9 13 14 15
2 
4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
 
3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

D. Insertion sort

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Insertion sort algoritmi oddiy saralash algoritmlari safida turadi. Ba’zida berilgan massivni saralash uchun insertion sort juda ko’p vaqt talab qilishi kuzatiladi. Ammo insertion sortda elementlarni surishlar sonini topishning boshqacha usullari ham mavjud.

Agar k[i] massivning i-elementi siljishi kerak bo’lgan elementlar soni bo’lsa, unda umumiy siljishlar soni k[1]+k[2]+k[3]+…+k[n] ga teng bo’ladi. Misol uchun massiv arr=[4,3,2,1] bo’lsa.

Massiv

Surishlar soni

[4,3,2,1]

 

[3,4,2,1]

1

[2,3,4,1]

2

[1,2,3,4]

3

Umumiy surishlar soni=1+2+3=6
Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1≤T≤15) testlar soni kiritiladi.

Keyin har bir test uchun alohida ikkita qatorning birinchi satrida N(1≤N≤100000) massiv elementlari soni, ikkinchi satrida esa N ta butun son, massiv elementlari kiritiladi. (1 ≤ a[i] ≤ 10000000)

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida satrda bittadan butun son, umumiy surishlar sonini chop eting.

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

E. Leksik eng kichik satr

Xotira: 16 MB, Vaqt: 1000 ms
Masala

Sizga lotin alifbosining katta harflaridan tashkil topgan ikkita satr berilgan. Siz bu ikki satrdan leksikografik eng kichik satrni quyidagi tartibda hosil qiling:

  • Har qadamda agar qaysidir satr bo’sh bo’lsa, hali bo’shamagan satrning birinchi belgisi satrdan qirqib olinib yangi satrga joylashtiriladi, aks holda ikki satrdan ixtiyoriy birini dastlabki belgisi satrdan qirqib olinib yangi satr oxiriga joylashtiriladi. Bu ish ikki satr ham batamom bo’sh bo’lib qolguniga qadar davom ettiriladi.
Kiruvchi ma'lumotlar:

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 5) testlar soni kiritiladi.

Keyingi satrdan boshlab har bir test uchun alohida ikkita qatorda ikkita satr kiritiladi. (1 ≤ satrlarning uzunliklari ≤ 105)

Chiquvchi ma'lumotlar:

OUTPUT.TXT chiqish faylida har bir test uchun alohida qatorda hosil qilinishi mumkin leksik eng kichik satrni chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
ADIZ
LAZIZ
ABACABA
ABACABA
 
ADILAZIZZ
AABABACABACABA
Kitob yaratilingan sana: 03-May-24 20:52