A. Playoff #1

Xotira: 32 MB, Vaqt: 1000 ms
Masala

\(\space\space\space\space\space\)Bu yili yangi yil oldidan Qorboboning kayfiyati juda yaxshi, sababi u barcha elflari bilan birga futbol bo'yicha jahon chempionatini ko'rdi va u muxlislik qilgan jamoa chempion bo'ldi. Ammo bir holat uning anchagina asablarini charchatdi, ya'ni elflarning playoff bosqichi qoidalarini umuman bilmasligi. Elflar undan qoidalarni so'rayverishi joniga tekkandan so'ng, futbol ko'riladigan zalga katta qilib playoff qoidalarini osib qo'ydi:

\(\space\space\space\space\space\)- Dastlabki bosqichda barcha jamoalar 1 dan boshlab ketma-ket raqamlab chiqiladi.

\(\space\space\space\space\space\)- Har bir toq o'rindagi jamoa o'zidan keyingi turgan juft o'rindagi jamoa bilan o'ynaydi.

\(\space\space\space\space\space\)- G'alaba qozongan jamoalar keyingi bosqichga chiqadi. O'yinlar durang bilan yakunlanmaydi, har bir o'yinda qaysidir jamoa aniq g'alaba qozonadi.

\(\space\space\space\space\space\)- Keyingi bosqichga yo'l olgan jamoaning tartib raqami \(\lceil {x \over 2} \rceil\) ga o'zgaradi (\(x\) jamoaning joriy bosqichdagi tartib raqami).

\(\space\space\space\space\space\)- Oxirgi qolgan 1 ta jamoa musobaqa g'olibi hisoblanadi.

\(\space\space\space\space\space\)Sizning vazifangiz esa pleyoff bosqichiga \(N\) ta jamoa chiqganini bilgan holda musobaqa tugashigacha nechta bosqich qolganini topish.

\(\space\space\space\space\space\)Musobaqaning barcha bosqichlarida toq sondagi jamoalar bo'lib qolmasligi kafolatlanadi.

Kiruvchi ma'lumotlar:

\(N\) natural soni \((2\leq N \leq 2^{63})\)

Chiquvchi ma'lumotlar:

Qolgan bosqichlar sonini chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
2
 
1
2 
4
 
2

B. Playoff #2

Xotira: 32 MB, Vaqt: 1000 ms
Masala

\(\space\space\space\space\space\)"Playoff #1" masalasi shartini o'qigan bo'lsangiz, shunchaki sizga yangi vazifa beramiz.
\(\space\space\space\space\space\)Qorbobo muxlislik qilayotgan jamoa playoffning dastlabki bosqichida N-tartibda turgan bo'lsa, u chempionlikgacha har bir bosqichdagi raqiblarining tartib raqamini toping.

\(\space\space\space\space\space\)Musobaqaning barcha bosqichlarida toq sondagi jamoalar bo'lib qolmasligi kafolatlanadi.

Kiruvchi ma'lumotlar:

Birinchi qatorda playoffning dastlabki bosqichi va N natural soni probel bilan ajratilgan holda kiritiladi. Playoff bosqichlari quyidagicha belgilanadi, \(1/X\) (\(X\) - shu bosqichdagi jamoalar soni). Misol uchun bosqichda 8 ta jamoa bo'lsa \(1/8\) kabi belgilanadi. \((1 \leq N\leq2^{63}; 2 \leq X\leq2^{63})\)

Chiquvchi ma'lumotlar:

Har bir bosqichni va shu bosqichdagi qorbobo muxlislik qilayotgan jamoa raqibining tartib raqamini alohida qatorda chop eting.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
1/2 2
 
1/2 1
2 
1/4 4
 
1/4 3
1/2 1

C. Qorboboning ko'payadigan massivi

Xotira: 32 MB, Vaqt: 1000 ms
Masala

Qorbobo Shaxzodga sovg'a olishi uchun quyidagi topshiriqni bajarishi kerakligini aytdi (Tasavvur qilyapsizlarmi Qorbobo dasturlash bo'yicha topshiriq beryapti XD).
N ta natural sondan iborat A massiv va K butun soni mavjud. Massiv ustida quyidagi amallarni aynan K marta bajarish kerak:
    A massividagi eng katta sonni X deb olaylik.

  • X ni massivdan olib tashlash;
  • Agar X>1 bo'lsa, \(\lceil {X \over 2} \rceil\) va \(\lfloor {X \over 2} \rfloor\) ni massivga qo'shish;
  • Agar X\({\leq 1}\) bo'lsa X ni massivga qo'shish.

