Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

ورودی

  • سطر اول ورودی شامل دو عدد طبیعی، 1N2105، تعداد مداد رنگی‌ها، و1MN، تعداد رنگ‌های مداد رنگی‌ها، است.
  • سطر دوم شامل N عدد طبیعی 1A1,,ANM به طوری که Ai رنگ i-امین مداد رنگی می‌باشد.
  • تضمین میشود به ازای هر 1iM عدد jی وجود دارد که Aj=i باشد.
  • در ۳۰ درصد از ورودیها، 1M4، است.
  • در ۶۰ درصد از ورودیها، 1M80، است.

خروجی

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

محدودیت‌ها

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

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

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

ابزار صفحه