المپدیا

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

ابزار کاربر

ابزار سایت


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

مداد رنگی‌های بچه‌ی آقا داوود

آقا داوود می‌خواهد برای بچه‌اش چند جعبه‌ی مداد رنگی بخرد. در مغازه‌ی مداد رنگی فروشی $N$ مداد رنگی با $M$ رنگ مختلف در یک ردیف چیده شده‌اند. هر جعبه‌ی مداد رنگی باید از هرکدام از $M$ رنگ دقیقا یک مداد رنگی داشته باشد. یک دنباله از مداد رنگی‌ها خوب است اگر بتوان مداد‌هایش را به تعدادی جعبه‌ی مداد رنگی افراز کرد. به آقا داوود کمک کنید تعداد زیر دنباله‌های متوالی خوب دنباله‌ی مداد‌های داده شده را بشمارد. برای فهم بیشتر سوال به ورودی‌‌های نمونه توجه کنید.

ورودی

  • سطر اول ورودی شامل دو عدد طبیعی، $1 \leq N \leq 2*10^5$، تعداد مداد رنگی‌ها، و$1 \leq M \leq N$، تعداد رنگ‌های مداد رنگی‌ها، است.
  • سطر دوم شامل $N$ عدد طبیعی $1 \leq A_1, \cdots, A_N \leq M$ به طوری که $A_i$ رنگ $i$-امین مداد رنگی می‌باشد.
  • تضمین میشود به ازای هر $1 \leq i \leq M$ عدد $j$ی وجود دارد که $A_j= i$ باشد.
  • در ۳۰ درصد از ورودیها، $1 \leq M \leq 4$، است.
  • در ۶۰ درصد از ورودیها، $1 \leq M \leq 80$، است.

خروجی

در تنها سطر خروجی پاسخ مسئله را چاپ کنید.

محدودیت‌ها

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

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

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

ابزار صفحه