Yuqoridagi K ta amaldan keyin A massiv uzunligini to'g'ri aytsa Shaxzodga Qorbobo sovg'a beradi, aks holda Shaxzod sovg'a ololmaydi. Shaxzodga sovg'a olishda yordam bering.

P.S: \(\lceil a\rceil\)=ceil(a), \(\lfloor a \rfloor\)=floor(a).

Kiruvchi ma'lumotlar:

Birinchi satrda \(N \space (1\leq N \leq 2*10^{5} )\) natural son va  \(K \space (0 \leq K \leq 10^{9} )\) butun son kiritiladi.
Ikkinchi satrda \(N\) ta natural son \(A\space(1 \leq A_i \leq 10^{9})\) massiv elementari kiritiladi.

Chiquvchi ma'lumotlar:

K ta amalni bajargach A massiv uzunligini chop eting.

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

D. LRX

Xotira: 128 MB, Vaqt: 3000 ms
Masala

\(N\) soni va \(N\) ta 0 dan iborat \(A\) massiv mavjud. Sizdan massiv ustida quyidagi so'rovni \(Q\) marta bajarish so'raladi:
\(\space\space\space\space\)- L R X ko'rinishida so'rov beriladi, siz \(A\) massivning \([L,R]\) oralig'idagi har bir elementiga \(X\) sonini qo'shib chiqing.

Barcha so'rovlardan so'ng \(A\) massivning oxirgi holatini chop eting.

Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) va \(Q\) sonlari. Keyingi \(Q\) ta qatorda \(L, R, X\) sonlari beriladi.

\(1\leq N,Q\leq10^6;\)

\(1\leq L_i,R_i \leq N, \space |X_i|\leq 10^9, \space 1\leq i \leq Q\).

Chiquvchi ma'lumotlar:

\(A\) massivning barcha so'rovlar bajarilgandan keyingi holati.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 3
1 2 3
4 5 6
1 5 1
 
4 4 1 7 7
2 
6 4
1 3 4
1 2 3
3 6 100
1 6 -10
 
-3 -3 94 90 90 90

E. Matching

Xotira: 64 MB, Vaqt: 1000 ms
Masala

IELTS topshiriqlarida matching vazifalari mavjud. Bunda bir nechta savol va xuddi shuncha sonda javoblar mavjud bo'lib, savollarga to'g'ri javoblarni moslab chizish talab qilinadi.

Qorbobo ham elflari ingliz tilini yaxshi bilishini xohlaydi, chunki unga bolalar tomonidan yoziladigan xatlarning asosiy qismi ingliz tilida. Shuning uchun elflar IELTS matching topshirig'ini bajarishdi, qorbobo esa barcha elflardan nechta savolda xatoga yo'l qo'yganligini so'rab chiqdi. Bitta elfga kelganda qorbobo shubhalanib qoldi, rostdan ham shuncha xato qilish mumkinmi deya. Va Shimoliy qutbning bosh dasturchisi sifatida sizdan yordam so'radi. 

Sizga qorbobo savollar soni N, shubhali elf qilgan xatolar soni K va javoblarni berdi. Siz rostdan ham K ta xato qilish mumkin yoki yo'qligni aniqlashingiz kerak.

Kiruvchi ma'lumotlar:

Birinchi qatorda N va K butun sonlari \((1\leq N \leq 10^5;\space 0 \leq K \leq N).\)

Keyingi N ta qatorda ingliz alifbosi harflaridan iborat, uzunligi 10 dan oshmaydigan matching javoblari.

Chiquvchi ma'lumotlar:

K ta xato qilish mumkin bo'lsa YES, aks holda NO so'zini chiqaring

Izoh:

Har bir savol qaysidir javobga matching qilingan deb hisoblang, ya'ni javoblardan birortasi bo'sh qolmaydi. Bitta savolga ikkita javobni yoki bitta javobni ikkita savolga matching qilish mumkin emas.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 2
yangi
yil
yangi
bayram
xixi
 
YES
2 
4 3
New
year
year
New
 
NO

F. Do'st elflar

Xotira: 128 MB, Vaqt: 1500 ms
Masala

