مساله H : هتل (لطفا تا آخر همراهی کنید)
مسعود (مسول تدارکات سفر) قصد داره که تعدادی اتاق برای مسافران رزرو کنه.اتاقها ظرفیت های مختلف و قیمت های مختلفی دارن
مسعود قصد داره که کمترین هزینه رو پیدا کنه بدین منظور او باید از بین اتاق های موجود، اتاق ها رو طوری به مسافران اختصاص بده که هزینه کلی کمترین باشه
یک محدودیت کوچولو برای این کار وجود داره:
اگه خواستیم یک اتاق رو به دو جنس مختلف اختصاص بدیم، اون دو باید حتما زن و شوهر باشن و در این صورت دیگه هیچ کس نمیتونه از این اتاق استفاده کنه
حال با این شرایط شما باید برنامه ای بنویسید که این کار را برای مسعود انجام بده (به ورودی و خروجی برنامه توجه کنید)
---------------------------
ورودی برنامه :
ورودی برنامه شامل موارد زیر است:
0<m<500
تعداد مردها
0<f<500
تعداد زنها
0<r<500
تعداد اتاقها
c>0
تعداد روابط زناشویی بین افراد
نکته : چند همسری نداریم
همچنین به ازای هر اتاق(r) یک ظرفیت و یک قیمت وجود داره که در ادامه ورودی خواهد آمد:
0<bi<5
ظرفیت اتاق
0<pi<1000
قیمت اتاق
خروجی برنامه :
پیدا کردن کمترین هزینه ممکن. (اتاق ها رو طوری به مشتریان اختصاص بدیم که هزینه کل کمترین باشه)
و در صورتی که اختصاص اتاقها غیر ممکن باشه برنامه باید "Impossile" برگردونه. (به مثال توجه کنید)
---------------------------
مثال :
ورودی برنامه:
2 1 3 1
3 5
2 10
2 4
تعداد مردها : 2
تعداد زنها : 1
تعداد اتاق ها : 3
تعداد روابط زناشویی : 1
خروجی برنامه 9 است
چون اتاق آخر به زن و شوهر اختصاص داده میشه : 4
و اتاق اول هم به یک نفر مرد باقی مانده : 5
مثال 2 :
ورودی :
1 1 1 0
1 4
خروجی :
Impossible