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