A. JShShIR

Xotira: 256 MB, Vaqt: 1000 ms
Masala

O‘zbekistonda JShShIR (PINFL) jismoniy shaxsni davlat axborot tizimlarida aniq ajratish uchun ishlatiladigan 14 xonali identifikatsiya raqamidir. U pasport, ID-karta, tug‘ilganlik guvohnomasi, soliq, bank, tibbiyot, pensiya, my.gov.uz kabi tizimlarda bir xil shaxsni bog‘lashda xizmat qiladi.

JShShIR 14 ta raqamdan iborat bo‘lib, umumiy ko‘rinishi quyidagicha bo‘linadi.
\(1\) raqam + \(6\) raqam + \(3\) raqam + \(3\) raqam + \(1\) raqam

1-pozitsiya, \(1\) ta raqam. Jins va tug‘ilgan asr indeksi.
\(1\) yoki \(2\) bo‘lsa, \(1800\)–\(1899\) yillarda tug‘ilgan
\(3\) yoki \(4\) bo‘lsa, \(1900\)–\(1999\) yillarda tug‘ilgan
\(5\) yoki \(6\) bo‘lsa, \(2000\)–\(2099\) yillarda tug‘ilgan
Bunda toq qiymat shaxsning erkak, juft qiymat ayol ekanligini bildiradi.

2–7-pozitsiyalar, \(6\) ta raqam. Tug‘ilgan sana \(ddmmyy\) formatida.
\(dd\) kun, \(01\) dan \(31\) gacha
\(mm\) oy, \(01\) dan \(12\) gacha
\(yy\) yilning oxirgi ikki raqami, \(00\) dan \(99\) gacha

8–10-pozitsiyalar, \(3\) ta raqam. Hudud kodi.
11–13-pozitsiyalar, \(3\) ta raqam. Tartib raqami.
14-pozitsiya, \(1\) ta raqam. Nazorat raqami.
Nazorat raqami 1–13-pozitsiyalardagi raqamlar asosida hisoblanadi va yozuvda xatoliklarni aniqlash uchun xizmat qiladi. 

Sizga 14 xonali JShShIR beriladi. Undan shaxsning tug‘ilgan sanasini aniqlang.

Kiruvchi ma'lumotlar:

Bitta qatorda 14 xonali JShShIR beriladi. U faqat raqamlardan iborat bo‘ladi.

Cheklovlar

JShShIR uzunligi \(14\).

1-pozitsiya qiymati \(1\) dan \(6\) gacha bo‘ladi.

JShShIR qiymati to'g'ri kiritilganligi kafolatlanadi.

Subtasklar

  • Subtask 1. Namunaviy testlar (15 ball)
  • Subtask 2. Qo'shimcha chegaralarsiz (85 ball)
Chiquvchi ma'lumotlar:

Bitta qatorda tug‘ilgan sanani \(dd.mm.yyyy\) formatida chop eting.

Izoh:

1-test uchun:

1-pozitsiya \(3\), demak asr \(1900\)–\(1999\).
2–7-pozitsiya \(121063\), demak \(dd=12\), \(mm=10\), \(yy=63\). Yil \(1963\).

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
31210632040244
 
12.10.1963
2 
20801028866464
 
08.01.1802
3 
51109017773431
 
11.09.2001

B. A + B multiple

Xotira: 256 MB, Vaqt: 2000 ms
Masala

Shohjahon va Arslonbek informatika darsida massivlar mavzusini birga o'rganishdi. Ular massiv ichidan sonni qidirish, uni tartibga keltirish kabi algoritmlarni o'zlashtirishdi. Mavzuni to'liq tushunganligini tekshirish uchun Shavkat ustoz ularga quyidagicha topshiriq berdi:

  • Avvalo doskaga, bir-biridan farqli bo'lgan \(N\) ta butun sonni ketma-ket yozdi.
  • Keyin bolalardan birma-bir quyidagicha savol so'radi: \(a\) va \(b\) butun sonlari berilgan bo'lsa. \(a + b\)  ning qiymati doskada yozilgan ketma-ketlikning qaysi o'rnida ekanligini topish zarur.

Bolalarga bu ishni tezlikda topishiga yordam bering.

Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida ikkita butun son \(N\) va \(Q\) - ketma-ketlik uzunligi va so'rovlar soni beriladi.

Keyingi qatorda \(N\) ta butun son - Shavkat ustoz doskaga ketma-ketlik elementlari - \( c_i\)  kiritiladi.

Keyingi \(Q\) ta qatorning har birida ikkitadan butun son - \(a_j\) va \(b_j\) sonlari probel bilan ajratilgan holatda kiritiladi.

 

Chegaralar:

\(1 \le N, Q \le 2 \times 10^5\)

\(-10^9 \le c_i, a_j, b_j \le 10^9\) 

\(c\) massivdagi barcha elementlar bir biridan farqli ekanligi kafolatlanadi.

 

Subtasklar:

  • Subtask 1.  \(Q = 1\) (14 ball)
  • Subtask 2.  \(N \times Q \le 2 \times 10^5\) (17 ball)
  • Subtask 3. \(0 \le c_i, a_j, b_j \le 10^6\) (30 ball)
  • Subtask 4. Qo'shimcha chegaralarsiz. (39 ball)
Chiquvchi ma'lumotlar:

Har bir so'rov uchun, alohida qatorda agar ketma-ketlikda ushbu qiymat mavjud bo'lsa uning pozitsiyasini, aks holda \(-1\) ni chop eting. Bunda pozitsiyalar 0 dan boshlanadi.

Izoh:

Massiv \(c\): \([−2,7,0,4,10]\). Indekslar 0 dan boshlanadi.

  • \(a=1,\ b=3\).  \(a+b=4\).  \(4\) massivda \(3\)-o‘rinda turibdi. Javob \(3\).
  • \(a=-1,\ b=-1\).  \(a+b=-2\).  \(-2\) massivda \(0\)-o‘rinda turibdi. Javob \(0\).
  • \(a=10,\ b=0\).  \(a+b=10\).  \(10\) massivda \(4\)-o‘rinda turibdi. Javob \(4\).
  • \(a=6,\ b=3\).  \(a+b=9\).  \(9\) massivda mavjud emas. Shuning uchun javob \(-1\).
  • \(a=4,\ b=3\).  \(a+b=7\).  \(7\) massivda \(1\)-o‘rinda turibdi. Javob \(1\).
  • \(a=5,\ b=-3\).  \(a+b=2\).  \(-2\) massivda mavjud emas. Shuning uchun javob \(-1\).
Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 6
-2 7 0 4 10
1 3
-1 -1
10 0
6 3
4 3
5 -3
 
3
0
4
-1
1
-1

C. Qiziqarli bo'linish!

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Matematik detektivga tayyormisiz? Sizda uzunligi \(n\) ga teng va \(\text{natural}\) sonlardan tashkil topgan sirli massiv bor. Sizga \(q\) ta sirli so'rovlar beriladi. Har bir so'rov quyidagicha:

  • \(l\) va \(r\) indekslari beriladi. Siz ushbu oraliqni \([l,\ r]\) ikkiga bo'lib beruvchi \(k\) (\(l\leq k < r\)) shunday nuqtani topingki, \(\left|\sum_{i=l}^{k} a_i - \sum_{i=k+1}^{r} a_i\right|\) (ya'ni, bo'lingan ikkala qismining yig'indisi farqi) minimal bo'lsin. Agar bunday \(k\) bir nechta bo'lsa, eng kichik \(k\)ni tanlang!

Har bir javob oddiy emas — eng aniq va muvozanatli bo'linishni topishga harakat qiling!

Kiruvchi ma'lumotlar:

Birinchi qatorda \(1 \le n,\ q \le 10^5\) sonlari kiritiladi

Ikkinchi qatorda massiv kiritiladi \(1 \le a_i \le 10^9\)

Keyingi q ta qatorda \(1 \le l < r \le n\) sonlari kiritiladi.

