به زودی جشن افتتاحیه ای برای یک رخداد بزرگ سیاسی برگزار خواهد شد و شما به عنوان مدیر تیم امنیتی آن قصد قرار دادن $n$ مامور خود در طول فرش قرمز مراسم دارید. ماموران شما با شماره های 1 تا $n$ مشخص شده و با یک سامانه خاص بی سیم مجهز شده اند. به دلایل امنیتی، نحوه کار این سامانه بی سیم به این صورت است که مامور شماره $i$ تنها می‌تواند با ماموران شماره $i-1$ و $i+1$ (در صورت وجود) صحبت کند. علاوه بر این برای هریک از دستگاه های بیسیمی که در اختیار ماموران قرار گرفته دامنه‌ای وجود دارد که تنها به مامورانی که به اندازه‌ای خاص به هم نزدیک باشند اجازه صحبت کردن با یک‌دیگر می‌دهد. به این صورت که اگر دامنه مجاز بی سیم مامور $i$ ام را $r_i$ و دامنه مجاز بی سیم مامور $j$ ام را $r_j$ در نظر بگیریم، این دو مامور تنها در صورتی قادر صحبت با یک‌دیگر خواهند بود که فاصله آن‌ها از کمینه دو مقدار $r_i$ و $r_j$ بیش‌تر نباشد. اولین وظیفه امنیتی شما این است که امکان برقرار ارتباط هر دو مامور را فراهم کنید. این ارتباط می‌تواند به صورت مستفیم و یا با استفاده از یک یا چند مامور میانی باشد.

فرش قرمز در یک خط مستقیم انداخته شده و هر چه بلندتر بودن آن نشانه شکوه بیش‌تر مراسم خواهد بود. اما از آنجا حتما باید در دو انتهای آن دو مامور قرار بگیرند و با توجه به وظیفه اول شما، طول این فرش نمی‌تواند خیلی بلند باشد. همه چیز خوب پیش می‌رفت تا یک روز مانده به مراسم که رئیس شما رسید و با نگاهی بر قراردهی مد نظر شما، چنین گفت:

«قراردهی فعلی ماموران در طول فرش قرمز از نظر ما خوشایند نیست. شما باید ماموران را از نظر قدی به صورت صعودی در طول فرش قرار دهید و ضمنا، فاصله هیچ دو ماموری نباید بیش از یک متر باشد!»

با توجه به عدم وقت کافی برای تغییر در سامانه‌های بی سیم ماموران، به نظر می‌رسد که تنها راه برای اعمال سفارشات رئیس و همچنین حفظ وظیفه اول (توانایی ارتباط مستقیم یا غیر مستقیم هر دو مامور)، کوتاه کردن طول فرش قرمز باشد. با داشتن دامنه مجاز بی سیم ماموران و همچنین قد هریک از آن‌ها، شما باید بیشینه طول ممکن برای فرش قرمز را بیابید.

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

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