المپدیا

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

ابزار کاربر

ابزار سایت


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

اردوی المپیکی

بعد از اظهار نظرهای آقا داوود درباره‌ی کسل‌کننده بودن برنامه‌ی المپیک، او قصد تدارک دو اردو برای شاگردانش برای آشنایی بیشتر آن‌ها با ورزش‌های مختلف را دارد. می‌دانیم المپیک شامل $N$ روز است به طوریکه در روز $i$-ام، ورزش شماره‌ی $A_i$ برگزار می‌شود. یک اردو به معنای تماشای بازی‌های المپیک در چند روز متوالی است. حال آقا داوود قصد دارد طوری این اردوها را برنامه‌ریزی کند به طوریکه شاگردان او در مجموع این دو اردو حداقل به تماشای $K$ ورزش مختلف رفته باشند و در عین حال به این دلیل که طولانی شدن یک اردو باعث کسل‌کننده شدن آن می‌شود، می‌خواهد بیشینه زمان اردوهای تدارک دیده شده کمینه شود. در واقع آقا داوود باید اعداد طبیعی $1 \leq L_1 \leq R_1 \leq L_2 \leq R_2 \leq N$ را طوری انتخاب کند به طوریکه اگر اردوی اول شامل روزهای $L_1$ تا $R_1$ و اردوی دوم شامل روزهای $L_2$ تا $R_2$ باشد، این روزها شامل حداقل $K$ ورزش متمایز المپیک باشند و مقدار $D = \max(R_1-L_1+1, R_2-L_2+1)$ کمینه شود. حال شما کمترین مقدار $D$ را چاپ کنید.

ورودی

  • سطر اول ورودی شامل سه عدد طبیعی، $1 \leq N \leq 2000$، تعداد روزهای برگزاری المپیک، و $ 1 \leq M \leq N$، تعداد بازی‌های این المپیک، و $1 \leq K \leq M$، حداقل تعداد ورزش‌هایی متمایزی که دو اردو باید شامل شوند، است.
  • سطر دوم شامل $N$ عدد طبیعی $1 \leq A_1, \cdots, A_N \leq M$ به طوری که $A_i$ ورزش انجام شده در روز $i$-ام است.
  • تضمین می‌شود به ازای هر $1 \leq i \leq M$ عدد $j$ی وجود دارد که $A_j= i$ باشد.
  • در ۳۰ درصد از ورودی‌ها، $1 \leq N \leq 500$، است.

خروجی

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

محدودیت‌ها

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

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

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

توضیحات ورودی

  • در ورودی اول اگر اردوی اول شامل روزهای اول و دوم و اردوی دوم شامل روزهای سوم و چهارم باشد، هر چهار روز در مجموع این دو اردو، شامل یک بازی متمایز از دیگر روزهاست.
  • در ورودی دوم اگر اردوی اول شامل روزهای اول و دوم و اردوی دوم شامل روزهای چهارم تا ششم باشد، در اردوی اول شاگردان آقا داوود با ورزش‌های 1 و 2 و در اردوی دوم با ورزش‌های 3و 4 آشنا می‌شوند.

ابزار صفحه