المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۲۵:سوال ۹

Damdaran

اخیرا گونه‌ی جدیدی از گاوها کشف شده است که «گاوهای خجالتی» نامیده شده‌اند. علت این نامگذاری آن است که این گاوها تنها در صورتی غذا می‌خورند که هیچ گاو دیگری نتواند آن‌ها را ببیند. برای پرورش این گاوها، چراگاه مخصوصی با $n$ نقطه‌ی سرسبز تشکیل شده است. $i$ $(0 \le i \le n - 1)$ امین نقطه‌ی سرسبز در $(i, y_i)$ قرار دارد.

دو گاو در صورتی یکدیگر را می‌بینند که هیچ یک از نقاط سرسبز بین آن دو، اکیدا بالاتر از خط واصل آن دو نباشد. برای مثال توجه کنید که در ورودی نمونه‌ی دوم دو گاو که به ترتیب در نقطه‌ی اول و آخر قرار دارند، یکدیگر را می‌بینند. بدیهی است که براساس این تعریف دو گاو در یک نقطه یکدیگر را می‌بینند.

می‌خواهیم بیش‌ترین تعداد گاو را در نقاط سرسبز چراگاه قرار دهیم طوری که هیچ دو گاوی یکدیگر را نبینند. برنامه‌ای بنویسید که بیش‌ترین تعداد گاو را به دست بیاورد.

پیاده‌سازی

در این سوال شما باید تابع زیر را پیاده‌سازی کنید:

  • int countMaximumCows(int n, int *y)

این تابع دقیقا یک‌بار صدا زده می‌شود. تابع را طوری پیاده سازی کنید که بیش‌ترین تعداد گاو را برگرداند.

  • $n$: تعداد نقاط سرسبز چراگاه
  • $y$: یک آرایه به طول $n$. به ازای هر $i$ $(0 \le i \le n - 1)$ نقطه‌ی سرسبز $i$ ام در $(i, y_i)$ قرار دارد.

ارزیاب نمونه

ارزیاب نمونه ورودی را به صورت زیر می‌خواند:

در خط اول عدد $n$ آمده است. در خط دوم $n$ عدد $y_0, y_1, \ldots, y_{n - 1}$ آمده است.

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۷۰ نمره): در همه‌ی تست‌ها ‎$n\leq 200$‎.
  • زیرمسئله‌ی دوم (۳۰ نمره): بدون محدودیت اضافی.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le n \le 2000$
  • $0 \le y_i \le 10^9$

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

ورودی نمونه خروجی نمونه
6
0 10 0 5 6 11
3
3
0 1 2
1

ابزار صفحه