شرکت خدمات پیشخوان ایرانیان و شرکت فناوران اطلاعات پیشخوان ایرانیان قصد برگزاری یک مسابقهی برنامهنویسی به صورت هکاتون را دارند. در این مسابقهی برنامهنویسی، هر تیم روی میز مخصوص به خودش نشسته است. دو شرکتی که اسپانسر برگزاری این هکاتون را دارند نیز، در غرفههایی وسایل و غذای رایگان میدهند. سارا و دوستانش نیز در این مسابقه شرکت کردهاند.
در حقیقت، سارا برای برنده شدن یا حتی تلاش برای برنده شدن در آنجا نیست؛ او همیشه به دنبال هکاتونهای جدیدی است که به آنها بپیوندد، به خصوص وقتی که با مزایای رایگان در آن هکاتونها باشن. این بار، غرفهی مختلف وجود دارد که شروع به توزیع وسایل و غذای رایگان خواهند کرد. میتوان گفت هکاتون در یک جدول مستطیلی برگزار میشود (یعنی نمای از بالا به پایین مسابقه به این شکل است). غرفهها همگی در سطر اول قرار دارند و غرفهی -ام در مختصات (، ) قرار دارد. سارا مکان هر یک از رقیب دیگر را میداند، رقیب i-ام در مختصات (, ) قرار دارد، در حالی که مکان سارا مختصات (, ) است. ممکن است چند رقیب در یک مختصات قرار گرفته باشند.
هنگامی که توزیع وسایل و غذای رایگان اعلام میشود، سارا میداند که هر رقیب بلافاصله به نزدیکترین غرفه حرکت خواهد کرد و در صورت پیش آمدن حالات برابر، غرفهی سمت چپ را انتخاب میکند. حرکت در شبکه فقط به صورت افقی یا عمودی امکانپذیر است و حرکت به اندازهی یک واحد در هر جهت، یک ثانیه طول میکشد.
با توجه به این اطلاعات، سارا میخواهد استراتژی خود را بهینه کند و احتمال خود را برای انتخاب بهترین وسیلهی رایگان موجود بیشینه کند: او به غرفهای میرود که کمترین تعداد افراد قبل از او به آنجا برسند. اگر او به غرفهای همزمان با رقیب دیگری برسد، مهربانی او غلبه میکند و اجازه میدهد آنها اول انتخاب کنند.
به او کمک کنید که تعداد افرادی که قبل یا همزمان با او به غرفه انتخاب شده میرسند را محاسبه کند.
شما باید یک خط شامل یک عدد صحیح بنویسید: کمترین تعداد رقیبی که حداقل به همان اندازه زودی که سارا به غرفه برسد، به آنجا میرسند.