Masala #0922
Muzqaymoq do‘konidagi avtomat
“Ice&Dance” muzqaymoq do‘koni o‘z mahsulotlari shirinligi tufayli bugungi kunda juda mashhur. Bu do‘konda \(N\) turdagi muzqaymoq turlari mavjud (mevali muzqaymoq, qaymoqli muzqaymoq, shokoladli muzqaymoq va h.k.). \(i\)-turdagi muzqaymoqning narxi mos ravishda \(c_i\) dir.
Do‘kondagi muzqaymoqlar shunchalik mazzaliki, xaridorlar iloji boricha barcha pulini muzqaymoq xaridiga ishlatishga harakat qiladi. Lekin so‘nggi kunlarda xaridorlar muzqaymoq tanlashda qiynalayotgani sababli do‘konda xizmat ko‘rsatish jaroyoni sekinlashib ketdi.
Yaqinda, do‘kon egasining buyurtmasiga ko‘ra, do‘konga maxsus avtomat olib kelishdi. Ushbu avtomatga xaridor hamyonidagi pul miqdorini kiritishi bilan unga pulini maksimal darajada sarflovchi xaridni ko‘rsatadi.
Bugun do‘konga \(Q\) nafar xaridor kelishi ma’lum, hamda k-xaridor o‘zi bilan ak miqdorda pul olib keladi. Bunda har bir xaridor maxsus avtomatdan foydalanishi aniq.
Sizning vazifangiz shu avtomat dasturini yaratishdir. Boshqa so‘zlar bilan aytganda, har bir xaridor uchun uning pulini maksimal darajada sarflovchi xaridga misol keltirishdir. Agar xaridor pulini maksimal darajada ishlatuvchi xaridlar bir nechta bo‘lsa, istalganini chiqaring.
Birinchi qatorda bitta butun son - \(N(1 ≤ N ≤ 100)\) muzqaymoq turlari soni kiritiladi. Keyinga qatorda \(N\) ta butun son - \(c\) massiv elementlari kiritiladi. \(c_i(1 ≤ c_i ≤ 1000)\) mos
ravishda \(i\)-turdagi muzqaymoqning narxi.
Bundan so‘ng yangi qatorda bitta butun son - \(Q(1 ≤ Q ≤ 100)\) xaridorlar soni kiritiladi.
Keyingi qatordan \(Q\) ta butun son - \(a\) massiv elementlari kiritiladi. \(a_k\)\((1 ≤ a_k ≤ 3000)\) mos ravishda \(k\)-inchi xaridorning hamyonidagi pul miqdori.
Har bir xaridor uchun 2 qator natija chiqaring:
- birinchi qatorda \(a_k\) pul miqdoridan sarflash mumkin bo‘lgan eng maksimal pul miqdori;
- ikkinchi qatorda \(N\) ta butun son. \(i\)-son shu xaridor \(i\)-turdagi muzaqaymoqdan nechta olishi kerakligi.
Agar xaridor pulini maksimal darajada sarflovchi xaridlar bir nechta bo‘lsa, istalganini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 2 12 2 4 7 4 4 7 1 9 3 16 |
4 0 0 0 0 1 4 0 1 0 1 0 7 1 0 0 2 0 0 0 0 0 0 0 9 1 2 0 1 0 3 1 0 0 0 0 16 0 2 1 0 0 |
| 2 |
3 4 4 4 2 7 16 |
4 0 1 0 16 1 1 2 |
1-testda:
Birinchi xaridor 4 birlik pul olib keladi. U pulini to‘liq sarflovchi turli xil xaridlar qilishi mumkin. U muzqaymoqning 5-turidan bitta yoki 2-turidan ikkita olishi mumkin. Yoki 2- turidan bitta hamda 4-turidan bitta xarid qilishi mumkin.
Uchinchi xaridor olib kelgan pul miqdori hech qaysi muzqaymoqga yetmaydi, shuning uchun uning xarid turi yagona: muzqaymoqning barcha turidan 0 dona, yani olmaslik.
2-testda:
Birinchi xaridor 7 birlik pul bilan keladi. Afsuski, u hech qanday usul bilan barcha 7 birlik pulini ishlata olmaydi. Ammo 4 birlik ishlatishi mumkin. Buning uchun istalgan muzqaymoqdan bitta olishi kerak.
Telegram kanalimizga obuna bo'ling