A. Hasan va Ikkilik Funksiya

Xotira: 32 MB, Vaqt: 1000 ms

Masala

Quyidagi 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$

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir test holati uchun bitta butun son: $f(n)$ .

Izoh:

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$ .

Misollar:

#	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 ms

Masala

Berilgan: 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?

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir test holati uchun bitta butun sonni chiqarish kerak: tanlangan $\bf{bo'sh \ emas}$ qism massivning maksimal yig'indisi.

Izoh:

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.

Misollar:

#	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 ms

Masala

Quyidagi 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))$ .

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir test holati uchun bitta butun sonni chiqarish kerak:
$\min(f(a))$ .

Izoh:

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.

Misollar:

#	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 ms

Masala

Berilgan 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Bitta butun son – shunday permutatsiyalarning soni, $10^9+7$ ga nisbatan moduli.

Izoh:

$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.

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 3	4

E. Kvadrat uchburchak

Xotira: 512 MB, Vaqt: 1000 ms

Masala

Sizga $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:

\sum_{i=l}^{r} \sum_{j=i}^{r} a_{i,j}

Kiruvchi ma'lumotlar:

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$ )

Chiquvchi ma'lumotlar:

Har bir so'rovga javobni chiqaring - bitta butun son.

Misollar:

#	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

#

INPUT.TXT

OUTPUT.TXT

1

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

F. Behruzbek va XOR so‘rovlar

Xotira: 512 MB, Vaqt: 2000 ms

Masala

Behruzbek 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir so'rov uchun javobni yangi qatorda chop eting.

Izoh:

$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$ .

Misollar:

#	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 ms

Masala

Bir 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.

Kiruvchi ma'lumotlar:

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$ .

Chiquvchi ma'lumotlar:

Bitta butun son, minimal nisbati $10^9 + 7$ moduli bo'yicha.

Izoh:

$n=4$ uchun eng yaxshi bo'linish quyidagicha:

$\{3,4\}$

$\{1,2\}$

javob quyidagicha bo'ladi:

$\frac{3 \times 4}{2 \times 1}=6$

Misollar:

#	INPUT.TXT	OUTPUT.TXT
1	1 4	6

H. Qo'shish

Xotira: 512 MB, Vaqt: 1500 ms

Masala

Jahonali 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.

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir $2$ turdagi so'rovga - bitta natural son chiqaring.

Misollar:

#	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 ms

Masala

Sizga 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

Kiruvchi ma'lumotlar:

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.

Chiquvchi ma'lumotlar:

Har bir so'rovga javobni chiqaring.

Izoh:

Birinchi so'rovni illyustratsiyasi:

Misollar:

#	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