المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۲۷

Gas Stations

شما می‌خواهید با استفاده از ماشین خود به یک سفر بروید. مسیری که شما باید طی کنید ‎$l$‎ متر طول دارد. باک ماشین شما حداکثر ‎$k$‎ لیتر بنزین می‌تواند در خود جای دهد و به ازای هر لیتر بنزین ‎$t$‎ متر می‌تواند حرکت کند.

در طول راه تعدادی پمپ بنزین وجود دارد که شما می‌توانید از هر کدام از آن‌ها مقداری (نه لزوماً صحیح) بنزین خریداری کنید و در باک خود بریزید. پمپ بنزین ‎$i$‎ام در فاصله ‎$p_i$‎ از شروع حرکت شما قرار دارد و قیمت بنزین آن برابر ‎$c_i$‎ واحد به ازای هر لیتر بنزین است. ‎ باک بنزین شما در ابتدا پر از بنزین است و شما می‌خواهید طوری مسافرت کنید که کم‌ترین هزینه لازم را برای رسیدن به مقصد خود خرج کنید. شما باید برنامه‌ای بنویسید که این کم‌ترین هزینه را به‌دست بیاورد.

ورودی

  • در سطر اول ورودی عدد ‎$1 \leq n \leq 50$‎ نشانگر تعداد پمپ بنزین‌ها آمده است.‎
  • در سطر بعدی، اعداد ‎$p_1$‎ تا ‎$p_n$‎ آمده است.‎
  • در سطر سوم، اعداد ‎$c_1$‎ تا ‎$c_n$‎ آمده است.‎
  • در آخرین سطر، سه عدد ‎$t$‎ و ‎$k$‎ و $l$‎ آمده است.‎
  • تمامی اعداد ورودی بین ‎$1$‎ و ‎$20000$‎ اند و ورودی طوری است که شما می‌توانید سفر خود را به پایان برسانید.

خروجی

در تنها سطر خروجی پاسخ سوال را با دقت ‎1‎ رقم اعشار چاپ نمایید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2‎
100 100‎
1000 1500‎
‎20 10 300
5000.0‎
3‎
300 450 525‎
1659 1529 1439‎
20 20 600
15277.5
3‎
‎300 450 525‎
1659 1529 1439‎
‎20 20 600
15277.5‎
3‎
300 450 525‎
1659 1439 1529‎
‎20 20 600
14940.0
4‎
300 125 450 525‎
1659 1729 1439 1529‎
20 20 600‎
14940.0

ابزار صفحه