Shimoliy qutbda so'nggi yillarda dasturlashga e'tibor ancha kuchayib qoldi. Bu yili Qorbobo dasturchi elflarni bir joyga yig'ish maqsadida ular uchun ofis qurdirdi.

Dasturchi elflar oldindan alohida-alohida ishlagani uchun hech qaysi dasturchi elf bir-birini tanimaydi. Qorbobo esa jamoada hamma bir-birini tanishi muhim deb hisoblaydi. Shuning uchun u dasturchi elflarning ofisiga har kuni kelib ularni kuzata boshladi. U kuzatuvlarini yon daftariga quyidagicha yozib boradi.

  • \(!\space a \space b\) - a va b elfni birga yurganini ko'rsa shu ko'rinishda belgilab qo'yadi va ularni do'stlashgan deb hisoblaydi. Bu yerda a va b natural sonlardir, chunki Qorbobo elflarini raqamlab chiqqan (Kim ham minglab elf ismlarini eslab qolardi).
  • \(?\space a \space b\) - Qorbobo a va b elf do'stlashganmi deb o'ylab qolganda shu ko'rinishda belgilab qo'yadi. Bunda a elf b elf bilan va b elf c elf bilan do'st bo'lsa a elf c elf bilan ham do'st hisoblanadi (ya'ni do'stimning do'sti mening ham do'stim).

Siz Qorboboning yon daftaridagi har bir so'rovga javob bering. \(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st yoki do'st emasligini aniqlang.

Kiruvchi ma'lumotlar:

Brinchi qatorda N va Q sonlari \((1<N\leq 2*10^5; 1\leq Q \leq 2*10^5)\), mos ravishda dasturchi elflar soni va Qorboboning yon daftaridagi so'rovlar soni. Keyingi Q ta qatorda so'rovlar:
    \(!\space a \space b\) yoki \(?\space a \space b\) ko'rinishida \((a \not= b)\), kamida bitta \(?\space a \space b\) ko'rinishida so'rov borligi kafolatlanadi.

Chiquvchi ma'lumotlar:

