المپدیا

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

ابزار کاربر

ابزار سایت


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

لیته و نیوفیته($Litteh\&NewFiteh$)

لیته پس از این که در همکاری با فیته به موفقیت نرسید، تصمیم گرفت که از این‌جا به بعد با نیوفیته همکاری کند. نیوفیته از این اتفاق بسیار خرسند است اما برای این که کسی شک نکند ابتدا از لیته خواسته تا یک مسئله‌ی سخت را برایش حل کند، متاسفانه لیته با تمام مهارتی که در حل مسائل الگوریتمی دارد، این بار نیازمند کمک‌های شایان شماست تا در همکاری‌اش با نیوفیته با شکست مواجه نشود.

در این مسئله دنباله‌ای از اعداد صحیح به طول $n$ به شما داده می‌شود و شما باید با حداقل تعداد عملیات ممکن همه‌ی اعداد دنباله را تبدیل به صفر کنید. اعداد این دنباله از چپ به راست $a_1$ تا $a_n$ نامیده می‌شوند.

هر عملیات به این صورت است که ابتدا یک بازه از دنباله مانند $[l, r)$ انتخاب می‌کنید و از همه‌ی اعضای این بازه ۱ واحد کم می‌کنید. ($1 \le l < r \le n + 1$)

  • طول هر بازه که انتخاب می‌کنید باید توانی از ۲ باشد.
  • هر بازه حداکثر ۱ بار می‌تواند انتخاب شود.
  • اگر دو بازه‌ی انتخاب شده مانند $[l_2, r_2)$ و $[l_1, r_1)$ وجود داشته باشند که اشتراکشان تهی نباشد، آنگاه $max(l_1 - l_2, l_2 - l_1)$ باید مضربی از $min(r_1 - l_1, r_2 - l_2)$ باشد.

ورودی

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

در خط بعدی، $n$ عدد حسابی آمده است که به ترتیب $a_1$ تا $a_n$ را نشان می‌دهند.

خروجی

در تنها خط خروجی، حداقل تعداد عملیات برای این که همه‌ی اعداد دنباله به صفر تبدیل شوند را چاپ کنید و در صورتی که این کار با عملیات‌های گفته شده امکان پذیر نیست عدد $-1$ را چاپ کنید.

زیرمسئله‌ها

  • زیرمسئله اول (۳۰ نمره): $1 \le n \le 600$
  • زیرمسئله دوم (۷۰ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n \le 10^5$
  • $0 \le a_i \le 10^5$ ($1 \le i \le n$)

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

ورودی نمونه خروجی نمونه
10
1 1 1 1 2 2 2 3 2 1
5
8
2 2 2 0 1 1 2 2
-1

ابزار صفحه