قورباغه


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

قورباغه‌ای روی محور اعداد زندگی می‌کند. NN جزیره روی محور اعداد وجود دارد و iiامین جزیره در نقطه‌ی aia_i قرار دارد، (1iN1 \le i \le N). قورباغه در ابتدا در نقطه‌ی a1a_1 است. او با هر پرش می‌تواند به جزیره‌ای به فاصله‌ی حداکثر LL برود. او نمی‌تواند به نقطه‌ای برود که جزیره‌ای وجود ندارد.

یک جزیره قابل دسترسی است اگر قورباغه بتواند با تعدادی پرش به آن برسد. تعداد جزیره‌های قابل دسترسی چند تاست؟

ورودی🔗

در خط اول ورودی دو عدد طبیعی NN و LL با فاصله از هم آمده است. در خط دوم ورودی اعداد a1,a2,,aNa_1, a_2, \dots, a_N با فاصله از هم آمده است که بیانگر موقعیت جزیره‌هاست.

خروجی🔗

در تنها خط ورودی تعداد جزیره‌های قابل دسترسی را چاپ کنید.

مثال🔗

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

5 1
4 7 1 3 5
Plain text

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

3
Plain text

قورباغه در نقطه‌ی ۴ قرار دارد و حداکثر طول پرشش ۱ است. در نتیجه فقط به جزیره‌های واقع در ۳، ۴ و ۵ می‌تواند برود.

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

5 2
100 101 103 105 107
Plain text

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

5
Plain text

او به تمام ۵ جزیره می‌تواند برود.

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

8 4
17 10 22 14 6 1 2 3
Plain text

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

7
Plain text

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

1 1000
0
Plain text

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

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