المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۵:تئوری نهایی سوم:سوال ۲

خیمه‌ی پارسا روی بچه‌ها

فرض کنید یک جایگشت مانند $\pi = <\pi_1, \pi_2, \ldots, \pi_n>$ از اعداد $1, 2, \ldots, n$ داریم و می‌خواهیم این جایگشت را مرتب کنیم. به اعداد $1, 2, 4, 8, 16, \ldots$ اعداد یاسی می‌گوییم. در هر مرحله می‌توان یک زیرجایگشت از اعداد متوالی جایگشت انتخاب کرد؛ طوری که تعداد اعداد این زیرجایگشت، یک عدد یاسی باشد؛ سپس اعداد این زیرجایگشت وارونه می‌شوند. برای مثال جایگشت $1, 6, 5, 2, 3, 4$ را می‌توان در ۳ مرحله به شکل زیر مرتب کرد: $$ 1, \underline{6, 5}, 2, 3, 4 \rightarrow 1, 5, \underline{6, 2, 3, 4} \rightarrow 1, \underline{5, 4, 3, 2}, 6 \rightarrow 1, 2, 3, 4, 5, 6 $$ کمینه‌ی تعداد مراحل لازم برای مرتب کردن جایگشت $\pi$ را $f(\pi)$ می‌گوییم. فرض کنید بیش‌ترین مقدار $f(\pi)$ به ازای تمام جایگشت‌های ممکن از اعداد $1, 2, \ldots, n$ برابر $g(n)$ باشد. $\theta \big(g(n)\big)$ را بیابید.


ابزار صفحه