دستگاه برش «الواربر» ابزاری برای برش الوارهای چوبی است. این دستگاه به عنوان ورودی تعدادی الوار هم اندازهي ۱×n و یک عدد k (کوچکتر از n و بزرگتر از صفر) را می گیرد. سپس به طور همزمان و با یک برش عظیم هرکدام از الوارها را به دو تکه با اندازه های ۱×k و ۱×(n−k) تبدیل می کند. برای مثال می توانیم به این دستگاه سه الوار ۱×۵ بدهیم تا در یک حرکت آن ها را به سه تکهي ۱×۱ و سه تکهي ۱×۴ تبدیل کند.
سهراب یک الوار چوبی ۱×۱۰۰ به عنوان کادوی تولد از رستم هدیه گرفته است! او میخواهد با کمترین تعداد دفعه استفاده از دستگاه٬ این الوار طویل را به ۱۰۰ تکهی ٰ۱×۱ تبدیل کند. کمترین تعداد دفعه استفاده از دستگاه برای این منظور چند است؟
دقت کنید که همهی الوار های ورودی به دستگاه در یک مرحله٬ باید با هم هماندازه باشند.
پاسخ
گزینه ی «۲» درست است.
100∗1→50∗2→25∗4→12∗4+13∗4→12∗8+1∗4→6∗16+1∗4→3∗32+1∗4→
2∗32+1∗36→1∗100
(x∗y یعنی x چوب به طول y داریم). در نتیجه ۸ مرحله لازم است.