Subtasklar:

  • \(Subtask\ 1.\ \text{Massivdagi har bir element bir xil, ya'ni}\ a_i = \ \text{const}\ (11\ \text{ball})\)
  • \(Subtask\ 2.\ n,\ q\ (n,\ q \le 100)\ (12\ \text{ball})\)
  • \(Subtask\ 3.\ n,\ q\ (n,\ q \le 5000)\ (23\ \text{ball})\)
  • \(Subtask\ 4.\ \text{To'liq yechim}\ (54\ \text{ball})\)
Chiquvchi ma'lumotlar:

Har bir so'rov uchun masala yechimini chiqaring

Eslatma!! python dasturlash tilidan foydalanuvchilar pypy compilatoridan foydalanishni maslahat beramiz

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

D. Eng katta tub son

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Tub son — bu aynan 2 ta natural bo‘luvchiga ega bo‘lgan son.

Biror sonni p qismga kesish deganda, uning yozuvini chapdan o‘ngga qarab p ta bo‘lakka ajratish tushuniladi. Har bir bo‘lakda kamida 1 ta raqam bo‘lishi kerak. Bo‘laklarni ketma-ket yozib qo‘ysak, boshlang‘ich son qayta hosil bo‘lishi shart.

Masalan, 12045 sonini 2 qismga kesish:

  • 1 va 2045
  • 12 va 045
  • 120 va 45
  • 1204 va 5

3 qismga kesish:

  • 1, 2, 045
  • 1, 20, 45
  • 1, 204, 5
  • 12, 0, 45
  • 12, 04, 5
  • 120, 4, 5

Eslatma: bo‘laklar oldida 0 bo‘lishi mumkin (045, 04 kabi). Bu bo‘laklar son sifatida qaraladi (masalan 045 = 45).

Sizga \(N\) ta natural sondan iborat \(a\) massiv va \(K\) soni beriladi.

Har bir berilgan sonni eng ko'pi bilan \(K\) ta bo‘lakka bo'lishingiz mumkin.  

Mumkin bo'lgan barcha kesishlar ichida hosil bo'ladigan eng katta tub sonni toping.

Agar hech qanday tub son hosil bo‘lmasa, 0 chiqaring.

Subtasklar

- Subtask 1 (9 ball): \(K = 1\) \(a[i] \le 1000\)

- Subtask 2 (20 ball): \(K = 1\)

- Subtask 3 (30 ball): \(K \le 2\)

- Subtask 4 (41 ball): Qo'shimcha cheklovlarsiz.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(N, K\) kiritiladi. \((1\le N\le 100, 1\le K\le 10)\)

Ikkinchi qatorda \(N\) ta butun sondan iborat \(a\) massiv elementlari kiritiladi. \((1 \le i \le N, 0 \le a[i] \le 10^9)\)

Chiquvchi ma'lumotlar:

Bitta son chiqaring — hosil bo‘lishi mumkin bo‘lgan eng katta tub son (agar yo‘q bo‘lsa 0).

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 2
55 1101
 
101

E. Askiya

Xotira: 256 MB, Vaqt: 1000 ms
Masala

Andijonda askiya san'ati juda rivojlangan. Bahor mavsumida, ayniqsa Navro'z bayrami arafasida insonlar to'planib har kuni askiya aytishadi. 

Andijonda \(2 \times N + 1\) ta askiyachi bor va ularning har biri o'z askiyasiga ega. Ular \(0\) dan \(2 \times N\) gacha raqamlangan. Askiyachilar \(K\) kun davomida har kuni aylana stol atrofida o'tirishadi. Har bir askiyachi o‘zining chap va o‘ng yonidagi qo‘shnisi bilan askiya aytishadi.

Agar ikki askiyachi oldingi kunlarning birortasida yonma yon qo‘shni bo‘lib o‘tirgan bo‘lsa, keyingi kunlarda yana yonma yon o‘tirsa, askiya ularga qiziq bo‘lmaydi va ular yig‘ilishni tark etadi. Siz \(K\) kun uchun joylashuvlarni shunday tuzishingiz kerakki, hech qaysi juftlik \(K\) kun ichida ikki marta qo‘shni bo‘lib qolmasin.

Berilgan chegaralarga asoslangan holda yechim har doim mavjud ekanligini isbotlash mumkin.

Kiruvchi ma'lumotlar:

Yagona qatorda ikkita butun son \(N\) va \(K\) kiritiladi.

Chegaralar

\(1 \le K \le N \le 500\)

Subtasklar

  • Subtask 1.  \(K = 1\) (3 ball)
  • Subtask 2.  \(K = 2\) (9 ball)
  • Subtask 3.  \(N \le 5\) (17 ball)
  • Subtask 4.  \(2 \times K \le N\) (22 ball)
  • Subtask 5.  \(2 \times N + 1\) tub son (24 ball)
  • Subtask 6.  Qo'shimcha chegaralarsiz (25 ball)
Chiquvchi ma'lumotlar:

\(K\) ta qatordan iborat chiqish chop eting.

Har bir qatorda \(2 \times N+1\) ta butun son bo‘lsin. Bu sonlar \(0\) dan \(2×N\) gacha bo‘lgan barcha raqamlar bo‘lishi kerak va shu kun uchun stol atrofida soat strelkasi bo‘yicha joylashuvni bildiradi.

Aylana stol bo‘lgani uchun, har bir qatorda birinchi va oxirgi yozilgan askiyachilar ham qo‘shni hisoblanadi.

Bir necha xil yechim mavjud bo'lsa, istalganini chop etishingiz mumkin.

Izoh:

1-kun qo‘shni juftliklar: (0,1), (1,2), (2,3), (3,4), (4,0)

2-kun qo‘shni juftliklar: (0,2), (2,4), (4,1), (1,3), (3,0)

Hech bir juftlik takrorlanmagan.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2 2
 
0 1 2 3 4
0 2 4 1 3
Kitob yaratilingan sana: 11-Mar-26 21:10