کمک در الگوریتم حریسانه

[Kamal]

سلام دوستان
خسته نباشید.

سوالم اینه:
فرض کنید میخاییم از تهران بریم مشهد توی مسیر پمپ بنزین های زیادی با فاصله از همدیگه هستند
به دلیل گران بودن خیلی زیاد بنزین الگوریتمی میخام بنویسم که با کمترین هزینه برای بنزین از تهران به مشهد برم
این اتومبیل تو هر کیلومتر یه لیتر بنزین مصرف میکنه و فاصله پمپ بنزین ها به کیلومتر هستش.
کاربر باید فاصله پمپ بنزین و قیمت هر کدوم رو وارد کنه و بعد کمترین هزینه محاسبه و نمایش داده بشه.

اینم یه مثال برای ورودی و خروجی
Sample Input
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399
Sample Output
450550

در ضمن اگه با توجه به ورودی امکان پذیر نبود پیغام "ناممکن" رو چاپ کنه

لطفا در مورد الگوریتم این برنامه به من توضیح بدید.

[مسعود اقدسی فام]

سلام دوستان
خسته نباشید.

سوالم اینه:
فرض کنید میخاییم از تهران بریم مشهد توی مسیر پمپ بنزین های زیادی با فاصله از همدیگه هستند
به دلیل گران بودن خیلی زیاد بنزین الگوریتمی میخام بنویسم که با کمترین هزینه برای بنزین از تهران به مشهد برم
این اتومبیل تو هر کیلومتر یه لیتر بنزین مصرف میکنه و فاصله پمپ بنزین ها به کیلومتر هستش.
کاربر باید فاصله پمپ بنزین و قیمت هر کدوم رو وارد کنه و بعد کمترین هزینه محاسبه و نمایش داده بشه.

اینم یه مثال برای ورودی و خروجی
Sample Input
100 999
150 888
200 777
300 999
400 1009
450 1019
500 1399
Sample Output
450550

در ضمن اگه با توجه به ورودی امکان پذیر نبود پیغام "ناممکن" رو چاپ کنه

لطفا در مورد الگوریتم این برنامه به من توضیح بدید.

میزان ظرفیت مخزن بنزین ماشین مشخص نیست؟ سوال کمی مبهم به نظر می‌یاد.

مثلا ورودی سطر اول چه مفهومی داره؟

[BOB]

سلام

چون روش حریصانه است، پس بهتر است به ترتیب (یعنی sort صعودی بر مبنای قیمت) در ارزان ترین پمپ بنزین های میان راه بنزین بزند.
ضمنا میتوان همواره مقدار بنزین باقیمانده در مخزن را نسبت به فاصله ای که با ارزانترین پمپ بنزین در ادامه راه داریم سنجیده و در صورت امکان از آنها استفاده کنیم.

[Kamal]

میزان ظرفیت مخزن بنزین ماشین مشخص نیست؟ سوال کمی مبهم به نظر می‌یاد.

مثلا ورودی سطر اول چه مفهومی داره؟

سپاس

مخزن 200 لیتری هستش و
سطر اول مثال یعنی
در کیلومتر 100 نسبت به مبدا یه پمپ بنزین هست که قیمت هر لیتر بنزینش 999 تمن