A. Bilmasvoy
Xotira: 64 MB, Vaqt: 1000 msBilmasvoy 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.
Yagona qatorda n natural soni. \((1\le n\le 10^9)\)
Masala javobini chop eting
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1903 |
5 |
B. ICPC
Xotira: 128 MB, Vaqt: 2000 msSunnat 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.
- 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)\).
Yagona qator: TATU jamoalarining maksimal umumiy kuchi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 1 2 3 |
2 |
| 2 |
6 5 6 2 3 1 4 |
8 |
C. Chegirma
Xotira: 64 MB, Vaqt: 1000 msGolden 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.
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)
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!
| # | 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 |
D. Yandex Internship
Xotira: 128 MB, Vaqt: 1000 msDavlatbek 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.
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.
Chiqish faylida Davlatbek maksimal necha kun anime ko‘rishi mumkinligini chop eting.
| # | 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 |
E. Statistika - 2
Xotira: 32 MB, Vaqt: 1000 msSizga 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.
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 \)
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.
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
| # | 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 |