- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
امروز روز جهانیه ریاضیاته! و «بهینهسازی» یکی از کاربردی ترین مباحث اونه...
دکتر غلامحسین مصاحب
مجموعهای از فایلها داریم و قصد داریم آنها را فقط با استفاده از یک فلش، از کامپیوتر مبدا به کامپیوتر مقصد منتقل کنیم.
در هر انتقال زیرمجموعهای از این فایلها را انتخاب میکنیم و همه را روی فلش ریخته و در کامپیوتر مقصد خالی میکنیم، با رعایت این نکته که حجم این زیرمجموعه از فایلها نباید از ظرفیت فلش بیشتر شود.
ما بینهایت تنبل هستیم در نتیجه میخواهیم با کمترین تعداد انتقال این کار را انجام دهیم. از آنجایی که شما برنامهنویسی بلد هستید، با گرفتن تعداد و حجم فایلها به همراه ظرفیت فلش در ورودی، این کمترین تعداد بار را خروجی چاپ کنید.
ورودی
در خط اول ورودی دو عدد طبیعی \(n\) و \(C\) با یک فاصله از هم آمدهاند که به ترتیب تعداد فایلها و ظرفیت فلش را مشخص میکنند.
\[ 1 \le n \le 18 \] \[ 1 \le C \le 100 \]
در خط دوم \(n\) عدد طبیعی با فاصله از هم آمدهاند. عدد \(i\)ام، \(v_i\) است که حجم فایل \(i\)ام را مشخص میکند.
\[ 1 \le v_i \le C \]
خروجی
در تنها خط خروجی کمترین تعداد انتقال این فایلها روی فلش را خروجی دهید.
مثال
ورودی نمونه ۱
3 10
2 4 3
خروجی نمونه ۱
1
مجموع حجم سه فایل میشود ۹ که از ظرفیت فلش(۱۰) کمتر است، پس تنها با یک بار انتقال میتوانیم به خواستهی مسئله برسیم.
ورودی نمونه ۲
4 15
2 10 5 13
خروجی نمونه ۲
2
در راه حل بهینه، ابتدا دو فایل با حجمهای ۲ و ۱۳ و در دور دوم فایلهای با حجم ۱۰ و ۵ را منتقل میکنیم.