قلی و گلی دارن باهم بازی میکنن. گلی ابتدا n تا خانهی خالی پست سر هم در نظر میگیرد و n−mتا این خانهها را با اعداد ۱ تا n پر میکند به طوری که هیچ عددی دو بار ظاهر نشود. اکنون نوبت قلی است. او وظیفه دارد که mخانهی خالی را با اعداد ۱ تا n پر میکند به طوری که هیچ عددی دو بار ظاهر نشود. اکنون نوبت قلی است. او وظیفه دارد که mخانهی خالی را با اعداد ۱ تا n طوری پر کند که در کل یک جایگشت از اعداد ۱ تا n بهدست آید. حال نوبت گلی خواهد شد که باید هر بار عددی که در آخر جایگشت قرار دارد، مثلا k را در نظر بگیرد و k عدد آخر جایگشت را به ترتیب عکس قرار دهد. این عمل را تا وقتی انجام میدهد که آخرین عدد ۱ شود.
مثلا فرض کنید که n=5 و m=3 باشد و در ابتدا گلی این ترتیب را تولید کند: 00302 منظور از صفر خانهی خالی است. سپس قلی این ترتیب را به جایگشت 41352 تبدیل میکند. آنگاه گلی مجبور است که پنج عمل 54123،54132،52314،41325 و 54321 را انجام دهد تا سرانجام بازی تمام شود.
دیروز گلی و قلی دعوا کردهاند. به همین دلیل قلی دوست دارد که mتا عدد را به گونهای به دنبالهای که گلی به او داده اضافه کند که گلی بیشترین تعداد عملیات را روی جایگشت انجام دهد. چون قلی کار با کامپیوتر را بلد نیست، از شما خواسته است.
برنامهای بنویسید که:
سطر نخست ورودی شامل عدد صحیح n است (1≤n≤21). سطر بعدی حاوی n عدد است که با یک فاصله از هم جدا شدهاند؛ اعداد صفر نشاندهندهی خانههای خالی دنباله است. برنامهی شما میتواند به جای این خانهها هر عددی در بازهی ۱ تا n را قرار دهد، به طوری که دنبالهی حاصل یک جایگشت شود؛ ولی حق ندارد سایر اعداد جایگشت را عوض کند. در ضمن تعداد خانههای خالی حداکثر ۱۰ تاست(1≤m≤10).
در سطر اول خروجی تعداد عملیات لازم برای جایگشتی که برنامهی شما ساخته را بنویسید. در سطر دوم جایگشتی که برنامهی شما ساخته را بنویسید: بین هر دو عدد جایگشت تعدادی فاصله قرار دهید. اگر چند جایگشت وجود دارد که تعداد عملیاتهایشان بیشینه است، هر کدام را که دوست دارید بنویسید.