در شهر تهران، میدان عجیبی به‌نام میدان ‎«\chiz»‎ وجود دارد که دور آن ‎$n$‎ خانه وجود دارد. هر خانه یک بالکن دارد و در هر خانه دقیقاً یک نفر زندگی می‌کند. هر نفر هر روز در یک ساعت مشخّص به بالکن می‌رود، مدت مشخّصی به تماشای میدان می‌ایستد و پس از آن دوباره به اتاق خود بر می‌گردد‎!‎

متأسفانه اطلاع‌رسانی در این شهر تا اندازه‌ای ضعیف‌ است و هر وقت خبر مهمی می‌شود، ‎«جارچی»‎ مجبورست وسط میدان بایستد و خبر را جاربزند‎!‎ منتها مشکل کار این‌جاست که در زمان جار زدن، تنها کسانی خبر را می‌شنوند که در آن لحظه روی بالکن باشند‎ (می‌‎توانید فرض کنید این افراد دقیقاً در لحظه‌ی آمدن به بالکن و بازگشتن به اتاق نیز خبر را می‌شنوند).

یک‌روز صبح دولت وقت تصمیم گرفت نرخ آزاد بنزین را (که از مدتی قبل سهمیه‌بندی شده بود) برابر ‎$x$‎ ریال اعلام کند. به‌دلیل مشکلات ناشی از جار زدن (نظیر آلودگی صوتی و غیره)، دولت تصمیم می‌گیرد که جارچی تنها یک‌بار و آن‌هم رأس ساعت ‎۹‎ صبح (اوّ‎لین زمان آمدن افراد به بالکن‌شان)، در میدان شهر جار بزند که ‎«بنزین آزاد لیتری ‎$x$‎ ریال شده»‎ تا افرادی که در آن زمان روی بالکن هستند، از این مهم آگاهی پیدا کنند. منتها پیش از آن، دولت اقدام به فرهنگ‌سازی کرده و به هر کدام اهالی میدان ‎\chiz‎ آموزش داده که اگر زمانی شما روی بالکن بودید و خبر نرخ بنزین آزاد را می‌دانستید و یکی دیگر از اهالی روی بالکن آمد، نرخ بنزین را به او بگویید. با این تدبیر و دانستن این موضوع که در هر لحظه حداقل یک نفر از اهالی روی بالکن است، دولت تضمین می‌کند که در پایان روز همه‌ی اهالی، نرخ آزاد بنزین را بدانند.

منتها مشکل کار در غریزه‌ی ‎«شایعه پراکنی»‎ اهالی میدان ‎\chiz‎ است‎!‎ این افراد به‌طور غریزی و غیرارادی وقتی قیمت بنزین را ‎$x$‎ ریال می‌شنوند، قیمت بنزین را به نفرات بعدی (کسانی که بعداً به بالکن می‌آید)، ‎$2x$‎ ریال اعلام می‌کنند‎!‎ از سوی دیگر، به دلیل این‌که خود این افراد از این حس مطّلع‌اند، هر کس اگر در لحظه‌ی آمدنش به بالکن چند نرخ بشنود، نرخ کمتر را باور می‌کند.

با این وصف، به‌دولت کمک کنید و الگوریتمی از زمان ‎${\cal O}(n^2)$‎ ارائه کنید تا با دانستن زمان ابتدا و زمان انتهای روی بالکن بودن هر یک از افراد‎ (این زمان‌ها لزوماً طبیعی نیستند؛ صرفاً اعداد حقیقی بزرگتر از ‎۹ (صبح)‎ و کوچک‌تر از ‎۲۴ (نیمه‌شب)‎ هستند)، گران‌ترین نرخ بنزینی که یک نفر باور می‌کند را به‌دست بیاورد. درستی الگوریتم خود را اثبات کنید.

• سوال بعد