• شانزدهمین مسابقه‌ی برنامه نویسی اینترنتی ایران
  • مقدماتی منطقه‌ی غرب آسیا، سایت تهران
  • دانشگاه صنعتی شریف، ٨ آذر ۱۳۹۷

لینک‌های مفید برای شرکت در مسابقه:

مهمان نوازی


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

باران شدیدی در جنگل شروع به باریدن گرفته و حیوانات جنگل به خانه ی خاله مرجان هجوم می‌آورند تا شب را در آنجا سپری کنند. خاله مرجان هم مثل همیشه در خانه اش را به روی حیوانات جنگل باز می‌گذارد و nn حیوان از سراسر جنگل وارد خانه ی خاله مرجان می‌شوند. خانه‌ی خاله مرجان به شکل یک تالار به طول 10610^6 و عرض 11 متر است که در ابتدای این تالار در ورودی قرار دارد. هر کدام از حیوانات بعد از وارد شدن به خانه‌ی خاله مرجان در یک فاصله‌ای از در می‌خوابند. قد تمام حیوانات یک متر و عرض آن‌ها صفر است! آن‌ها به گونه‌ای می‌خوابند که قدشان در موازات عرض تالار باشد. پس با توجه به لاغری تمام حیوانات، می‌توان محل خوابیدن هر کدام از آن‌ها را با یک عدد طبیعی بین 11 تا 10610^6 نشان داد که فاصله‌ی آن‌ها از در است.

خاله مرجان که نگران سرما خوردن مهمان های خود است، تصمیم می‌گیرد با کم ترین تعداد پتو، تمام مهمان‌ها را پوشش دهد. پتوهای خاله مرجان مستطیل شکل به طول dd و عرض یک متر هستند. حال می‌خواهیم به خاله مرجان بگوییم چند پتو نیاز دارد. برای مثال اگر طول پتوها 33 باشد و یکی از حیوانات در فاصله‌ی 22 متری در و دیگری در فاصله‌ی 55 متری در باشد، می‌توان با یک پتو که بازه‌ی [2,5][2 ,5] را پوشش می‌دهد، هر دو حیوان را پوشش داد.

ورودی🔗

در خط اول ورودی دو عدد طبیعی nn و dd آمده است که به ترتیب تعداد حیوانات و طول پتوهای خاله مرجان را نشان می‌دهد. 1n5000,1d1061 \leq n \leq 5000, \quad \quad 1 \leq d \leq 10^6

در خط بعدی، nn عدد طبیعی آمده است که iiامین آن ها محل خوابیدن iiامین حیوان را نشان می‌دهد.

محل خوابیدن هر حیوان حداکثر 10610^6 است.

خروجی🔗

در خروجی، کم‌ترین تعداد پتوی لازم را چاپ کنید.

مثال‌ها🔗

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

4 2
4 3 2 1
Plain text

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

2
Plain text

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

6 3
7 4 13 1 11 15
Plain text

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

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