A. O'yinchoqlar guruhi

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Sizda 2 ta guruhdan tashkil topgan o'yinchoqlaringiz bor. Siz ularni qaysi biri kuchli ekanini bilish uchun o'ziga xos reja tuzdingiz. Bunda birinchi jamoaning eng kuchli o'yinchisi raqib jamoaning eng kuchli o'yinchisi bilan bellashadi, ikkinchi eng kuchli o'yinchi esa raqib jamoaning ikkinchi eng kuchli o'yinchisi bilan, va hokazo. Siz birinchi guruhning nechta o'yinchisi bellashuvda yutib chiqishini bilmoqchisiz. (O'yinchi bellashuvda yutib chiqishi uchun raqibidan qat'iy kuchli bo'lishi kerak)

Kiruvchi ma'lumotlar:

1-qatorda 5 ta natural son. Birinchi jamoa o'yinchilarining kuchlari beriladi.

2-qatorda 5 ta natural son. Ikkinchi jamoa o'yinchilarining kuchlari beriladi.

Kiritiladigan sonlar $[1, 100]$ oralig'ida bo'lishi kafolatlangan.

Chiquvchi ma'lumotlar:

Yagona qatorda bitta butun son, masala javobini chop eting.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 7 1 5 9 9 8 8 10 3	0
2	7 10 9 8 5 10 1 8 4 3	4

B. Olimpiya o'yinlari

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Siz qadimgi Olimpiya o'yinlariga tashrif buyurdingiz. Olimpiya o'yinlarida turli xil o'yinlar (musobaqalar) o'tkaziladi. Ammo nechta o'yin bo'lishini bilmaysiz. Hamma g'olib nomi bilan qiziqsa, siz esa aksincha har bir o'yinda eng kam ball yig'gan o'yinchilarni aniqlamoqchisiz.

Shunday qilib Olimpiyada bo'layotgan har bir o'yindagi eng kam ball yig'gan o'yinchining balini topishingiz kerak.

Kiruvchi ma'lumotlar:

Har bir o'yin n natural soni - joriy o'yinda ishtirok etayotgan o'yinchilar soni bilan boshlanadi $(0\le n \le 100)$ .

Keyingi qatorda n ta natural son, ushbu o'yinda qatnashgan o'yinchilarning ballari kiritiladi. $[1, 1000]$

Qachonki biror o'yinda bitta ham o'yinchi qatnashmasa Olimpiya o'yinlari o'z nihoyasiga yetadi.

Qo'shimcha ravishda barcha o'yinlardagi n larning yig'indisi $10^5$ dan oshmaydi.

Chiquvchi ma'lumotlar:

Har bir o'tkazilgan o'yin uchun eng kam ball yig'gan o'yinchi balini chop eting.

Hech kim ishtirok etmagan o'yin o'tkazilmagan deb hisoblanadi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 4 4 4 7 10 2 0	4 2
2	10 1 9 6 6 5 3 1 9 1 4 7 3 8 9 8 4 7 5 0	1 3

