$n$ عدد سوسک اهل حال جشن تولد گرفته بودند و دور یک میز دایره‌ای (با فاصله‌ی مساوی از هم) نشسته بودند.ما هم وقتی متوجه شدیم شروع کردیم به کشتن‌شان.سوسک‌ها چون در مهمانی حسابی خورده بودند حال پاشدن هم نداشتند و از سر جایشان بلند نشدند (تا آخر مسئله هم بلند نخواهند شد).در ابتدا کشتن سوسک‌ها به این روش بود که یک سوسک را به صورت تصادفی انتخاب می‌کردیم و با یک قاشق به او سَم می‌خوراندیم (شاید بپرسید خوب چرا با یک دمپایی نمی‌زدیم توی سرش. خوب اونم می‌شه!).ولی این کار پس از مدتی خسته کننده شد و یک اسپری حشره‌کشِ خریدیم تا با آن کار را ادامه دهیم.با هر بار استفاده از اسپری، ‎$k$‎ سوسک متوالی آلوده می‌شوند و اگر زنده باشند می‌میرند.

خوب، خصوصیت یک المپیاد کامپیوتری (یا بهتر بگوییم یک Computer Scientist‎) چیست؟ این که می‌خواهد با کم‌ترین تعداد استفاده از اسپری، همه‌ی سوسک‌های باقی‌مانده را کشته باشد.راه حل درست و ساده‌ای به ذهنمان نرسید از این رو الگوریتم زیر را ارائه دادیم: ‎

1. ‎‎ از یک سوسک دلخواه در دایره شروع کن و در جهت ساعت‌گرد روی دایره حرکت کن.
2. ‎‎ تا وقتی سوسک زنده‌ای باقی مانده، حلقه‌ی زیر را تکرار کن:
   • روی دایره برو جلو تا یک سوسک زنده ببینی.
   • با اسپری، آن سوسک و ‎$k-1$‎ سوسک بعدش را آلوده کن.
   • صبر کن تا سوسک‌های آلوده شده‌ی زنده بمیرند.

ثابت کنید این الگوریتم حداکثر یک بار بیش‌تر از روش بهینه از اسپری استفاده می‌کند.

• سوال بعد
• سوال قبل