Masala #0972
Archa do`konida
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.
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.
Har bir so`rov uchun yangi qatorda, turli xil xaridlar usulini chop eting.
| # | 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 |
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].
Telegram kanalimizga obuna bo'ling