C. Test

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Siz va do‘stingiz tezkor savol-javob (Ha/Yo'q) testini topshirgansiz. Dos'tingiz nechta savolga to'g'ri javob berganini biladi, lekin qaysi savollar to‘g‘ri ekanini bilmaydi. Siz o‘z javoblaringizni va do‘stingizning javoblarini solishtirasiz. Sizning maqsadingiz — siz maksimal ravishda nechta savolga to‘g‘ri javob bergan bo‘lishingiz mumkinligini aniqlash.

Kiruvchi ma'lumotlar:

Har bir test ishi quyidagilardan iborat bo‘ladi:

n — do‘stingiz to‘g‘ri javob bergan savollar soni $(0\le n \le 1000)$
s — ikki qatorli satr. Birinchi qatorda sizning javoblaringiz (H yoki Y), ikkinchi qatorda esa do‘stingizning javoblari (H yoki Y). Ikkala satr uzunligi bir xil va uzunlik $(max(n, 1)\le \lvert s\rvert \le 1000$ oraliqda bo‘ladi.

Chiquvchi ma'lumotlar:

Siz maksimal nechta savolga to‘g‘ri javob bergan bo‘lishingiz mumkinligini aniqlab, bitta butun son chiqaring.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 YHYYY HYHHH	2
2	6 HHYHYYHYHY HHHHYYHHHH	9

D. Spiral

Xotira: 128 MB, Vaqt: 2000 ms

Masala

Humoyun ko‘plab multfilmlarda ko‘rganidek spiral shakli insonni o‘ziga jalb qilib, hatto gipnoz qilib qo‘yishi ham mumkin deb o‘ylaydi. Shu sababli u o‘zi tomonidan berilgan masala eng ko‘p ishtirokchiga yoqishini xoxlagani uchun masalaga aynan spiral deb nom qo’yishni joiz deb topdi, hatto masalaning o’zi ham spiralga aloqador. Ya’ni u quyidagicha:

Humoyun o’lchami $1\ 000\ 000\ 001 \times 1\ 000\ 000\ 001$ jadval oldi va uning ichini natural sonlar ketma-ketligini spiralsimon shaklda joylashtirish orqali to’ldirib chiqdi.

Sizning vazifangiz Humoyun tuzgan jadvaldan A va B sonlari orasidagi masofani aniqlashdan iborat.

Ikki sonning orasidagi masofa ularning jadvaldagi joylashuv koordinatalari Manhattan masofasi(farqlarining yig’indisi)ga teng.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son, $Q (1 \le Q \le 10^5)$ , testlar soni kiritiladi.

Keyingi $Q$ ta qatorning har birida ikkitadan butun son, $A(1 \le A \le 10^{18})$ va $B(1 \le B \le 10^{18})$ sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda $A$ va $B$ sonlari orasidagi masofani chop eting!.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	2 12 2 26 6	2 6

E. Statistika - 1

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga $n$ uzunlikdagi $X$ massivi berilgan. Har bir element $x_i$ nuqtani ifodalaydi. Siz ikkita turdagi so'rovlarni bajarishingiz kerak:

1. $1 \ i \ a$ : Bu so'rovda $x_i$ qiymatini $a$ ga o'zgartirish kerak bo'ladi.

2. $2 \ l \ r$ : Bu turdagi so'rovda massivning $[l, r]$ oralig'idagi nuqtalarning populyatsiya standart chetlanishini hisoblash kerak bo'ladi.

Populyatsiya standart chetlanishi $\sigma$ quyidagi formula bilan hisoblanadi:

How To Calculate Standard Deviation In Google Sheets - Kieran Dixon

Bu yerda:

- $\mu = \frac{\sum x_i}{n}$ , ya'ni $x_i$ larning o'rta arifmetik qiymati.

- $n$ — oraligdagi nuqtalar soni.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son $n$ va $q$ berilgan, bunda:

- $n$ — massiv uzunligi.

- $q$ — so'rovlar soni.

Ikkinchi qatorda $n$ ta butun son $x_i$ berilgan, massiv elementlarini ifodalaydi.

Keyingi $q$ qatorda so'rovlar berilgan:

- Yangilash So'rovi uchun qatorda $1 \ i \ a$ berilgan, bunda:

- $i$ — yangilanadigan element indeksi (indekslash 1 dan boshlangan deb hisoblanadi).

- $a$ — $x_i$ ning yangi qiymati.

- Oraliq So'rovi uchun qatorda $2 \ l \ r$ berilgan, bunda:

- $l$ va $r$ — $[l, r]$ oralig'ining indekslari (indekslash 1 dan boshlangan deb hisoblanadi).

Qiymat chegaralari:

- $1 \leq n, q \leq 10^5$

- $-25 \leq x_i, a \leq 25$

- $1 \leq i, l, r \leq n$

Chiquvchi ma'lumotlar:

Har bir oraliq so'rovi uchun $[l, r]$ oralig'idagi nuqtalarning populyatsiya standart chetlanishini chiqaring. Natijani 6 kasr belgigacha yaxlitlab chiqaring.

Izoh:

formuladagi $n$ massiv uzunligi emas!. Formuladagi $n$ nima ekanligi formulani pastida yozilgan!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 3 1 2 3 4 5 2 1 5 1 3 10 2 1 5	1.41421356 3.13687743
2	3 2 -1 0 1 2 1 3 1 2 5	0.81649658

F. Bilmasvoy

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Bilmasvoy o'xshash sonlarga qiziqadi. U a va b sonlarini o'xshash deb hisoblaydi, agar ushbu sonlarning aynan bitta raqami faqat 1 ga farq qilsa.

Masalan 1903 soni 1803, 1913, 1902, 1904 va 2903 sonlari bilan o'xshash.

Bilmasvoy sizga bitta son beradi. Siz shu songa o'xshash sonlar nechta ekanini topishingiz kerak.

Kiruvchi ma'lumotlar:

Yagona qatorda n natural soni. $(1\le n\le 10^9)$

Chiquvchi ma'lumotlar:

Masala javobini chop eting

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1903	5

G. ICPC

Xotira: 128 MB, Vaqt: 2000 ms

Masala

Sunnat TATUda talabalarni ICPCga tayyorlash uchun mas'ul shaxs. Unda ICPC uchun tayyorlangan n ta talaba bor. Har bir talabaning o'ziga xos kuchi bor - $f_i$ . U talabalarni uch kishilik jamoalarga bo'lishi kerak.

Uch kishidan iborat jamoaning kuchi ularning kuchlari orasidagi median (o‘rtadagi qiymat) bo‘ladi, ya’ni ularning kuchlarini saralab o‘rtadagi qiymat olinadi.

Sunnatga yordam bering! U talabalarni k ta uch kishilik jamoaga ajratishi kerak, shunday qilib umumiy kuch maksimal bo‘lsin.
Umumiy kuch — barcha k jamoaning kuchlari yig‘indisiga teng.

Kiruvchi ma'lumotlar:

1-qator: Talabalar soni — n $(1\le n\le 10^6)$ , bu son 3 ga karrali bo‘ladi.
2-qator: n ta talabaning kuchlari — $f_1, f_2, ..., f_n (1\le f_i\le 10^6)$ .

Chiquvchi ma'lumotlar:

Yagona qator: TATU jamoalarining maksimal umumiy kuchi.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	3 1 2 3	2
2	6 5 6 2 3 1 4	8

H. Chegirma

Xotira: 64 MB, Vaqt: 1000 ms

Masala

Golden Valley Clothing Warehouse o‘zining ko‘p miqdordagi qishki mahsulotlarini tezda sotish niyatida, chunki yaqin orada bahor va yozgi kiyim-kechaklar keladi. Menejer sotuvni boshqarish uchun juda murakkab chegirma tizimini o‘ylab topdi va siz endi shu tizimni amalga oshirishingiz kerak.

Mana menejer belgilagan qoidalar:
Mahsulotlarga rangli dumaloq stikerlar yopishtiriladi — bular "stiker" deb ataladi, masalan, qizil stiker, sariq stiker va hokazo. Har bir rang ma’lum bir foiz chegirmaga mos keladi.

Rangli Dot	Chegirma %
Qizil (Red)	45%
Yashil (Green)	30%
Ko‘k (Blue)	20%
Sariq (Yellow)	15%
To‘q sariq (Orange)	10%
Oq (White)	5%

Bunga qo‘shimcha ravishda, menejer maxsus chegirma kuponlari tarqatdi! Har qanday xaridor ushbu kuponni taqdim etsa, "stiker" chegirmalari hisoblab chiqilgandan keyin yana qo‘shimcha 5% chegirma oladi.

Siz har bir mahsulot uchun yakuniy chegirma narxini hisoblab chiqishingiz kerak.

Dastur savdo terminalida ishlashi kerak va narxlar eng yaqin sentga (0.5 yuqoriga) yaxlitlanadi.
- Agar sentning oxiri [0.0, 0.5) orasida bo'lsa, pastga — 0 ga yaxlitlanadi.
- Agar sentning oxirgi [0.5, 1.0) orasida bo‘lsa, yuqoriga — keyingi sentga yaxlitlanadi.
Agar xaridor naqd pul to‘layotgan bo‘lsa, narx eng yaqin 10 sentga yaxlitlanadi.
- Agar sentning oxirgi raqami 0 dan 5 gacha bo‘lsa, pastga — 0 ga yaxlitlanadi.
- Agar sentning oxirgi raqami 5 dan 10 gacha bo‘lsa, yuqoriga — keyingi 10 sentga yaxlitlanadi.

Tizim hamma bu qoidalarga amal qilib, to‘g‘ri narxlarni chiqara olishi kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda N — qayta ishlanishi kerak bo‘lgan xaridlar soni beriladi (0 < N ≤ 100). Keyingi N ta qatorning har biri bitta xaridni ifodalaydi.

Har bir qator quyidagi formatda bo‘ladi, elementlar bo‘sh joy bilan ajratiladi:

<asosiy narx> <stiker> <kupon> <to'lov>

<asosiy narx> — chegirma berilishidan oldingi mahsulot narxi. Bu ikkita o‘nlik kasr joyiga ega o‘nli son bo‘ladi.
<stiker> — dotning rangi, katta harfda yoziladi va rangning birinchi harfi bo‘ladi:
- R — Qizil (Red)
- G — Yashil (Green)
- B — Ko‘k (Blue)
- Y — Sariq (Yellow)
- O — To‘q sariq (Orange)
- W — Oq (White)
<kupon> — xaridor chegirma kuponi ko‘rsatganini bildiradi:
- C — kupon bor (5% qo‘shimcha chegirma)
- X — kupon yo‘q
<to'lov> — to‘lov turi:
- C — naqd pul
- P — plastik karta (yoki boshqa naqd pulsiz to'lov)

Chiquvchi ma'lumotlar:

Har bir xarid uchun chiqishda bitta qator bo‘lishi kerak, unda chegirmadan keyingi narx ko‘rsatiladi. U quyidagi formatda bo‘lishi kerak:

$d.cc

ya’ni sent qismi nuqtadan keyin 2 xonada chiqishi shart!

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	9 67.34 O X P 78.58 O C C 45.81 Y X C 95.42 Y C C 4.02 Y C P 21.16 B X C 26.71 R X P 67.99 G C C 11.22 Y X P	$60.61 $67.20 $38.90 $77.10 $3.25 $16.90 $14.69 $45.20 $9.54

I. Yandex Internship

Xotira: 128 MB, Vaqt: 1000 ms

Masala

Davlatbek yaqinda Yandex kompaniyasida amaliyotchi (intern) sifatida ish boshladi va unga dasturdagi kichik xatoliklarni (bug) tuzatish vazifasi yuklatildi.

Keyingi $N$ kun davomida, $i$ -kuni $a_i$ ta bug paydo bo‘ladi. Davlatbek esa har kuni maksimal $b_i$ ta bugni tuzatishi yoki anime tomosha qilishi mumkin. Agar u barcha xatolarni shu kunning o'zida bartaraf etmasa, ular keyingi kunga o'tadi. Davlatbek anime ko‘rishni yoqtirgani sababli, imkon qadar ko‘proq kunini unga ajratishga harakat qiladi.

Biroq, mentor uning o‘z ustida ko‘proq ishlashini xohlaydi va $M$ kun davomida Davlatbekni tekshiradi. Har bir $j$ uchun $c_j$ -kuni mentor ish tugaganidan so‘ng keladi va dasturda hech qanday bug yo'q ekanini tekshiradi.

Davlatbek barcha zarur ma’lumotlarni sizga taqdim etdi. Endi siz uning ko'pi bilan necha kun anime ko‘rishi mumkinligini aniqlashingiz lozim.

Kiruvchi ma'lumotlar:

Kirish faylining 1-satrida ikkita butun son $N$ va $M$ $(1≤M≤N≤10^5)$ – umumiy kunlar soni va mentor tekshiradigan kunlar soni beriladi.

2-satrda $N$ ta butun son $a_1, a_2, ..., a_N (1 \leq a_i \leq 10^9)$ – har kuni paydo bo‘ladigan buglar soni keltiriladi.

3-satrda $N$ ta butun son $b_1, b_2, ..., b_N (1 \leq b_i \leq 10^9)$ – Davlatbek $i$ -kuni maksimal qancha bug tuzata olishi mumkinligi beriladi.

4-satrda $M$ ta butun son $c_1, c_2, ..., c_M (1≤c_j≤N)$ – mentor keladigan kunlar tartiblangan holda beriladi $(1 \leq j \leq M - 1$ uchun $c_j \leq c_{j+1})$ . Mentor kelgan vaqtda barcha bug larni tuzatish mumkinligi kafolatlanadi.

Chiquvchi ma'lumotlar:

Chiqish faylida Davlatbek maksimal necha kun anime ko‘rishi mumkinligini chop eting.

Misollar:

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

J. Statistika - 2

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Sizga uzunligi $n$ bo'lgan ikki $X$ va $Y$ ikkita massivlari beriladi. har bir ( $x_i, y_i$ ) juftlik 2D fazodagi nuqtani ifodalaydi. Siz ikkita turdagi jami $q$ ta so'rovlarni bajarishingiz kerak:

$1 \ i \ a \ b$ turidagi so'rov. Bu so'rov uchun $(x_i, y_i)$ juftligi qiymatini $(a, b)$ ga o'zgartiring.
$2 \ l \ r$ turdagi so'rov. Bu so'rov uchun $[l, r]$ oralig'idagi nuqtalarning nuqtalar o'zaro qanday bog'langanligini - korrelyatsiya koeffitsientini hisoblang.

Korrelyatsiya koeffitsienti quyidagi formula bilan hisoblanadi:

$\overline{x}$ - oraliqdagi barcha $x_i$ qiymatlarning o'rta arifmetik qiymati bo'lsin.

$\overline{y}$ - oraliqdagi barcha $y_i$ qiymatlarning o'rta arifmetik qiymati bo'lsin.

Unda korrelyatsiya koeffitsienti quyidagi formula orqali hisoblanadi:

Agar maxraj hamda surat nolga teng bo'lsa, korrelyatsiya koeffitsienti aniqlanmagan hisoblanadi. Bu holatda “undefined” deb chiqaring.

Agar surat musbat va maxraj nolga teng bo'lsa “inf” deb chiqaring.

Agar surat manfiy va maxraj nolga teng bo'lsa, “-inf” deb chiqaring.

Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son $n$ va $q$ berilgan, bunda:

Keyingi $n$ qatorda ikkita butun son $x_i$ va $y_i$ berilgan, $i$ -nuqtaning koordinatalarini ifodalaydi.

Keyingi $q$ qatorda so'rovlar berilgan:
- Birinchi turdagi so'rov uchun qatorda `1 i a b` berilgan, bunda:
- $i$ — yangilanadigan nuqtaning indeksi.
- $a$ va $b$ — yangi koordinatalar $(x_i, y_i)$ .
- Ikkinchi turdagi so'rov uchun qatorda `2 l r` berilgan, bunda:
- $l$ va $r$ — $[l, r]$ oralig'ining indekslari.

Cheklovlar:

- $1 \leq n, q \leq 10^5$
- $-25 \leq x_i, y_i \leq 25$
- $1 \leq i, l, r \leq n$
- $-25 \leq a, b \leq 25$

Chiquvchi ma'lumotlar:

Har bir oraliq so'rovi uchun $[l, r]$ oralig'idagi nuqtalarning korrelyatsiya koeffitsientini chiqaring:
- Agar korrelyatsiya koeffitsienti aniqlanmagan bo'lsa, `undefined` chiqaring.
- Agar korrelyatsiya koeffitsienti inf bo'lsa, `inf` chiqaring.
- Agar korrelyatsiya koeffitsienti -inf bo'lsa, `-inf` chiqaring.
- Aks holda, korrelyatsiya koeffitsientini chiqaring

Dasturingiz chiqargan son, juri yechimi chiqargan sondan ko'p bilan $10^{-4}$ farq qilishi lozim.

Izoh:

Birinchi test uchun izoh

1. Birinchi So'rov (`2 1 5`):

- Oraliq: $[1, 5]$ (barcha 5 nuqta).
- Bu nuqtalar bir to'g'ri chiziqda joylashgan, shuning uchun korrelyatsiya koeffitsienti $1.00000000$ ga teng.

2. Ikkinchi So'rov (`1 3 10 20`):
- Uchinchi nuqtani $(5, 6)$ dan $(10, 20)$ ga yagilanadi.
- Yangi nuqtalar: $(1, 2), (3, 4), (10, 20), (7, 8), (9, 10)$ .

3. Uchinchi So'rov (`2 1 5`):
- Oraliq: $[1, 5]$ (barcha 5 nuqta).
- Nuqtalar: $(1, 2), (3, 4), (10, 20), (7, 8), (9, 10)$ .
- Uchinchi nuqta $(10, 20)$ chiziqdan biroz chetga chiqqanligi sababli, korrelyatsiya koeffitsienti $0.99339927$ ga teng.

4. To'rtinchi So'rov (`2 2 4`):
- Oraliq: $[2, 4]$ (2-chi, 3-chi va 4-chi nuqtalar).
- Nuqtalar: $(3, 4), (10, 20), (7, 8)$ .
- Korrelyatsiya koeffitsienti: 0.93471954

5. Beshinchi So'rov (`2 1 3`):
- Oraliq: $[1, 3]$ (1-chi, 2-chi va 3-chi nuqtalar).
- Nuqtalar: $(1, 2), (3, 4), (10, 20)$ .
- Korrelyatsiya koeffitsienti: 0.99377021

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	5 5 1 2 3 4 5 6 7 8 9 10 2 1 5 1 3 10 20 2 1 5 2 2 4 2 1 3	1.00000000 0.88345221 0.93471954 0.99377021
2	3 4 -1 1 0 0 1 -1 2 1 3 1 2 5 5 2 1 3 2 2 3	-1.00000000 0.78571429 1.00000000
3	4 4 1 1 1 1 1 1 1 1 2 1 4 1 2 2 2 2 1 4 1 3 2 -2	undefined 1.00000000

#

INPUT.TXT

OUTPUT.TXT

1

2

-1.00000000
0.78571429
1.00000000

3

undefined
1.00000000