المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

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

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

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10427$ محاسبه شده‌اند.

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

پاسخ

9562

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

پاسخ

6725


ابزار صفحه