المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۶

ماشین بر زن

سارا و دارا یک دسته‌ی $N$ کارتی با شماره‌های ۱ تا $N$ (هیچ دو کارتی شماره‌ی یکسان ندارند.) و یک ماشین بر زن دارند. فرض می‌کنیم $N$ عددی فرد است. ماشین بر زن به صورت در هم ریخته را می‌گیرد و عملیات دوبله را به این صورت انجام می‌دهد:

برای هر مکان $(1\leq i \leq N)i$ اگر در مکان $i$ عدد $j$ قرار دارد و در مکان $j$ عدد $k$، بعد از تمام شدن عملیات دوبله در مکان $i$ عدد $k$ قرار خواهد داشت.

سارا دارا این بازی را انجام می‌دهند. ابتدا سارا اعداد ۱ تا $N$ را به یک ترتیب تصادفی می‌نویسد: $a_1$، $a_2$، …،‌$a_N$ سپس کارت‌ها را طوری جابه‌جا می‌کند که کارت مکان $a_i$، عدد $a_{i+1}$ را داشته باشد برای هر $1\leq i \leq N-1$ و کارت مکان $a_N$ عدد $a_1$ را. به این صورت کارت‌ها به ترتیب $x_1$، $x_2$، …،‌$x_N$ در می‌آیند. حالا سارا به ترتیب $S$ بار عملیات دوبله را با استفاده از ماشین بر زن انجام می‌دهد و ترتیب نهایی $p_1$، $p_2$، …،‌$p_N$ را به همراه عدد $S$ به دارا می‌دهد. دارا باید ترتیب اولیه‌ی کارت‌ها قبل از داده شدن به ماشین بر زن را حدس بزند. ($x_1$، $x_2$، …،‌$x_N$)

ورودی

در اولین سطر فایل ورودی دو عدد آمده است. ابتدا عدد فرد $(1\leq N \leq 1000) N$. تعداد کارت‌ها و سپس $(1\leq S \leq 1000)S$. تعداد عملیات دوبله و در $N$ سطر بعد در هر سطر یک عدد که مشخص کننده‌ی $p_i$ هاست. در واقع سطر $i+1$ ام ورودی حاوی عدد $p_i$ است.

خروجی

فایل خروجی دارای $N$ سطر است که در سطر $i$ ام باید عدد $x_i$ نوشته شود.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
5 2
4
1
5
3
2
2
5
4
1
3
7 4
6
3
1
2
4
7
5
4
7
5
6
1
2
3

ابزار صفحه