المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۹:تئوری:سوال ۷

شبه جایگشت

یک شبه جایگشت $k$ بعدی، یک دنباله از اعداد ۱ تا $n$ است که هر عدد $k$‌بار تکرار شده است. توجه کنید که یک شبه جایگشت ۱بعدی همان جایگشت است. برای هر دو عدد $i$ و $j$، $\pi_i(j)$ مکان $i$ امین عدد $j$ در شبه جایگشت است. (مثلا در شبه جایگشت ۱۲۳۳۱۲، $\pi_2(2)=6$ و $\pi_1(2)=2$). رتبه‌ی $i$ ام یک شبه جایگشت که با $r(i)$‌ نشان می‌دهیم، مقدار $\pi_1(i)+2\pi_2(i)+…+k\pi_k(i)$ می‌باشد. مثلا در مثال قبل رتبه‌ی دوم ۱۴ و رتبه‌ی سوم ۱۱ است. عدد یک شبه‌جایگشت یعنی مقدار $r(1)+r(2)+…+r(n)$ نمایش می‌دهیم. یک شبه جایگشت خوب است اگر و تنها اگر عدد آن بیشینه باشد.

  • عدد یک شبه جایگشت خوب چند است؟
  • تعداد شبه جایگشت‌های خوب را به‌دست آوردید.

ابزار صفحه