\(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st bo'lsa 1 aks holda 0 chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
5 5
! 1 2
! 3 4
! 2 4
? 1 3
? 3 5
 
1 0
2 
5 3
? 1 2
! 1 2
? 1 2
 
0 1

G. Shaxzodning yangi yil sovg'asi

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Qorbobo Shaxzodga Yangi yilda yangi MacBook PRO 14 sovg'a qildi. Endi Shaxzod eski MacBookidagi hamma ma'lumotlarini yangisiga ko'chirishi kerak. Buning uchun u qo'shimcha SSD diskidan foydalanmoqchi. Lekin diskga uning hamma ma'lumotlari sig'mas ekan. Azimjonning hisob-kitobiga ko'ra Shaxzod ma'lumotlarini 2 martada o'tkaza olar ekan. Buning uchun u papkalarining o'lchamini iloji boricha bir-biriga yaqin qilib 2 ga ajratishi kerak. Bu ishni Azimjon osongina bajara oldi, siz ham urinib ko'ring ;)

Shaxzodning eski MacBookida hamma papkalari 0 dan boshlab raqamlab chiqilgan. 0 papka root hisoblanadi, ya'ni barcha fayl va boshqa papkalar 0 papkada joylashgan. 2 qismga ajratayotganda faqat 1 ta papkani 1 marta ko'chirish mumkin, ko'chirishda papkaning ichidagi barcha fayllar va papkalar birgalikda ko'chadi. Fayllarni ko'chirish yoki bir nechta papkani ko'chirish ma'lumotlar chalkashib ketishiga olib keladi.

Kiruvchi ma'lumotlar:

N natural soni va ikkinchi qatorda N ta butun sondan iborat A massiv beriladi. A massivning i-elementi i-papka qaysi papkaning ichida turganligini bildiradi, 0 papka uchun bu qiymat har doim -1 ga teng.

Keyingi N ta qatorning har birida \(K_j\) soni va \(K_j\) ta nomanfiy butun son, mos ravishda j-papkadagi fayllar soni va fayl o'lchamlari beriladi. Fayl o'lchamlari \(10^9\) dan oshmaydi.
\(0<N\leq10^4; \space 0\leq K_j \leq 100; \space 0\leq j <N.\)

Chiquvchi ma'lumotlar:

Ma'lumotlarni ajratganda hosil bo'ladigan eng kichik farqni toping.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
-1 0 0
0
1 13
2 3 10
 
0
2 
3
-1 0 0
1 1
1 13
2 3 10
 
1

H. Eeeelffff

Xotira: 512 MB, Vaqt: 2000 ms
Masala

Qorboboda sovg'a ulashishi kerak bo'lgan N ta bolaning ro'yxati bor edi. Qorbobo bu ro'yxatni ko'zdan kechirar ekan ro'yxat N o'lchamdagi P permutatsiya ekanligini tushunib qoldi. Qorbobo sovg'alarni ro'yxatdagi tartibda ulashishga qaror qildi va permutatsiyani yordamchi elfga saqlash uchun berdi.

Elf bekorchi vaqtida P permutatsiyadan foydalanib A massivini yasadi. Har bir \(A_i\) \((1\leq i \leq N)\) ning qiymati \(i\) son uchun P permutatsiyada \(i\) sondan o'ng tarafdagi o'zidan katta eng yaqin sonning qiymatini, agar bunday son mavjud bo'lmasa -1 qiymatni saqlaydi. Yaxshiroq tushunish uchun izohga qarang!

Lekin elf A massivni yasash uchun P permutatsiyani bo'yab tashladi. Endi u Qorbobodan gap eshitmasligi uchun permutatsiyani qayta tiklashi kerak. Elfga yordam bera olasizmi ?

Kiruvchi ma'lumotlar:

Birinchi qatorda N \((1 \leq N \leq 2*10^{5})\) natural son kiritiladi.
Ikkinchi qatorda N ta sondan iborat A massiv kiritiladi.

Chiquvchi ma'lumotlar:

N uzunlikdagi P permutatsiyani chiqaring.

Izoh:

P={2,3,1}
1 soni uchun o'zidan o'ng tarafda 1 dan katta son yo'q, demak \(A_1=-1;\)
2 soni uchun o'zidan o'ng tarafda 2 dan katta 3 soni mavjud, demak \(A_2=3;\)
3 soni uchun o'zidan o'ng tarafda 3 dan katta son yo'q, demak \(A_3=-1.\)
A={-1,3,-1}.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
-1 3 -1
 
2 3 1
2 
3
3 -1 -1
 
1 3 2

I. Shimoliy city

Xotira: 256 MB, Vaqt: 4000 ms
Masala

Quruvchi elflar va nihoyat Shimoliy citydagi barcha binolarni qurib bitkazishdi, endigi vazifa esa bu binolarni yo'llar orqali bog'lab chiqish. Qiyin tarafi esa yo'llarni Yangi yil bayramigacha bitkazish kerak, chunki Shimoliy qutbda asosiy bayramlarni yangi Shimoliy cityda o'tkazish rejalashtirilgan. Yo'llarni iloji boricha tez bitirish uchun esa hamma binolarni birlashtiruvchi eng qisqa yo'lni topish kerak.

Kiruvchi ma'lumotlar:

Sizga \(N\) natural soni va keyingi \(N\) ta qatorda \(X_i\), \(Y_i\) sonlari beriladi. \(X_i\), \(Y_i\) bu i-binoning joylashgan koordinatalari. Binolar 1 dan N gacha raqamlangan.
\(1\leq N \leq 1000;\)     \(-10^9 \leq X_i, Y_i \leq 10^9, \space i=\{1...N\}.\)

Chiquvchi ma'lumotlar:

Quruvchi elflarga eng qisqa yo'l uchun qaysi binolar o'rtasida yo'llar qurish kerakligini yozib bering. O'rtasida yo'l qurilishi kerak bo'lgan bino juftliklari sonini va keyingi qatorlarda juftliklarni probel bilan ajratgan holda alohida qatorlarda chop eting.
Agar bir necha xil javob mavjud bo'lsa, istalganini chop eting.

Izoh:

Siz bergan javob va muallif javobidagi yo'l uzunliklari farqi \(10^{-6}\) dan katta bo'lganda javobingiz noto'g'ri deb hisoblanadi.

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

J. Sonlar o`qidagi girlyanda #1

Xotira: 64 MB, Vaqt: 1250 ms
Masala

Masalaning #1 va #2 versiyalari tubdan farq qiladi. Ularni alohida masalalar sifatida hisoblash to`g`riroqdir.

Yangi yilda arafasida, yangi yil ruhini bag`ishlovchi har xil bezak buyumlari mavjud. Asilbekka eng yoqgani - girlyandadir. Uni istalgan joyga ossa bo`ladi, devorga, mebelga, archaga... Asilbek esa girlyandani sonlar o`qiga osilganini ham ko`rgan!

Asilbek o`zining sevimli sonlar o`qining musbat tomoniga qarasa, u to`liq girlyanda bilan bezatilgan ekan. Bunda \(a\) va \(b(a \neq b)\) sonlar girlyanda bilan bog`langan, agarda \(a|b\) yoki \(b|a\) (bir sonni ikkinchisini qoldiqsiz bo`ladi) sharti qanoatlantirsa.

