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

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

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