المپدیا

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

ابزار کاربر

ابزار سایت


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

جایگشت‌های علامت‌دار

یک جایگشت، یک ترتیب از اعداد ۲،۱،… و $n$ است. برای مثال ($3,1,4,2,5$) جایگشتی از اعداد ۱ تا ۵ است. یک جایگشت علامت‌دار از روی یک جایگشت عادی به این شکل به دست می‌آید که صفر یا چند عدد آن جایگشت را منفی می‌کنیم. برای مثال ($-3,1,-4,-2,5$) جایگشتی علامت‌دار است.

اگر $A=(a_1,a_2,…,a_n)$ یک جایگشت علامت‌دار باشد، دوران $(i,j)$ که در آن $1\leq i \leq j \leq n$ آن را به جایگشت علامت‌دار زیر تبدیل می‌کند:

$$(a_1,a_2,…,a_{i-1},-a_j,-a_{j-1},…,-a_{i+1},-a_{i}+a_{j+1},…,a_n)$$

برای مثال با انجام متوالی دوران‌های $(1,2)$، $(2,3)$ و $(1,2)$ روی جایگشت علامت‌دار $(1,2,3)$، به ترتیب جایگشت‌های علامت‌دار زیر به‌دست می‌آیند:

$$(1,2,3) \rightarrow (-2,-1,3) \rightarrow (-2,-3,1) \rightarrow (3,2,1)$$

ثابت کنید دست کم $n-1$ دوران برای تبدیل $(a_1,a_2,…,a_n)$ به $(a_n,a_{n-1},…,a_1)$‌ لازم است.


ابزار صفحه