Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

آقای بین (Mr.Bean)

مبین و مبینا می‌خواهند با بازی فکری جدیدی که پدربزرگشان، مستربین برایشان خریده است بازی کنند. مبین دفترچه راهنمای بازی را می‌خواند و بازی را برای مبینا شرح می‌دهد:

«این بازی فقط از تعدادی آجر تشکیل شده است. در ابتدا آجرها را در n ردیف بچینید و در ردیف iام ai آجر را روی هم قرار دهید. شما در هر دقیقه می‌توانید تعدادی ردیف متوالی که تعداد آجرهای آن‌ها به یک اندازه است را انتخاب کنید و به همه‌ی آن‌ها به تعداد مساوی آجر اضافه کنید یا از آجر‌هایش بکاهید. به عبارتی دیگر می‌توانید یک بازه lr و عدد صحیح x انتخاب کنید به طوری که ai=al به ازای تمامی lir برقرار باشد، سپس تمامی اعضای این بازه را با x جمع کنید.

به طور مثال اگر دنباله a=4,2,2,2,3,2 باشد، می‌توانید با انتخاب بازه l=2 و r=3 و عدد صحیح x=1 دنباله را به a=4,1,1,2,3,2 تبدیل کنید.

هدف بازی این است که در کمترین زمان ممکن کاری کنید که همه‌ی ردیف‌ها به یک اندازه آجر داشته باشند.»

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

ورودی

در خط اول n تعداد ردیف‌ها می‌آیند.

در خط دوم n عدد a1,a2,...,an به ترتیب می‌آیند.

خروجی

کمترین زمان ممکن برای برابر کردن تعداد آجرهای تمامی ردیف‌ها را چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۹ نمره): عدد طبیعی x وجود دارد که aiai+1 به ازای تمامی i<x و aiai+1 به ازای تمامی ix برقرار است.
  • زیرمسئله دوم (۲۰ نمره): n100
  • زیرمسئله سوم (۳۲ نمره): n300
  • زیرمسئله چهارم (۳۹ نمره): بدون محدودیت اضافی

محدودیت‌ها

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

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

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

ابزار صفحه