المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:عملی نهایی اول:سوال ۳

Money

حمید در حساب خود ‎$k$‎ ریال پول دارد. می‌دانیم که او باید شب روز ‎$d_1$ $c_1$‎ ریال ، شب روز ‎$d_2$ $c_2$‎ ریال و ‎$\ldots$‎ و شب روز ‎$d_n$ $c_n$‎ ریال پول بابت پول‌هایی که از دوستان خودش قرض گرفته به دوستان خودش پس بدهد. از آنجایی که او هیچ منبع درامدی ندارد ، تنها راهی که می‌تواند با استفاده از آن بدهی‌های خودش را پس بدهد خرید بسته‌های بیمه است. خرید بسته بیمه به این صورت است که در صورتی که حمید در روز ‎$i \geq 1$‎ام حداقل ‎$h$‎ واحد پول داشته باشد می‌تواند یک بسته بیمه بخرد و از روز ‎$i+1$‎ام به بعد صبح هر روز ‎$q$‎ ریال به حساب او پول واریز می‌شود. حمید می‌تواند در یک روز بیش از یک بسته بیمه بخرد ولی او می‌تواند حداکثر ‎$X$‎ بسته بیمه خریداری کند. شما باید برنامه‌ای بنویسید که به دست بیاورد آیا حمید می‌تواند طوری عملی کند که همه بدهی‌های خود را بدهد؟ در صورتی که جواب مثبت است باید روشی را چاپ کنید که با خرید کمترین تعداد بسته بیمه این کار را انجام دهد.

ورودی

  • در سطر اول ورودی عدد ‎$(1 \leq t \leq 10)$‎ نشان دهنده تعداد تست‌های ورودی آمده است.‎
  • در هر یک از ‎$t$‎ تست ورودی در سطر اول پنج عدد ‎$(0 \leq k \leq 10^9)$‎ ، ‎$(0 \leq X \leq 4000)$‎ ، ‎$(0 \leq h \leq 10^9)$‎ و ‎$(0 \leq q \leq 10^3)$‎ و ‎$(1 \leq n \leq 4000)$‎ آمده است.
  • در سطر دوم هر تست ‎$n$‎ عدد ‎$(1 \leq d_i \leq 10^9)$‎ آمده است. در سطر بعدی ‎$n$‎ عدد ‎$(1 \leq c_i \leq 10^9)$‎ آمده است. امکان دارد برخی از ‎$d_i$‎ها با هم برابر باشند.

خروجی

‎ به ازای هر تست در صورتی که این کار امکان‌پذیر نیست در یک سطر کلمه ‎NO‎ و در غیر این صورت کلمه ‎YES‎ را چاپ کنید و در سطر بعدی عدد ‎$r$‎ نشان دهنده تعداد بیمه‌هایی که حمید باید بخرد و پس از آن ‎$r$‎ عدد بنویسید که روزهایی که حمید باید بسته‌های بیمه را بخرد را نشان می‌دهد. در صورت وجود چند جواب برای یک تست یکی از آن‌ها را چاپ کنید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
2‎
3 100 2 2 1‎
3‎
5‎
2 100 3 2 1‎
3‎
4‎
YES‎
1 1‎
NO‎

ابزار صفحه