A. Hasan va Ikkilik Funksiya

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Quyidagi ikkilik satri ss berilgan bo'lib, u 0 yoki 1 dan iborat; ikkilik satrda ba'zi bir butun son nn ning ikkilik ko'rsatilishi ifodalangan. Sizdan quyidagi ifodani hisoblash so'raladi:

f(n)=log2(n)f(n) = ⌊\log₂(n)⌋

x\lfloor x \rfloor : xx dan kichik yoki teng maksimal butun sonni bildiradi, masalan 3.6 \lfloor 3.6 \rfloor =33 , 1.9999=1 \lfloor 1.9999 \rfloor=1 .

Misol uchun, s=1011s=1011 bo'lsa, u n=11n=11 ni ifodalaydi va f(11)=3f(11)=3 bo'ladi.
 

NOTE : f(0)=0f(0)=0

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son berilgan:  tt  (1t104)(1 \le t \le 10^4) – test holatlarining soni.  

Har bir test holatining birinchi qatori bitta butun sondan iborat:   nn   (1n2105)(1 \le n \le 2 \cdot 10^5) –  ss  satrining uzunligi.  

Har bir test holatining ikkinchi qatori nn uzunlikdagi ikkilik satr ss ni o‘z ichiga oladi.  

Shuningdek, testlarning umumiy  nn  yig‘indisi  21052 \cdot 10^5 dan oshmasligi kafolatlangan.
 

Chiquvchi ma'lumotlar:

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

Izoh:

Birinchi test holatida  n=2n=2  shunday qilib,  f(2)=1f(2)=1.  

Ikkinchi test holatida  n=7n=7  shunday qilib,  f(7)=2f(7)=2.  

To'rtinchi test holatida  n=62n=62  shunday qilib,  f(32)=5f(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  aa  massivi, uzunligi  nn  bo‘lgan  (a1,a2,...,an)(a_1, a_2, ..., a_n)  va bir butun son  kk .

Sizdan bo‘sh bo‘lmagan (ya’ni, kamida bitta elementdan iborat) qism massiv  al,al+1,...,ara_l, a_{l+1}, ..., a_r  ni tanlab, quyidagi operatsiyalardan birini bajarishingiz talab qilinadi:

1. Tanlangan qism massivning barcha elementlarini  kk  ga ko‘paytirish, ya’ni  ai:=kai(lir)a_i := k \cdot a_i \quad (l \le i \le r) .
2. Tanlangan qism massivning barcha elementlarini   kk ga bo‘lish, natijani pastga yaxlitlash bilan, ya’ni ai:=aik(lir)a_i := \left\lfloor \frac{a_i}{k} \right\rfloor \quad(l \le i \le r) .

x\lfloor x \rfloor xx ga teng yoki undan kichik bo‘lgan eng katta butun sonni ifodalaydi. Masalan, 3.5=3\lfloor 3.5 \rfloor = 3 va 3.5=4\lfloor -3.5 \rfloor = -4.

aa  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(1t104)t (1 \le t \le 10^4) – test holatlarining soni.

Har bir test holatining birinchi qatori ikkita butun sondan iborat:

nn, kk (1n21051 \le n \le 2 \cdot 10^5, 109k109-10^9 \le k \le 10^9) – massiv uzunligi aa va butun son kk.

Har bir test holatining ikkinchi qatori nn ta ajratilgan butun sonlarni o‘z ichiga oladi: a1,a2,...,ana_1, a_2, ..., a_n (104a1,a2,...,an104-10^4 \le a_1, a_2, ..., a_n \le 10^4) – massiv aa.

Shuningdek, nn ning yig‘indisi barcha testlarda 21052 \cdot 10^5 dan oshmasligi kafolatlangan.


 

Chiquvchi ma'lumotlar:

Har bir test holati uchun bitta butun sonni chiqarish kerak: tanlangan bosh emas\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=4010 + 5 + 10 + 5 + 10 = 40.

Ikkinchi test holatida, butun massivni tanlab, ko'paytirish amali bajarish optimal bo'ladi, 3×20=603 \times 20 = 60.

Uchinchi test holatida, [1][1] massivini tanlab, uni 44 ga ko'paytirish optimal bo'ladi, natijada javob 44 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: aa uzunligi nn bo'lgan butun sonlardan iborat. Keling, massivning f(a)f(a) funksiyasini aniqlaymiz, u massivdagi turli xil (unikal) butun sonlar soniga teng bo'ladi aa.

Masalan, f([1,2,4,4,2])=3f([1, 2, 4, 4, 2]) = 3 , chunki unda uchta turli xil son mavjud: {1,2,4}\{1,2,4\}.

Siz faqat bitta amalni bajarishga ruxsat berilgansiz: uzunligi kk bo'lgan istalgan qism massivni tanlab, uni olib tashlash.

Masalan, agar a=[1,2,4,4,2]a =[1, 2, 4, 4, 2] va k=2k = 2, bo'lsa, agar 3-chi va 4-chi elementlarni olib tashlasak, hosil bo'lgan massiv[1,2,2][1, 2, 2]   bo'ladi vaf(a)=2f(a)=2

Operatsiyani bajargandan so‘ng, min(f(a))\min(f(a)) .

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son berilgan:  
t(1t104)t (1 ≤ t ≤ 10^4 ) – test holatlarining soni.  

Har bir test holatining birinchi qatori ikkita butun sondan iborat:  
nn va kk (1k<n21051 ≤ k < n ≤ 2·10^5 ) – mos ravishda massiv uzunligi va olib tashlanadigan qism massiv uzunligi.  

Har bir test holatining ikkinchi qatori  
nn ta butun sonni o‘z ichiga oladi:  
a1,a2,..,ana_1,a_2,..,a_n (1ai10111 ≤ a_i ≤ 10^{11} ).  

Shuningdek, nn ning yig‘indisi 41054 · 10^5 dan oshmasligi kafolatlangan.  

Chiquvchi ma'lumotlar:

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

Izoh:

Birinchi test holati uchun:
Qaysi qism massivni tanlamang, natija har doim 11 ga teng bo'ladi.  

Ikkinchi test holati uchun:
Qism massivni tanlashning ikki usuli mavjud: [1,2][1,2] yoki [4,4][4,4]
va hosil bo'lgan massiv ikkala holatda ham 22 ta turli xil sonlarga ega bo'ladi.  

To‘rtinchi test holati uchun:
Siz [8,3,6][8,3,6] ni tanlashingiz kerak va hosil bo'lgan massiv  
[2,1,4,7,6,4,7][2,1,4,7,6,4,7] bo‘ladi, bu holda qiymat 44 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 nn, uzunligi nn bo'lgan nechta permutatsiya mavjudligini hisoblang, unda faqat bitta indeks ii mavjud bo'lib, u pi>ip_i > i shartini qanoatlantiradi . Javobni 109+7 10^9+7 ga bo'lgandagi qoldig'ini hisoblang.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son  t t (1t104) (1 \le t \le 10^4)  — testlar soni.

Har bir testning faqat bitta qatori bor, unda bitta butun son  n n  (1n1018) (1 \le n \le 10^{18})  — p p permutatsiyasining uzunligi.

Chiquvchi ma'lumotlar:

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

Izoh:

n=3n = 3 uchun, amalga oshirilgan permutatsiyalar:

1. [1,3,2] [1, 3, 2] , bu yerda p2=3>2 p_2 = 3 > 2
2. [2,1,3] [2, 1, 3] , bu yerda p1=2>1 p_1 = 2 > 1
3. [3,1,2] [3, 1, 2] , bu yerda p1=3>1 p_1 = 3 > 1
4. [3,2,1] [3, 2, 1] , bu yerda p1=3>1 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 nnn \cdot n   aa jadval berilgan, va sehirgar agar siz qq 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:

ll va rr (lr)(l \le r)beriladi sizni vazifangiz shunday ai,ja_{i, j} lar summasini topshingiz kerak lijrl≤i≤j≤r sharti bajariladi. Rasmiy ravishda:
 

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

 

Kiruvchi ma'lumotlar:

Birinchi qatorda nn va qq1n25001 \le n \le 25001q2000001 \le q \le 200000) - satr va qatorni uzunligi va so'rovlar soni.

Keyingi nn qatorda jadval aa(ai,j109a_{i,j} \le 10^9).

