Problem
هنگام انجام یک بازی جدید (برخی ترکیبی از بولینگ و بیلیارد)، از N توپ استفاده می شود که از 1 تا N شماره گذاری شده اند. در ابتدای بازی، این توپ ها باید در یک خط به ترتیب عددی قرار گیرند. در طول بازی، ممکن است ترتیب آنها تغییر کند.
برای چیدمان توپ ها قبل از شروع بازی بعدی از دستگاه زیر استفاده می شود. این دستگاه از یک سر تشکیل شده است که با حرکت روی توپ ها می تواند "مک" کند. و " تف کردن " بالن ها برای درک بهتر این دستگاه، جاروبرقی را تصور کنید که می تواند توپ ها را بمکد، به مکان مناسب حرکت کند و در آنجا با دمیدن در جهت مخالف، توپ ها را «تفک کند».
هنگامی که بادکنکی به داخل مکیده می شود، تمام بادکنک هایی که در سمت راست بادکنک مکیده شده بودند به سمت چپ منتقل می شوند. " تف کردن " توپ می تواند بین هر دو توپ باشد (و همچنین قبل از توپ اول یا بعد از توپ آخر)، سپس توپ تف بین این توپ ها قرار می گیرد و تمام توپ هایی که در سمت راست توپ وارد شده هستند به سمت راست منتقل می شوند. .
بیش از یک توپ را می توان همزمان به داخل دستگاه مکید و در هنگام تف کردن توپ به بیرون، ابتدا آخرین توپ مکیده شده و سپس ماقبل آخر و غیره تف داده می شود. (یعنی دستگاه بر اساس اصل یک پشته کار می کند). توپ ها یکی یکی به بیرون تف می شوند، یعنی. شما می توانید فقط یک توپ را بیرون بیاندازید و بقیه را داخل دستگاه بگذارید (در این مورد، می توانید به بیرون ریختن توپ ها در همان مکان یا مکان دیگر ادامه دهید یا توپ های جدید را بمکید).
پر انرژی ترین عملیات توصیف شده، عملیات مکیدن توپ است، بنابراین می خواهیم تعداد چنین عملیاتی را به حداقل برسانیم.
برنامه ای بنویسید که با توجه به چینش اولیه توپ ها، حداقل تعداد مکش مورد نیاز برای چیدمان توپ ها به ترتیب عددی را تعیین کند.
ورودی
در فایل ورودی، ابتدا عدد N داده می شود — تعداد توپ (1≤N≤1000). سپس N عدد وجود دارد که اعداد توپ ها را به ترتیب از چپ به راست در مکان فعلی آنها نشان می دهد (هر عدد &mdash؛ از 1 تا N، و هر یک از اعداد دقیقاً یک بار در دنباله رخ می دهد).
خروجی
خروجی یک عدد — حداقل تعداد عملیات مکیدن توپ که برای مرتب کردن توپ ها به ترتیب تعداد آنها لازم است.
نظرات در مورد آزمایشات نمونه
1. می توانید مثلاً بادکنک شماره 2 را بمکید و بین بالون 1 و 3 بیرون بیاورید.
2.>می توانید کاری شبیه به این انجام دهید. ابتدا
بالون شماره 1 را بمکید، سپس – توپ شماره 2. سپس به ابتدا حرکت می کنیم و قبل از توپ 4 توپ را تف می کنیم (این توپ شماره 2 خواهد بود). سپس بادکنک شماره 3 را بمکید و آن را بین بادکنک های 2 و 4 تف کنید. سپس به ابتدا بروید و بادکنک شماره 1 را در آنجا تف کنید. البته این تنها ترتیب ممکن بادکنک ها در این مثال نیست.
<بدن>
| ورودی |
خروجی |
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
المپیاد تیمی، المپیاد تیمی مسکو، کلاس های 9-11، 2007، لیگ A، مشکل F