Payqash qiyin emaski, 1 sonidan girlyandalar orqali boshqa barcha sonlarga borish mumkin. Girlyanda orqali faqat katta songa o`tish mumkin bo`lsa, 1 sonidan \(A\) sonigacha eng ko`pi bilan nechta o`tish yordamida yetib olsa bo`ladi?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 2*10^5)\) testlar soni kiritiladi.

Keyingi  \(T\) ta qaorning har birida bittadan butun son - \(A(2 \leq A \leq 10^7)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bitta butun son, masala javobini chop eting.

Izoh:

1-test:

1 dan 12 ga yetish uchun eng uzun yo`l: 1 -> 2 -> 6 -> 12

2-test:

1 dan 100 ga yetish uchun eng uzun yo`l: 1 -> 5 -> 25 -> 50 -> 100

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
12
4
7
 
3
2
1
2 
2
100
8
 
4
3

K. Uchburchaklar yasash

Xotira: 16 MB, Vaqt: 1250 ms
Masala

Yangi yilda arafasida eng ko`p tilga olinadigan geometrik figura - yulduz bo`lsa kerak. Chunki archaning uchida ham yulduz turadi, qor parchasini ham yulduzga o`xshatamiz va h.k. Ammo hozir Asilbek uchburchaklarga oid masala ishlamoqda.

Sizga dekart koordinatalar sistemasida \(K\) ta nuqta beriladi. Siz bu nuqtalardan \(N(3N \leq K)\)  ta uchburchak yasashingiz kerak. Bunda:

  • bitta nuqta ko`pi bilan bitta uchburchak yasashda qatnashishi mumkin;
  • yuzasi 0 ga teng uchburchak yasash taqiqlanadi;
  • hosil qilingan uchburchaklar yuzalari yig`inidisi minimal bo`lsin.
Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son - \(K,N(1 \leq N \leq 6, 3N \leq K \leq 20)\) kiritiladi.

Keyingi \(K\) ta qatorning har birida ikkitadan butun son - \(X,Y(-100 \leq X,Y\leq 100)\) navbatdagi nuqtaning koordinatalari kiritiladi.

Chiquvchi ma'lumotlar:

Birinchi qatorda bitta son, hosil qilingan \(N\) ta uchburchaklar yuzasi yig`inidisini chiqaring.

Keyingi \(N\) ta qatorning har birida uchburchak hosil qilgan uchlik nuqtalarning tartib raqamlarini chiqaring. To`g`ri javob bir nechta bo`lsa istalganini chiqaring. Uchburchaklarni va nuqtalarning tartib raqamlarini ham istalgan tartibda chiqarishingiz mumkin.

Agar shartlarni qanoatlantiruvchi \(N\) ta uchburchakni yasashning iloji bo`lmasa, yagona qatorda "IMPOSSIBLE" deb chiqaring.

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
4 1
0 0
4 0
0 3
0 10
 
6
1 2 3
2 
5 1
-1 -1
3 3
-2 -2
4 4
0 0
 
IMPOSSIBLE
3 
5 1
-1 -1
3 3
-2 -2
4 4
-2 1
 
1.5
3 5 1

L. Sonlar o`qidagi girlyanda #2

Xotira: 128 MB, Vaqt: 1000 ms
Masala

Masalaning #1 va #2 versiyalari tubdan farq qiladi. Ularni alohida masalalar sifatida hisoblash to`g`riroqdir.

Yangi yilda arafasida, yangi yil ruhini bag`ishlovchi har xil bezak buyumlari mavjud. Asilbekka eng yoqgani - girlyandadir. Uni istalgan joyga ossa bo`ladi, devorga, mebelga, archaga... Asilbek esa girlyandani sonlar o`qiga osilganini ham ko`rgan!

Asilbek o`zining sevimli sonlar o`qining musbat tomoniga qarasa, u to`liq girlyanda bilan bezatilgan ekan. Bunda \(a\) va \(b(a \neq b)\) sonlar girlyanda bilan bog`langan, agarda \(a|b\) yoki \(b|a\) (bir sonni ikkinchisini qoldiqsiz bo`ladi) sharti qanoatlantirsa.

