Masala #MGZ7JOYVIE
Tezkor xotira
Quvonchbek katta hajmdagi faylni USB fleshkaga saqlamoqchi. Uning ixtiyorida hajmlari mos ravishda \(a_1, a_2, ..., a_n\) bo‘lgan \(n\) ta USB fleshkasi mavjud. Fayl hajmi esa \(m\) megabaytga teng.
Agar faylni bir nechta fleshkalarga bo‘lib yozishga ruxsat berilgan bo‘lsa, Quvonchbek ushbu faylni saqlash uchun eng kamida nechta USB fleshka kerak bo‘ladi?
Kiruvchi ma'lumotlar:
- Birinchi qatorda bitta butun son \(n (1 ≤ n ≤ 100)\) — USB fleshkalar soni.
- Ikkinchi qatorda bitta butun son \(m (1 ≤ m ≤ 100000)\) — fayl hajmi megabaytda.
- Keyingi \(n\) ta qatorda har bir fleshkaning hajmi \(a_i (1 ≤ a_i ≤ 1000)\) keltiriladi.
Kafolatlanadi: barcha fleshkalar hajmlarining yig‘indisi \(m\) dan kam bo‘lmaydi — ya’ni faylni albatta saqlash mumkin.
Chiquvchi ma'lumotlar:
Faylni saqlash uchun kerak bo‘ladigan eng kam USB fleshkalar sonini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 2 1 3 |
2 |
| 2 |
3 6 2 3 2 |
3 |
| 3 |
2 5 5 10 |
1 |
Izoh:
Eslatma:
- Birinchi misolda, Quvonchbek faqat ikki dona USB fleshkaga ehtiyoj sezadi — birinchi va uchinchi fleshkalar yetarli bo‘ladi.
- Ikkinchi misolda, Quvonchbek faylni saqlash uchun uchala USB fleshkaning hammasidan foydalanishi kerak bo‘ladi.
- Uchinchi misolda, Quvonchbek faqat bitta USB fleshka bilan faylni saqlashi mumkin va u istalgan fleshkani tanlasa bo‘ladi — birinchi yoki ikkinchi.
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling