در بازه‌ی ‎$[0,m]$‎ از محور اعداد حقیقی، ‎$n$‎ نورافکن قرار گرفته اند. محل قرار گرفتن هر نورافکن، عددی صحیح است به این ترتیب که نورافکن اول در مکان ‎$x_1$‎ ، نورافکن دوم در مکان ‎$x_2$‎ و به همین ترتیب نور افکن ‎$n$‎ ام در مکان ‎$x_n$‎ قرار دارد. در ضمن می‌دانیم که ‎$x_1 \leq x_2 \leq‎ ... ‎\leq x_n$‎ .

همه‌ی نور افکن‌ها در ابتدا خاموش‌اند، در صورت روشن کردن نورافکن ‎$i$‎ ام، این نورافکن هر نقطه‌ی دیگری که در فاصله‌ی حداکثر ‎$l_i$‎ از نقطه‌ی ‎$x_i$‎ قرار داشته باشد را روشن می‌کند‎.

الگوریتمی از ‎$O(n)$‎ طراحی کنید تا کم‌ترین تعداد از این ‎$n$‎ نورافکن را روشن کند به‌طوری که تمام نقاط بازه‌ی ‎$[0,m]$‎ روشن شود و یا اعلام کند که روشن کردن این بازه توسط نورافکن‌های موجود امکان‌پذیر نیست.

مقدار حافظه‌ای که الگوریتم شما استفاده می‌کند نیز باید از ‎$O(n)$‎ باشد.

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