Keyingi qq qatorda so'rovlar, har bir so'rovda ll va rr beriladi(1lrn1 \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

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 nn bo'lgan aa massiv hamda [l,r,x,y][l,r,x,y] turdagi  qq ta so'rovlar berdi . Har bir so'rov uchun Behruzbekdan a[l:r]a[l:r] qismida joylashgan va qiymatlari [x,y][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 tt (1t1000) (1 \le t \le 1000) - testlar soni.

Har bir test uchun birinchi qatorida ikkita butun son mavjud n,qn,q  (1n,q4×105 (1 \le n,q \le 4\times 10^5 ) -  aa massiv uzunligi va so'rovlar soni.

Keyingi qatorda  nn ta butun sonlar a1,a2,..,ana_1,a_2,..,a_n  (1a1,a2,..,an109) (1 \le a_1,a_2,..,a_n \le 10^9) - aa massiv elementlari kiritiladi.

Keyingi qq  ta qatorning har birida  44 ta butun son l,r,x,yl,r,x,y (1lrn) (1 \le l \le r \le n) (1x,y109) (1 \le x,y \le 10^9) kiritiladi.

n+qn+q umumiy testlar summasi 8105 8\cdot 10^5 dan oshmasligi kafolatlangan.

Chiquvchi ma'lumotlar:

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

Izoh:
  1. 11-so'rov [5,1,4,2,3][5, \color{red}{\underline{\bf{1}}} \color{white}, 4, 2, 3] massivini oladi. Elementlardan faqat bittasi [1,1][1,1] oralig'ida. Javob: 11.
  2. 22-so'rov  [5, 1, 4, 2, 3][ \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][1, 100] diapazonni oladi. Javob: 51423=15 ⊕1 ⊕ 4 ⊕ 2 ⊕ 3 = 1.
  3. 33-so'rov  [5,1,4] [ \color{red}{\underline{\bf{5}}} \color{while}{,} 1 , \color{red}{\underline{\bf{4}}} \color{while}{]} pastki qator (subarray)  va [2,100][2, 100] oraliqni oladi. Javob: 54=15 ⊕ 4 = 1.
  4. 44-so'rov  [1,4] [ 1 , \color{red}{\underline{\bf{4}}} \color{while}{]} pastki qator (subarray) va [2,100] [2,100] diapazonni oladi. Javob: 44.
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 nn ta ishtirokchi bor, har birining kuchi sis_i bo'lib, (1sin)(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)(T) quyidagicha aniqlanadi:

T1×T2××TmT_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 109+710^9 + 7 ga bo'lganda chiqaring.
 

E'tibor bering, (n=1)(n=1) uchun javob 1 ga teng.

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son tt (1t104)(1 \leq t \leq 10^4) — test holatlari soni.

Har bir test holatining yagona qatorida bitta butun son nn (1n106)(1 \leq n \leq 10^6) — ishtirokchilar soni.
 

Bu miqdor kafolatlangan nn oshmaydi 10610^6.

Chiquvchi ma'lumotlar:

Bitta butun son, minimal nisbati 109+710^9 + 7 moduli bo'yicha.
 

Izoh:

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

{3,4}\{3,4\}

{1,2}\{1,2\}

javob quyidagicha bo'ladi:

3×42×1=6\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 aa massivga ega(a=0|a|=0). Shundan so'ng, qq ta hodisa sodir bo'ladi Har bir hodisa quyidagilardan biri bo'lishi mumkin:

1 i x1 \ i \ x - yangi element xx ni aia_{i} va ai+1a_{i+1} orasiga qo'shish. Yangi massiv shunday bo'ladi:

[a1,a2,,ai,x,ai+1,,aa][a_1, a_2, \dots, a_i, x, a_{i+1}, \dots, a_{|a|}]

2  i2  \ i - ii-chi elementni chiqarish ya'ni aia_{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|x|- Bu yerda xx massivni uzunligi. 

Kiruvchi ma'lumotlar:

Birinchi qatorda qq(1q51051 \le q \le 5 \cdot 10^5) - hodisalar soni.

Keyingi qq ta qatorda quyidagi berilgan hodisalardan bitta bo'ladi har bir hodisa uchun:

1 i x1 \ i \ x (0ia0 \le i \le |a|1x10181 \le x \le 10^{18} ) - yangi element xx ni aia_{i} va ai+1a_{i+1} orasiga qo'shish. 

2 i2 \ i  (1ia1 \le i \le |a|) - ii-chi elementni chiqarish ya'ni aia_{i}.


x|x| - Bu yerda xx massivni uzunligi. 

Chiquvchi ma'lumotlar:

Har bir 22 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 nn ta tugundan tashkil topgan tt daraxt bergan. Har bir tugunda sonlar yozilgan ya'ni ii -chi tugun uchun unda yozilgan son - aia_{i} , sizga qq  ta so'rovga javob berishingiz kerak. Har bir so'rovda xxll va rr(1lrn1 \le l \le r \le n) berilgan. Aytaylik qanaqadir ii va jj tugunlar uchun ular orasidagi ma'sofani d(i,j)d(i,j) deb belgilab olaylik, sizni vazifangiz shunday aia_{i} lar yig'indisini topishingiz kerak ld(x,i)rl \le d(x, i) \le r sharti bajarilishi kerak. Rasmiy ravishda:

itld(x,i)rai\sum_{\substack{i \in t \\ l \leq d(x, i) \leq r}} a_i
Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita natural sonlar nn va qq(2n,q1052 \le n,q \le 10^5, ) - Daraxtdagi tugunlar soni va so'rovlar soni.

Ikkinchi qatorda nn ta natural sondan tashkil topgan aa massiv (1ai1091 \le a_{i} \le 10^9).

Keyingi n1n-1 ta qatorda tt daraxtni ikkita tugunlari uu vavv(1u,vn1 \le u,v \le n) - uu va vv ni bog'lab turuvchi yo'l.

Keyingi qq ta qatorda xxll va rr(1xn1 \le x \le n1lrn1 \le l \le r \le n). Agar [l,r][l,r] oralig'ida qaysidir tugun yo'q bolsa u tugundagi qiymatini 00 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
Kitob yaratilingan sana: 06-Jun-25 20:59