Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

ماشین بر زن

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

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

سارا دارا این بازی را انجام می‌دهند. ابتدا سارا اعداد ۱ تا N را به یک ترتیب تصادفی می‌نویسد: a1، a2، …،‌aN سپس کارت‌ها را طوری جابه‌جا می‌کند که کارت مکان ai، عدد ai+1 را داشته باشد برای هر 1iN1 و کارت مکان aN عدد a1 را. به این صورت کارت‌ها به ترتیب x1، x2، …،‌xN در می‌آیند. حالا سارا به ترتیب S بار عملیات دوبله را با استفاده از ماشین بر زن انجام می‌دهد و ترتیب نهایی p1، p2، …،‌pN را به همراه عدد S به دارا می‌دهد. دارا باید ترتیب اولیه‌ی کارت‌ها قبل از داده شدن به ماشین بر زن را حدس بزند. (x1، x2، …،‌xN)

ورودی

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

خروجی

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

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

ورودي نمونه خروجي نمونه
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

ابزار صفحه