A. Hasan va Ikkilik Funksiya
Xotira: 32 MB, Vaqt: 1000 msQuyidagi ikkilik satri \(s\) berilgan bo'lib, u 0 yoki 1 dan iborat; ikkilik satrda ba'zi bir butun son \(n\) ning ikkilik ko'rsatilishi ifodalangan. Sizdan quyidagi ifodani hisoblash so'raladi:
\(f(n) = ⌊\log₂(n)⌋\)
\(\lfloor x \rfloor \) : \(x\) dan kichik yoki teng maksimal butun sonni bildiradi, masalan \( \lfloor 3.6 \rfloor \)=\(3\) , \( \lfloor 1.9999 \rfloor=1 \).
Misol uchun, \(s=1011\) bo'lsa, u \(n=11\) ni ifodalaydi va \(f(11)=3\) bo'ladi.
NOTE : \(f(0)=0\)
Birinchi qatorda bitta butun son berilgan: \(t\) \((1 \le t \le 10^4)\) – test holatlarining soni.
Har bir test holatining birinchi qatori bitta butun sondan iborat: \(n\) \((1 \le n \le 2 \cdot 10^5)\) – \(s\) satrining uzunligi.
Har bir test holatining ikkinchi qatori \(n\) uzunlikdagi ikkilik satr \(s\) ni o‘z ichiga oladi.
Shuningdek, testlarning umumiy \(n\) yig‘indisi \(2 \cdot 10^5\) dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun son: \(f(n)\).
Birinchi test holatida \(n=2\) shunday qilib, \(f(2)=1\).
Ikkinchi test holatida \(n=7\) shunday qilib, \(f(7)=2\).
To'rtinchi test holatida \(n=62\) shunday qilib, \(f(32)=5\).
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
5 2 10 3 111 5 10011 6 111110 6 011010 |
1 2 4 5 4 |
B. Hasan va Go'zal!
Xotira: 32 MB, Vaqt: 1000 msBerilgan: butun sonlardan tashkil topgan \(a\) massivi, uzunligi \(n\) bo‘lgan \((a_1, a_2, ..., a_n)\) va bir butun son \(k\) .
Sizdan bo‘sh bo‘lmagan (ya’ni, kamida bitta elementdan iborat) qism massiv \(a_l, a_{l+1}, ..., a_r\) ni tanlab, quyidagi operatsiyalardan birini bajarishingiz talab qilinadi:
1. Tanlangan qism massivning barcha elementlarini \(k\) ga ko‘paytirish, ya’ni \(a_i := k \cdot a_i \quad (l \le i \le r)\) .
2. Tanlangan qism massivning barcha elementlarini \(k\) ga bo‘lish, natijani pastga yaxlitlash bilan, ya’ni \(a_i := \left\lfloor \frac{a_i}{k} \right\rfloor \quad(l \le i \le r)\) .
\(\lfloor x \rfloor\) \(x\) ga teng yoki undan kichik bo‘lgan eng katta butun sonni ifodalaydi. Masalan, \(\lfloor 3.5 \rfloor = 3\) va \(\lfloor -3.5 \rfloor = -4\).
\(a\) massividagi barcha qism massivlar orasida, bitta bo‘sh bo‘lmagan qism massivni tanlab, unga yuqoridagi operatsiyalardan birini qo‘llagandan keyin tanlangan massiv yig‘indisining maksimal qiymati qancha bo‘lishi mumkin operatsiyani qo'llashdan keyin faqat bir marta?
Birinchi qatorda bitta butun son berilgan:
\(t (1 \le t \le 10^4)\) – test holatlarining soni.
Har bir test holatining birinchi qatori ikkita butun sondan iborat:
\(n\), \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(-10^9 \le k \le 10^9\)) – massiv uzunligi \(a\) va butun son \(k\).
Har bir test holatining ikkinchi qatori \(n\) ta ajratilgan butun sonlarni o‘z ichiga oladi: \(a_1, a_2, ..., a_n\) (\(-10^4 \le a_1, a_2, ..., a_n \le 10^4\)) – massiv \(a\).
Shuningdek, \(n\) ning yig‘indisi barcha testlarda \(2 \cdot 10^5\) dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun sonni chiqarish kerak: tanlangan \(\bf{bo'sh \ emas}\) qism massivning maksimal yig'indisi.
Birinchi test holatida, butun massivni tanlash optimal bo'ladi, natijada \(10 + 5 + 10 + 5 + 10 = 40\).
Ikkinchi test holatida, butun massivni tanlab, ko'paytirish amali bajarish optimal bo'ladi, \(3 \times 20 = 60\).
Uchinchi test holatida, \([1]\) massivini tanlab, uni \(4\) ga ko'paytirish optimal bo'ladi, natijada javob \(4\) bo'ladi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 5 1 10 5 10 5 10 5 3 10 -5 10 -5 10 3 4 1 -1 -2 |
40 60 4 |
C. Hasan va Maxsus O'chirish
Xotira: 1000 MB, Vaqt: 1000 msQuyidagi massiv berilgan: \(a\) uzunligi \(n\) bo'lgan butun sonlardan iborat. Keling, massivning \(f(a)\) funksiyasini aniqlaymiz, u massivdagi turli xil (unikal) butun sonlar soniga teng bo'ladi \(a\).
Masalan, \(f([1, 2, 4, 4, 2]) = 3\) , chunki unda uchta turli xil son mavjud: \(\{1,2,4\}\).
Siz faqat bitta amalni bajarishga ruxsat berilgansiz: uzunligi \(k\) bo'lgan istalgan qism massivni tanlab, uni olib tashlash.
Masalan, agar \(a =[1, 2, 4, 4, 2]\) va \(k = 2\), bo'lsa, agar 3-chi va 4-chi elementlarni olib tashlasak, hosil bo'lgan massiv\([1, 2, 2]\) bo'ladi va\(f(a)=2\)
Operatsiyani bajargandan so‘ng, \(\min(f(a))\) .
Birinchi qatorda bitta butun son berilgan:
\(t (1 ≤ t ≤ 10^4 )\) – test holatlarining soni.
Har bir test holatining birinchi qatori ikkita butun sondan iborat:
\(n\) va \(k\) (\(1 ≤ k < n ≤ 2·10^5 \)) – mos ravishda massiv uzunligi va olib tashlanadigan qism massiv uzunligi.
Har bir test holatining ikkinchi qatori
\(n\) ta butun sonni o‘z ichiga oladi:
\(a_1,a_2,..,a_n\) (\(1 ≤ a_i ≤ 10^{11} \)).
Shuningdek, \(n\) ning yig‘indisi \(4 · 10^5\) dan oshmasligi kafolatlangan.
Har bir test holati uchun bitta butun sonni chiqarish kerak:
\(\min(f(a))\).
Birinchi test holati uchun:
Qaysi qism massivni tanlamang, natija har doim \(1\) ga teng bo'ladi.
Ikkinchi test holati uchun:
Qism massivni tanlashning ikki usuli mavjud: \([1,2]\) yoki \([4,4]\),
va hosil bo'lgan massiv ikkala holatda ham \(2\) ta turli xil sonlarga ega bo'ladi.
To‘rtinchi test holati uchun:
Siz \([8,3,6]\) ni tanlashingiz kerak va hosil bo'lgan massiv
\([2,1,4,7,6,4,7]\) bo‘ladi, bu holda qiymat \(4\) ga teng bo‘ladi.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
4 3 2 1 2 3 5 2 1 2 4 4 2 6 1 1 1 4 5 1 4 10 3 2 1 4 7 4 8 3 6 4 7 |
1 2 2 4 |
D. Hasan va Indeks Sanash
Xotira: 32 MB, Vaqt: 500 msBerilgan butun son \(n\), uzunligi \(n\) bo'lgan nechta permutatsiya mavjudligini hisoblang, unda faqat bitta indeks \(i\) mavjud bo'lib, u \(p_i > i\) shartini qanoatlantiradi . Javobni \( 10^9+7 \) ga bo'lgandagi qoldig'ini hisoblang.
Birinchi qatorda bitta butun son \( t \) \( (1 \le t \le 10^4) \) — testlar soni.
Har bir testning faqat bitta qatori bor, unda bitta butun son \( n \) \( (1 \le n \le 10^{18}) \) — \( p \) permutatsiyasining uzunligi.
Bitta butun son – shunday permutatsiyalarning soni, \(10^9+7\) ga nisbatan moduli.
\(n = 3\) uchun, amalga oshirilgan permutatsiyalar:
1. \( [1, 3, 2] \), bu yerda \( p_2 = 3 > 2 \)
2. \( [2, 1, 3] \), bu yerda \( p_1 = 2 > 1 \)
3. \( [3, 1, 2] \), bu yerda \( p_1 = 3 > 1 \)
4. \( [3, 2, 1] \), bu yerda \( p_1 = 3 > 1 \)
Javob: 4.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 3 |
4 |
E. Kvadrat uchburchak
Xotira: 512 MB, Vaqt: 1000 msSizga \(n \cdot n\) \(a\) jadval berilgan, va sehirgar agar siz \(q\) ta so'rov ga javob bersangiz shokolad beraman deb vada berdi, afsuski sehirgar uhlashni juda hohlab turgani uchun siz unga tez javob berishingiz kerak har bir so'rov da:
\(l\) va \(r\) \((l \le r)\)beriladi sizni vazifangiz shunday \(a_{i, j}\) lar summasini topshingiz kerak \(l≤i≤j≤r\) sharti bajariladi. Rasmiy ravishda:
Birinchi qatorda \(n\) va \(q\)( \(1 \le n \le 2500\), \(1 \le q \le 200000\)) - satr va qatorni uzunligi va so'rovlar soni.
Keyingi \(n\) qatorda jadval \(a\)(\(a_{i,j} \le 10^9\)).
Keyingi \(q\) qatorda so'rovlar, har bir so'rovda \(l\) va \(r\) beriladi(\(1 \le l \le r \le n\))
Har bir so'rovga javobni chiqaring - bitta butun son.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
3 5 15 19 11 18 20 3 9 4 4 1 2 1 1 1 2 3 3 2 2 |
54 15 54 4 20 |
| 2 |
6 7 2 1 1 1 19 5 16 13 16 7 19 8 10 2 14 14 16 13 3 7 3 16 10 4 8 12 12 1 16 17 18 12 10 6 5 4 4 4 4 5 3 6 2 3 4 4 1 2 1 5 |
16 42 124 43 16 16 165 |
F. Behruzbek va XOR so‘rovlar
Xotira: 512 MB, Vaqt: 2000 msBehruzbek massivlarda XOR operatsiyasini bajarishni juda ham yoqtiradi. Bir kuni uning oldiga do'sti Temur kelib, uzunligi \(n\) bo'lgan \(a\) massiv hamda \([l,r,x,y]\) turdagi \(q\) ta so'rovlar berdi . Har bir so'rov uchun Behruzbekdan \(a[l:r]\) qismida joylashgan va qiymatlari \([x,y]\) oralig'ida bo'lgan elementlarning XOR ni topishni so'radi. Behruzbek bu muammoni bir o'zi hal qila olmadi, shuning uchun sizdan yordam umid qilmoqda. Unga Temurning barcha savollariga javob berishga yordam bering.
Birinchi qatorda bitta butun son mavjud \(t\) \( (1 \le t \le 1000) \) - testlar soni.
Har bir test uchun birinchi qatorida ikkita butun son mavjud \(n,q\) \( (1 \le n,q \le 4\times 10^5 \) ) - \(a\) massiv uzunligi va so'rovlar soni.
Keyingi qatorda \(n\) ta butun sonlar \(a_1,a_2,..,a_n\) \( (1 \le a_1,a_2,..,a_n \le 10^9) \) - \(a\) massiv elementlari kiritiladi.
Keyingi \(q\) ta qatorning har birida \(4\) ta butun son \(l,r,x,y\) \( (1 \le l \le r \le n) \) \( (1 \le x,y \le 10^9) \) kiritiladi.
\(n+q\) umumiy testlar summasi \( 8\cdot 10^5\) dan oshmasligi kafolatlangan.
Har bir so'rov uchun javobni yangi qatorda chop eting.
- \(1\)-so'rov \([5, \color{red}{\underline{\bf{1}}} \color{white}, 4, 2, 3] \) massivini oladi. Elementlardan faqat bittasi \([1,1]\) oralig'ida. Javob: \(1\).
- \(2\)-so'rov \([ \color{red}{\underline{\bf{5}}} \color{while}{,} \color{red}{\underline{\bf{1}}} \color{while}{,} \color{red}{\underline{\bf{4}}} \color{while}{,} \color{red}{\underline{\bf{2}}} \color{while}{,} \color{red}{\underline{\bf{3}}} \color{white}{]}\) massiv va \([1, 100]\) diapazonni oladi. Javob: \(5 ⊕1 ⊕ 4 ⊕ 2 ⊕ 3 = 1\).
- \(3\)-so'rov \( [ \color{red}{\underline{\bf{5}}} \color{while}{,} 1 , \color{red}{\underline{\bf{4}}} \color{while}{]} \) pastki qator (subarray) va \([2, 100]\) oraliqni oladi. Javob: \(5 ⊕ 4 = 1\).
- \(4\)-so'rov \( [ 1 , \color{red}{\underline{\bf{4}}} \color{while}{]}\) pastki qator (subarray) va \( [2,100] \) diapazonni oladi. Javob: \(4\).
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 5 4 5 1 4 2 3 1 5 1 1 1 5 1 100 1 3 2 100 2 3 2 100 |
1 1 1 4 |
G. Hasan va Adolatli Bo'linish
Xotira: 64 MB, Vaqt: 1000 msBir musobaqada \(n\) ta ishtirokchi bor, har birining kuchi \(s_i\) bo'lib, \((1 \leq s_i \leq n)\) va har bir ishtirokchining kuchi noyob (har bir o'yinchida faqat bitta noyob qiymat mavjud). Ishtirokchilar ikki jamoaga bo'linadi va ular o'yinni iloji boricha adolatli qilishni xohlaydi, shuning uchun ular jamoalarining kuchi teng bo'lishini istaydi. Biror jamoaning kuchi \((T)\) quyidagicha aniqlanadi:
\[T_1 \times T_2 \times \dots \times T_m\]Birinchi jamoaning kuchi va ikkinchi jamoaning kuchi o'rtasidagi minimal nisbatni aniqlang (Nisbat har doim butun son bo'lishini unutmang). Javob katta bo'lishi mumkin, shuning uchun uni \(10^9 + 7\) ga bo'lganda chiqaring.
E'tibor bering, \((n=1)\) uchun javob 1 ga teng.
Birinchi qatorda bitta butun son \(t\) \((1 \leq t \leq 10^4)\) — test holatlari soni.
Har bir test holatining yagona qatorida bitta butun son \(n\) \((1 \leq n \leq 10^6)\) — ishtirokchilar soni.
Bu miqdor kafolatlangan \(n\) oshmaydi \(10^6\).
Bitta butun son, minimal nisbati \(10^9 + 7\) moduli bo'yicha.
\(n=4\) uchun eng yaxshi bo'linish quyidagicha:
\(\{3,4\}\)
\(\{1,2\}\)
javob quyidagicha bo'ladi:
\[\frac{3 \times 4}{2 \times 1}=6\]
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
1 4 |
6 |
H. Qo'shish
Xotira: 512 MB, Vaqt: 1500 msJahonali oson masalarni yechishdan zerikdi, shuning uchun u qiyinroq masala o'ylab topdi. U boshida bo'sh \(a\) massivga ega(\(|a|=0\)). Shundan so'ng, \(q\) ta hodisa sodir bo'ladi Har bir hodisa quyidagilardan biri bo'lishi mumkin:
\(1 \ i \ x\) - yangi element \(x\) ni \(a_{i}\) va \(a_{i+1}\) orasiga qo'shish. Yangi massiv shunday bo'ladi:
\[[a_1, a_2, \dots, a_i, x, a_{i+1}, \dots, a_{|a|}]\]\(2 \ i\) - \(i\)-chi elementni chiqarish ya'ni \(a_{i}\).
Dastlab, Jahonali bu masalani oson deb o‘yladi. Biroq, biroz o‘ylab ko‘rgach, u buni yecha olmasligini tushundi. Jahonalining do‘sti sifatida, sizga ushbu masalani hal qilish topshirildi
\(|x|\)- Bu yerda \(x\) massivni uzunligi.
Birinchi qatorda \(q\)(\(1 \le q \le 5 \cdot 10^5\)) - hodisalar soni.
Keyingi \(q\) ta qatorda quyidagi berilgan hodisalardan bitta bo'ladi har bir hodisa uchun:
\(1 \ i \ x\) (\(0 \le i \le |a|\), \(1 \le x \le 10^{18}\) ) - yangi element \(x\) ni \(a_{i}\) va \(a_{i+1}\) orasiga qo'shish.
\(2 \ i\) (\(1 \le i \le |a|\)) - \(i\)-chi elementni chiqarish ya'ni \(a_{i}\).
\(|x|\) - Bu yerda \(x\) massivni uzunligi.
Har bir \(2\) turdagi so'rovga - bitta natural son chiqaring.
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
15 1 0 17 2 1 1 0 1 2 1 2 2 1 2 5 1 3 4 1 3 9 1 3 6 1 4 6 1 4 8 1 5 9 1 3 5 2 10 2 9 |
17 1 17 4 9 |
I. Yana so'rovlar?
Xotira: 256 MB, Vaqt: 5000 msSizga do'stingiz \(n\) ta tugundan tashkil topgan \(t\) daraxt bergan. Har bir tugunda sonlar yozilgan ya'ni \(i\) -chi tugun uchun unda yozilgan son - \(a_{i}\) , sizga \(q\) ta so'rovga javob berishingiz kerak. Har bir so'rovda \(x\), \(l\) va \(r\)(\(1 \le l \le r \le n\)) berilgan. Aytaylik qanaqadir \(i\) va \(j\) tugunlar uchun ular orasidagi ma'sofani \(d(i,j)\) deb belgilab olaylik, sizni vazifangiz shunday \(a_{i}\) lar yig'indisini topishingiz kerak \(l \le d(x, i) \le r\) sharti bajarilishi kerak. Rasmiy ravishda:
\[\sum_{\substack{i \in t \\ l \leq d(x, i) \leq r}} a_i\]Birinchi qatorda ikkita natural sonlar \(n\) va \(q\)(\(2 \le n,q \le 10^5\), ) - Daraxtdagi tugunlar soni va so'rovlar soni.
Ikkinchi qatorda \(n\) ta natural sondan tashkil topgan \(a\) massiv (\(1 \le a_{i} \le 10^9\)).
Keyingi \(n-1\) ta qatorda \(t\) daraxtni ikkita tugunlari \(u\) va\(v\)(\(1 \le u,v \le n\)) - \(u\) va \(v\) ni bog'lab turuvchi yo'l.
Keyingi \(q\) ta qatorda \(x\), \(l\) va \(r\)(\(1 \le x \le n\), \(1 \le l \le r \le n\)). Agar \([l,r]\) oralig'ida qaysidir tugun yo'q bolsa u tugundagi qiymatini \(0\) deb olib ketishingiz mumkin.
Har bir so'rovga javobni chiqaring.
Birinchi so'rovni illyustratsiyasi:
| # | INPUT.TXT | OUTPUT.TXT |
|---|---|---|
| 1 |
9 5 1 2 4 8 16 32 64 128 256 3 5 1 7 4 5 4 6 2 4 1 8 5 8 1 9 1 2 3 2 4 4 3 2 2 4 1 5 1 1 4 |
28 1 136 503 510 |