المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۴۱

Perm

پسرشجاع با پدر پسرشجاع مشغول بازی است. این دو نفر به این شکل بازی می کنند:

‎ دور یک میزگرد اعداد ‎$1$ تا ‎$n$‎ به ترتیب نوشته شده است. هم‌چنین یک دیسک در وسط میز قرار دارد. پسرشجاع در مقابل هر عددی که روی میز نوشته شده یک عدد بین ‎$1$ تا ‎$n$‎ روی دیسک می‌نویسد و هر عدد را دقیقا یک بار می‌نویسد.

‎ بازی از این قرار است که پدر پسرشجاع می‌تواند این دیسک را مقداری که دوست دارد بچرخاند. سپس این دیسک را ثابت کند. در این لحظه هر عدد روی دیسک در مقابل یک عدد میز قرار گرفته است. به عددی روی دیسک که در آخر کار در مقابل عدد ‎$i$‎ میز قرار دارد ‎$b_i$‎ می‌گوییم. در این‌صورت، پدر پس شجاع باید به اندازه مجموع ‎$\mid b_i-i \mid$‎ برای ‎$i$‎ از ‎$1$‎ تا ‎$n$‎ شکلات به پسرشجاع بدهد. به پدر پسرشجاع کمک کنید تا کم‌ترین تعداد شکلات را به پسر شجاع بدهد تا مریض نشود.

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

  • اعدادی را که پسرشجاع روی دیسک نوشته است از ورودی بخواند؛
  • در خروجی کم‌ترین تعداد شکلاتی را بنویسید که پدر پسرشجاع باید به پسرش بدهد.

ورودی

  • در سطر اول ورودی، ‎$n$‎ (تعداد اعداد دور میز) آمده است.‎
  • در سطر دوم، ‎$n$‎ عدد آمده است. عدد ‎$i$‎ام عددی است که در ابتدای کار پسرشجاع روی دیسک و در مقابل عدد ‎$i$‎ام میز نوشته است.‎
  • ‎$1 \leq n \leq 1000000$‎ (در ‎$30$‎ درصد تست‌ها ‎$1 \leq n \leq 5000$‎ می‌باشد)‎

خروجی

در تنها سطر خروجی، کم‌ترین تعداد شکلاتی را بنویسید که پدر پسر شجاع باید به پسر شجاع بدهد.

محدودیت‌ها

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

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

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

ابزار صفحه