المپدیا

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

ابزار کاربر

ابزار سایت


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

ببعی و دزدی از مزرعه‌ی کاهو!

ببعی چندی پیش به خاطر دزدی از مزرعه ی کاهو، دستگیر شد. او تنها یک راه برای آزادی دارد و باید بتواند چالش بزرگ چارپایان را حل کند. چالش بزرگ چارپایان یک معمای مرموز قدیمی است.

قبل از گفتن معما، لازم است تعاریفی را بدانید. فرض کنید یک جایگشت داریم. منظور از $a_i$، خانه ی $i$-ام جایگشت است. همچنین فرض کنید جایگشت $a_۱, a_۲,...a_m$ را داریم و می خواهیم روی تعدادی از خانه های آن مانند $a_j۱, a_j۲ ,..., a_jk $ عمل دوران را انجام دهیم. در این عمل دوران، عدد خانه ی اول یا $a_j۱$ به خانه‌ي دوم یا $a_j۲$ می رود، عدد خانه ی دوم یا $a_j۲$ به خانه ی سوم یا $a_j۳$ می رود و … و عدد خانه ی $k$-ام یا $a_jk$ به خانه‌ي اول یا $a_j۱$ می رود. برای مثال فرض کنید جایگشت ۶ ,۵ ,۴ ,۳ ,۲ ,۱ را داریم و می خواهیم روی خانه های دوم، سوم و پنجم جایگشت، عمل دوران را انجام دهیم. پس از عمل دوران، جایگشت ما به ۶ ,۳ ,۴ ,۲ ,۵ ,۱ تبدیل خواهد شد.

حال به معما بر می گردیم. جایگشت مرتب شده ی اعداد $۱, ۲, ..., n!$ را در نظر بگیرید. سپس برای هر $i$ که $1 \le i \le n$ عدد $i!$ را در نظر بگیرید و کار زیر را انجام دهید:

خانه های جایگشت را به دسته های زیر افراز کنید:

  • دسته ی نخست: $a_۱, a_{i!+1}, a_{2\times i! +1}, ...a_{n!-i!+1}$
  • دسته ی دوم: $a_۲, a_{i!+۲}, a_{2\times i! +۲}, ...a_{n!-i!+۲}$
  • دسته ی آخر: $a_{i!}, a_{2*i!}, a_{3* i!}, ..., a_{n!}$

حال روی خانه های هر دسته، عمل دوران را انجام دهید. به عنوان مثال فرض کنید ۳=$n$ باشد. در ابتدا ۶, ۵, ۴, ۳, ۲, ۱ را داریم. پس از مرحله ی نخست، جایگشت به ۵ ,۴ ,۳ ,۲ ,۱ ,۶ تبدیل خواهد شد. پس از مرحله ی دوم، به جایگشت ۳ ,۲ ,۱ ,۶ ,۵ ,۴ خواهیم رسید و در مرحله ی آخر، جایگشت ۳ ,۲ ,۱ ,۶ ,۵ ,۴ را خواهیم داشت.

جایگشتی که در انتها به دست می آید را در نظر بگیرید. این جایگشت را به صورت عددی $n!$ رقمی در مبنای ۳ +$n!$ در نظر بگیرید. برای نجات ببعی، شما باید این عدد را در پیمانه ی $\Delta$ به دست بیاورید. برای مثال عدد متناظر جایگشتی که در مثال قبل به دست آوردیم، ۴۵۶۱۲۳ در مبنای ۹ می باشد.

۶- الف (۱۱ نمره) : معما را برای n= ۴ حل کنید.

۶- ب (۱۱ نمره) : معما را برای n= ۱۰ حل کنید.

۶- ج (۱۱ نمره) : معما را برای n= ۱۷ حل کنید.


ابزار صفحه