المپدیا

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

ابزار کاربر

ابزار سایت


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

Perm

قلی و گلی دارن باهم بازی می‌کنن. گلی ابتدا $n$ تا خانه‌ی خالی پست سر هم در نظر می‌گیرد و $n-m$‌تا این خانه‌ها را با اعداد ۱ تا $n$ پر می‌کند به طوری که هیچ عددی دو بار ظاهر نشود. اکنون نوبت قلی است. او وظیفه دارد که $m$‌خانه‌ی خالی را با اعداد ۱ تا $n$ پر می‌کند به طوری که هیچ عددی دو بار ظاهر نشود. اکنون نوبت قلی است. او وظیفه دارد که $m$‌خانه‌ی خالی را با اعداد ۱ تا $n$‌ طوری پر کند که در کل یک جای‌گشت از اعداد ۱ تا $n$ به‌دست آید. حال نوبت گلی خواهد شد که باید هر بار عددی که در آخر جای‌گشت قرار دارد، مثلا $k$ را در نظر بگیرد و $k$ عدد آخر جایگشت را به ترتیب عکس قرار دهد. این عمل را تا وقتی انجام می‌دهد که آخرین عدد ۱ شود.

مثلا فرض کنید که $n=5$ و $m=3$ باشد و در ابتدا گلی این ترتیب را تولید کند: $00302$ منظور از صفر خانه‌ی خالی است. سپس قلی این ترتیب را به جای‌گشت $41352$ تبدیل می‌کند. آن‌گاه گلی مجبور است که پنج عمل $54123،54132،52314،41325$ و $54321$ را انجام دهد تا سرانجام بازی تمام شود.

دیروز گلی و قلی دعوا کرده‌اند. به همین دلیل قلی دوست دارد که $m$‌تا عدد را به گونه‌ای به دنباله‌ای که گلی به او داده اضافه کند که گلی بیش‌ترین تعداد عملیات را روی جای‌گشت انجام دهد. چون قلی کار با کامپیوتر را بلد نیست، از شما خواسته است.

برنامه‌ای بنویسید که:

  • تعداد اعداد جای‌گشت و دنباله‌ای که گلی ساخته را از ورودی بخواند.
  • برای دنباله‌ای ورودی جای‌گشتی از اعداد ۱ تا $n$ را بیابد که بیش‌ترین تعداد عملیات را لازم دارد.
  • این جایگشت را در خروجی بنویسید.

ورودی

سطر نخست ورودی شامل عدد صحیح $n$ است $(1\leq n \leq 21)$. سطر بعدی حاوی $n$ عدد است که با یک فاصله از هم جدا شده‌اند؛ اعداد صفر نشان‌دهنده‌ی خانه‌های خالی دنباله است. برنامه‌ی شما می‌تواند به جای این خانه‌ها هر عددی در بازه‌ی ۱ تا $n$ را قرار دهد، به طوری که دنباله‌ی حاصل یک جای‌گشت شود؛ ولی حق ندارد سایر اعداد جای‌گشت را عوض کند. در ضمن تعداد خانه‌های خالی حداکثر ۱۰ تاست$(1\leq m \leq 10)$.

خروجی

در سطر اول خروجی تعداد عملیات لازم برای جای‌گشتی که برنامه‌ی شما ساخته را بنویسید. در سطر دوم جای‌گشتی که برنامه‌ی شما ساخته را بنویسید: بین هر دو عدد جای‌گشت تعدادی فاصله قرار دهید. اگر چند جای‌گشت وجود دارد که تعداد عملیات‌هایشان بیشینه است، هر کدام را که دوست دارید بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۳۲ مگابایت

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

ورودی نمونه خروجی نمونه
5
0 0 3 0 2
5
4 1 3 5 2

ابزار صفحه