Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:عملی:سوال ۳

نوار

یک نوار داریم که از یک سمت نامتناهی است و خانه‌های آن را با شماره‌های ۱،۰ و … شماره‌گذاری کرده‌ایم. در n خانه‌ی ابتدای این نوار، اعداد ۱ تا n قرار گرفته‌اند. در یک حرکت می‌توانیم یک عدد را انتخاب کرده و آن را از مکان فعلی‌اش به یک خانه‌ی خالی در سمت راست منتقل کنیم. بالطبع پس از این حرکت خانه‌ی اولی خالی و خانه‌ی دوم پر می‌شود. هدف ما این است که این اعداد را به صورت مرتب شده در n خانه‌ی مجاور نوار داشته باشیم. بنا به دلایل فنی از ما خواسته شده که کمینه‌ی x را پیدا کنیم که بتوان با تعدادی حرکت اعداد را به خانه‌های x تا x+n1 ببریم و عدد موجود در خانه‌ی x،۱ و محتوای خانه‌ی x+n1 نیز n باشد.

شما این مقدار کمینه را برای x حساب کنید.

ورودی

در سطر اول فایل ورودی، n تعداد اعداد آمده و در n سطر بعدی به ترتیب اعداد موجود در خانه‌های ۰ تا n1 می‌آید.(1n105)

خروجی

در تنها سطر خروجی x‌را بنویسید.

محدودیت‌ها

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

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

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

ابزار صفحه