المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۶:سوال ۱

روبات رولت‌بر

شیرینی‌فروشی «‌پای‌تک»، یک شیرینی‌فروشی مدرن است که حتی برای برش رولت‌هایش از روبات استفاده می‌کند. یک روبات رولت‌بر، تنها می‌تواند رولت‌هایی که طولشان توانی از $2$ است، برش دهد. یک رولت به طول $2^n$ را می‌توانید به صورت یک نوار با طول $2^n$ در نظر بگیرید.

برای شروع برش زدن، رولت‌بر عدد $k$ را که نشان‌دهنده‌ی تعداد تکه‌هایی است که باید رولت به آن تقسیم شود، به عنوان ورودی دریافت می‌کند. سپس، رولت‌بر در هر مرحله می‌تواند تیغه‌‌ی برش خود را به وسط یکی از قسمت‌هایی که طولش زوج است ببرد و آنجا را برش دهد. برای انتقال تیغه‌ی رولت‌بر از مکان $x$ به مکان $y$، $|x-y|$ ثانیه زمان لازم است. در ابتدا تیغه‌ی رولت‌بر در چپ‌ترین قسمت رولت (مکان صفر) قرار دارد. هم‌چنین می‌توانیم از زمان برش زدن صرف نظر کنید. واضح است برای این‌که رولت به $k$ قسمت تقسیم شود، $k-1$ برش نیاز است.

برای نمونه، دو روش تقسیم رولتی به طول $2^3$ به چهار قسمت در شکل زیر نشان داده شده‌اند. روش اول ۴+۲+۱=۷ ثانیه و روش دوم ۴+۲+۴=۱۰ ثانیه طول می‌کشد.

می‌دانیم به ازای هر $k$، روبات رولت‌بر در کمترین زمان ممکن رولت را به $k$ قسمت تقسیم می‌کند. اگر $f(n,k)$ مدت زمانی باشد که رولت‌بر، رولتی با طول $2^n$ را به $k$ قسمت تقسیم می‌کند، به سوالات زیر پاسخ دهید.

$1$- الف ($11$ نمره) : باقی‌مانده‌ی $f(20,2^{20})$ بر $\Delta$ چند است؟

$1$- ب ($14$ نمره) : باقی‌مانده‌ی $f(60,12345678987654321)$ بر $\Delta$ چند است؟


ابزار صفحه