اخیرا شایعه شده تعدادی از شخصیت‌های سابق المپیاد کامپیوتر سعی بر جوسازی علیه خیکوله را داشته‌اند. برای همین او که خود را قهرمان بلامنازع تمامی دوران‌های المپیاد می‌دانست، از شخصیت‌های مدعی دعوت به عمل آورد تا در یک رقابت هرآن‌چه در توان دارند به نمایش بگذارند و به چشم خود به قدرت خیکوله پی ببرند!

رقابت به این شکل است که که خیکوله باید از یک راهرو عبور کند. $n$ شخصیت مدعی به ترتیب در طول این راهرو ایستاده‌اند. انرژی خیکوله در ابتدا برابر $k$ (بیشترین مقدار ممکن) است و پس از مبارزه با قهرمان $i$ام انرژی‌اش به مقدار $c_i$ کاهش پیدا می‌کند. اگر انرژی خیکوله به صفر (یا کمتر از آن) برسد او جان خود را از دست می‌دهد!

خیکوله پس از شکست دادن قهرمان $i$ام هرچند ساعت که بخواهد می‌تواند استراحت کند و به ازای هر یک ساعت استراحت انرژی‌اش به میزان $e_i$ افزایش پیدا می‌کند. (توجه کنید که به ازای هر $i$، $e_i$ها ها فرق می‌کند.) البته انرژی او هیچگاه از مقدار $k$ بیشتر نمی‌شود. هدف خیکوله این است که با صرف کمترین زمان برای استراحت، همه‌ی قهرمان‌ها را شکست دهد و به آخر راهرو برسد.

1. فرض کنید که خیکوله می‌تواند در یک مکان کسری از ساعت (و نه لزوما مضربی از ساعت) استراحت کند. در این حالت الگوریتمی خطی ارائه کنید که کمترین زمان برای عبور از راهرو را حساب کند.
2. فرض کنید که خیکوله در یک مکان فقط به تعداد مضارب صحیح از یک ساعت می‌تواند استراحت کند. در این صورت آیا الگوریتم بالا نیاز به تغییر دارد؟ اگر جواب‌تان مثبت است تغییرات لازم را توضیح دهید.

• سوال قبل