Payqash qiyin emaski, 1 sonidan girlyandalar orqali boshqa barcha sonlarga borish mumkin. Girlyanda orqali faqat katta songa o`tish mumkin bo`lsa, 1 sonidan \(A\) sonigacha eng ko`pi bilan nechta o`tish yordamida yetib olish mumkinligini oldin hisoblagan edik. Sizning endigi vazifangiz bunday o`tishlar sonini hisoblashdir.

Boshqa so`zlar bilan, 1 sonidan A sonigacha eng ko`p girlyandalar orqali o`tishning necha xil usuli mavjud?

Kiruvchi ma'lumotlar:

Birinchi qatorda bitta butun son - \(T(1 \leq T \leq 2*10^5)\) testlar soni kiritiladi.

Keyingi  \(T\) ta qatorning har birida bittadan butun son - \(A(2 \leq A \leq 10^7)\) soni kiritiladi.

Chiquvchi ma'lumotlar:

Har bir test uchun yangi qatorda bitta butun son, masala javobini chop eting.

Izoh:

1-test:

12 ga yetib olish eng ko`pi bilan 3 ta girlyanda o`tishi orqali yetib borish mumkin. Bunday o`tishlar jami 3 xil.

1 -> 2 -> 4 -> 12

1 -> 2 -> 6 -> 12

1 -> 3 -> 6 -> 12

 

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
12
4
7
 
3
1
1
2 
2
100
1
 
6
1

M. Archa do`konida

Xotira: 64 MB, Vaqt: 1000 ms
Masala

Archasiz yangi yil bayramini tassavur qilib bo`lmasa kerak. Albatta, Asilbek ham shunday fikrda. Bundan tashqari uning fikricha archalar qancha ko`p bo`lsa shuncha yaxshi!

Ma'lum bir do`konda jami \(N\) ta archalar bor. \(i\)-archaning narxi \(a[i]\) $(dollar).

Asilbek sizga quyidagi so`rovdan \(Q\) marta beradi:

  • \(Y\) va \(X\) butun sonlari kiritiladi. X $(dollar) dan ko`p pul ishlatmagan holda kamida Y ta archa xarid qilishning nechta turli xil usuli mavjud? 

Sizing vazifangiz barcha so`rovlarga javob berishdir.

Ikki xarid bir xil hisoblanadi, agarda ikki xaridda ham sotib olingan archalar to`plami ustma-ust tushsa. Aks holda ular har xil.

Kiruvchi ma'lumotlar:

Birinchi qatorda yagona butun son - \(N(1 \leq N \leq 50)\) kiritiladi.

Ikkinchi qatorda \(N\) ta butun son - \(a\) massiv elementlari \((1 \leq a[i] \leq 1000)\) kiritiladi.

Uchinchi qatorda yagona butun son - \(Q(1 \leq Q \leq 5*10^5)\) so`rovlar soni kiritiladi.

Keyingi \(Q\) ta qatorning har birida ikkitadan butun son - navbatdagi so`rov uchun \(Y,X(1 \leq Y \leq 100, 1 \leq X \leq 2000)\) sonlari kiritiladi.

Chiquvchi ma'lumotlar:

Har bir so`rov uchun yangi qatorda, turli xil xaridlar usulini chop eting.

Izoh:

1-test:

2-so`rov uchun xaridlar: [1], [2].

4-so`rov uchun xarid: [1,2,3].

6-so`rov uchun xaridlar: [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].

7-so`rov uchun xaridlar mavjud emas.

2-test:

3-so`rov uchun xaridlar: [3,4], [3,5], [4,5].

5-so`rov uchun xaridlar: [1,2,3,4], [1,2,3,5], [1,2,4,5], [1,3,4,5], [2,3,4,5].

Misollar:
# INPUT.TXT OUTPUT.TXT
1 
3
1 2 3
7
1 1
1 2
2 2
3 3
3 6
1 10
7 12
 
1
2
0
0
1
7
0
2 
5
300 400 100 50 177
5
3 800
6 1000
2 300
3 1200
4 977
 
11
0
3
16
5
Kitob yaratilingan sana: 03-May-24 18:15