پس از پیاده شدن از هواپیمای متلاشی‌شده و گذر از جنگل سرد و تاریک، آن‌ها مجبور شده‌اند از یک تونل تنگ و ترس‌ناک، به نام تونل ‎«مردافکن»‎ بگذرند. برای همین منظور، آقای ‎«کاف»‎ در جلوی همه وارد تونل شد و پشت سر او ‎$n$‎ دانش‌پژوه در ادامه‌ی صف قرار گرفتند.

می‌دانیم فاصله‌ی هر دانش‌پژوه با نفر جلویی‌اش، پارامتر وابسته‌ای به میزان شجاعت اوست؛ از این‌رو، فاصله‌ی هر دانش‌پژوه با نفر جلویی‌اش را ‎«بی‌باکی»‎ وی می‌نامیم. یک دانش‌پژوه را ‎«ترسو»‎ می‌گوییم، اگر بی‌باکی‌اش، از میانگین بی‌باکی سایر دانش‌پژوهان بیش‌تر نباشد‎!‎

با فرض دانستن محل استقرار افراد (فاصله‌‎ی هر کس از آقای کاف که عدد بسیار بزرگی است)، الگوریتمی از زمان اجرای متوسط ‎$O(n)$‎ ارائه دهید که یک دانش‌پژوه ترسو را شناسایی کند. الگوریتم خود را تحلیل و اثبات کنید.

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