در کشور دو ریل راه آهن موازی وجود دارند که در ریل شمالی فقط از سمت شرق به غرب میتوان حرکت کرد و در ریل جنوب فقط از غرب به شرق. این ریل به $m$ بلوک که از غرب به شرق به ترتیب با شماره های ۰ تا $m-1$ تقسیم شده است و در هر ریل بین هر دو بلوک مجاور بستهایی قرار گرفته است. در $n$ تا از بلوکها، هر کدام دقیقا یک ایستگاه قرار دارد. هر بلوک یا میتواند خالی باشد، یا بلوک از نوع «الف» که به ایستگاه آن فقط از ریل شمالی میتوان رسید و از طریق ریل جنوبی خارج شد، و یا بلوک از نوع «ب» که فقط میتوان از ریل جنوبی بدان رسید و از طریق ریل شمالی خارج شد.

مثلا شکل زیر را در نظر بگیرید. در این شکل ۷ بلوک با شماره های صفر تا ۷ و همچنین ۴ ایستگاه با شماره های ۰ تا ۳ مشخص شده اند و مثلا در بلوک ۱ (که از نوع نوع الف است) ایستگاه شماره ۳ قرار دارد و در بلوک ۵ (از نوع ب) ایستگاه شماره ۱ و بلوک ۴ خالی است. همچنین بستها با مستطیل های خاکستری مشخص شده اند.

ما تعداد ایستگاه ها ($n$) را میدانیم، همچنین میدانیم ایستگاه صفر در چه شماره بلوکی قرار دارد و نوع آن بلوک «الف» است. ولی از شماره و نوع بلوک سایر ایستگاه ها اطلاعی نداریم. هر بار میتوانیم به یک سیستم رایانه ای شماره دو ایستگاه $a$ و $b$ را بدهیم و آن سیستم به ما میگوید فاصله بین آن دو ایستگاه چقدر است، یعنی در طول حرکت از ایستگاه $a$ به ایستگاه $b$ از چند بست می گذریم. برای مثال در شکل بالا اگر بخواهیم از ایستگاه ۰ به ایستگاه ۲ برسیم باید ابتدا از بلوک ۲ وارد ریل جنوبی شده سپس از بلوکهای ۳ و ۴ عبور کنیم و بعد با گذشتن از ایستگاه ۱ وارد ریل شمالی شویم و از بلوک ۴ بگذریم و از طریق بلوک ۳ وارد ایستگاه ۲ شویم. در طول این مسیر از ۵ بست میگذریم پس فاصله ایستگاه ۰ و ۲ برابر ۵ است.

الگوریتمی ارایه دهید که با حداکثر $3n$ سوال بتواند شماره و نوع بلوک مربوط به هر ایستگاه را پیدا کند.

منبع: المپیاد جهانی کامپیوتر ۲۰۱۴ - تایوان