رضا یک رستوران تاسیس کرده که در طبقهی آخر ساختمانی ضد زلزله قرار دارد. در صورت وقوع زلزله، ساختمان به چپ متمایل میشود رضا میز در رستوان دارد که میز ام در فاصله متری درب ورودی قرار دارد (توجه کنید میتواند منفی یا مثبت باشد؛ منفی یعنی میز سمت چپ و مثبت یعنی میز سمت راست درب قرار دارد).
مدیر ساختمان به رضا هشدار داده اگر ساختمان به چپ متمایل شود، میزها به چپ لیز میخورند مگر اینکه آنها را به کف زمین بچسباند. در واقع هر میزی که به زمین چسبیده باشد حرکت نمیکند، در غیر این صورت اینقدر به چپ لیز میخورد تا به میز سمت چپش برسد (فرض کنید عرض میزها آنقدر کم است که چندین میز میتواند در یک فاصله از درب قرار گیرد). همچنین اگر در سمت چپ میزی که به زمین نچسبده، میزی نباشد، از پنجره به بیرون پرت میشود و رستوران بسته میشود. رضا تصمیم گرفته بعضی میزها را به زمین بچسباند و باقی را بعد از پایان زلزله هل داده و به جای اصلیشان برگرداند.
رضا به شاگردش پول میدهد تا کارها را انجام دهد. شاگرد به ازای هر یک متری که میزی را هل دهد، هزار تومان میگیرد. پول چسباندن میز ام به زمین، هزار تومان است. (که میتواند مثبت یا منفی باشد، در صورتی که منفی باشد، رضا از شاگردش بابت چسباندن میز پول میگیرد!)
شما باید برنامهای بنویسید که در صورت وقوع زلزله، کمترین هزینهی ممکن برای چسباندن و هل دادن میزها را حساب کند.
توجه داشته باشید نباید میزی از پنجره بیرون بیفتد وگرنه رستوران بسته و رضا ورشکسته میشود.
در اولین خط عدد یعنی تعداد میزها آمده است. در خط دوم، عدد میآید که ها هستند. تضمین میشود هیچ دو میزی در ابتدا در یک نقطه قرار ندارند.
در نهایت در خط سوم، عدد میآید که ها هستند.
در تنها خط خروجی، کمترین هزینهی ممکن برای چسباندن و هل دادن میزها را چاپ کنید.
کافیست تنها چپترین میز چسبانده شود. در اینصورت ۵ هزار تومان هزینهی چسباندن آن است و دو میز دیگر به سمت آن میلغزند و هزینهی هل دادن آنها به جایگاه اولشان، ۱۰ + ۲ = ۱۲ هزار تومان است و جمعا ۱۷ هزار تومان هزینه میکنیم.
در این مثال بهتر است همهی میزها را به زمین بچسبانیم و در مجموع ۹۷ هزار تومان خرج میکنیم.
میز دوم باید چسبانده شود تا از پنجره بیرون نیفتد. اگر میز اول و دوم و چهارم را بچسبانیم ۱۰ هزار تومان هزینه میدهیم. ۲ هزار تومان هم هزینهی هل دادن میز سوم است و در مجموع ۱۲ هزار تومان هزینه میکنیم.
بهترین جواب، چسباندن میز اول و چهارم است که باعث میشود سه میز دیگر لیز بخورند و هزینهی هل دادن آنها، ۴ هزار تومان و هزینهی کل، ۱۰ هزار تومان شود.