المپدیا

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

ابزار کاربر

ابزار سایت


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

Perm

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

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

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

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

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

ورودی

در سطر اول ورودی، $n$(تعداد اعداد دور میز) آمده است.($1\leq n \leq 10^6$)

در سطر دوم، $n$‌عدد آمده است. عدد $i$ام عددی است که در ابتدای کار پسر شجاع روی دیسک و در مقابل عدد $i$ام میز نوشته است.

خروجی

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

محدودیت‌ها

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

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

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

ابزار صفحه