عند لعب لعبة جديدة (بعض هجين من البولينج والبلياردو) ، يتم استخدام كرات N ، مرقمة من 1 إلى N. في بداية اللعبة ، يجب ترتيب هذه الكرات في خط بترتيب رقمي. أثناء اللعبة ، قد يتغير ترتيبهم.
من أجل ترتيب الكرات قبل بدء اللعبة التالية ، يتم استخدام الجهاز التالي. يتكون هذا الجهاز من رأس يمكن أن "يمتص" يتحرك فوق الكرات و "بصق" بالونات. للحصول على فكرة أفضل عن هذا الجهاز ، تخيل مكنسة كهربائية يمكنها امتصاص الكرات ، والانتقال إلى المكان الصحيح ، وهناك ، تنفث في الاتجاه المعاكس ، "بصق" الكرات.
& nbsp؛
عندما يتم امتصاص بالون ، يتم إزاحة جميع البالونات التي كانت على يمين البالون الممص إلى اليسار. "بصق" يمكن أن تكون الكرة بين أي كرتين (وأيضًا قبل الكرة الأولى أو بعد الكرة الأخيرة) ، ثم يتم إدخال كرة البصق بين هذه الكرات ، ويتم إزاحة جميع الكرات الموجودة على يمين الكرة التي تم إدخالها إلى اليمين .
& nbsp؛
يمكن شفط أكثر من كرة واحدة في الجهاز في نفس الوقت ، وعند بصق الكرة ، يتم بصق آخر كرة تم امتصاصها أولاً ، ثم الكرة قبل الأخيرة ، وهكذا. (أي أن الجهاز يعمل على مبدأ المكدس). يتم بصق الكرات واحدة تلو الأخرى ، أي يمكنك بصق كرة واحدة فقط ، وترك الباقي داخل الجهاز (في هذه الحالة ، يمكنك الاستمرار في "بصق" الكرات في نفس المكان أو في مكان آخر ، أو امتصاص الكرات الجديدة).
& nbsp؛
أكثر العمليات الموصوفة استهلاكًا للطاقة هي عملية مص الكرة ، لذلك نريد تقليل عدد هذه العمليات فقط.
& nbsp؛
اكتب برنامجًا ، بالنظر إلى الترتيب الأولي للكرات ، سيحدد الحد الأدنى من عمليات الشفط المطلوبة لترتيب الكرات بالترتيب العددي.
& nbsp؛
إدخال
في ملف الإدخال ، يتم إعطاء الرقم N أولاً & [مدش] ؛ عدد الكرات (1 & Le؛ N & le؛ 1000). ثم هناك أرقام N التي تعطي أرقام الكرات بالترتيب من اليسار إلى اليمين في موقعها الحالي (كل رقم و [مدش] ؛ من 1 إلى N ، وكل رقم يظهر مرة واحدة بالضبط في التسلسل).
& nbsp؛
الإخراج
إخراج رقم واحد و [مدش] ؛ الحد الأدنى من عمليات مص الكرة المطلوبة لترتيب الكرات حسب أرقامها.
& nbsp؛
تعليقات على نماذج الاختبارات
& nbsp؛
1. يمكنك مص ، على سبيل المثال ، بالون رقم 2 وبصقه بين البالون الأول والثالث.
& nbsp؛
2. & gt ؛ يمكنك فعل شيء كهذا. أولاً ،
مص البالون رقم 1 ، ثم & ndash؛ رقم الكرة 2. ثم ننتقل إلى البداية ونبصق الكرة قبل الكرة الرابعة (ستكون هذه الكرة رقم 2). بعد ذلك ، قم بشفط البالون رقم 3 وابصقه بين البالونين 2 و 4. ثم انتقل إلى البداية وابصق البالون رقم 1 هناك. ومع ذلك ، ليس هذا هو الترتيب الوحيد الممكن للبالونات في هذا المثال.
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
|
3
2 1 3
|
1 |
|
4
4 3 2 1
|
3 |
أولمبياد الفريق ، أولمبياد فريق موسكو ، الصفوف 9-11 ، 2007 ، الدوري أ ، المشكلة و