به دلیل اینکه این سوالات برای المپیاد کامپیوتر طراحی شده و محدودیت تست‌ها، امکان ارسال فقط با زبان سی‌پلاس‌پلاس ممکن است.

لیته و نیوفیته


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

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

در این مسئله دنباله‌ای از اعداد صحیح به طول nn به شما داده می‌شود و شما باید با حداقل تعداد عملیات ممکن همه‌ی اعداد دنباله را تبدیل به صفر کنید. اعداد این دنباله از چپ به راست a1a_1 تا ana_n نامیده می‌شوند.

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

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

ورودی🔗

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

در خط بعدی، nn عدد حسابی آمده است که به ترتیب a1a_1 تا ana_n را نشان می‌دهند.

1n105 1 \le n \le 10^5 0ai105(1in) 0 \le a_i \le 10^5 (1 \le i \le n)

خروجی🔗

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

زیرمسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۳۰ 1n600 1 \le n \le 600
۲ ۷۰ بدون محدودیت اضافی

مثال🔗

ورودی نمونه ۱🔗

10
1 1 1 1 2 2 2 3 2 1
Plain text

خروجی نمونه ۱🔗

5
Plain text

ورودی نمونه ۲🔗

8
2 2 2 0 1 1 2 2
Plain text

خروجی نمونه ۲🔗

-1
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.