وب سایت شخصی سجاد رفاقت

مسئله‌ی حرکت سربازها

مساله 6 - صفحه 12 کتاب «مساله‌های الگوریتمی»: حرکت سربازها

N سرباز در یک ردیف ایستاده‌اند به‌طوری‌که تعدادی از آنها به طرف راست و تعدادی دیگر به طرف چپ رو کرده‌اند. با هر فرمان فرمانده، هر دو سربازی که روبه‌روی هم ایستاده‌اند به جهت مخالف چرخش می‌کنند به‌طوری‌که پشت به پشت هم قرار گیرند. ثابت می‌شود که بعد از تعدادی انجام این عمل به وضعیتی می‌رسیم که هیچ دو سربازی مقابل هم قرار نگرفته‌اند.

برنامه‌ای بنویسید که با گرفتن ورودی از فایل، تعداد دفعات لازم برای تکرار این عمل را تا رسیدن به حالت پایدار در فایل خروجی چاپ نماید. در سطر اول فایل ورودی تعداد سربازها (1 <= N <= 200) و در سطر بعد به‌ترتیب جهت نگاه آن‌ها با استفاده از حروف L (به نشانه‌ی چپ) و R (به نشانه‌ی راست) نوشته شده است.

به مثال زیر توجه کنید:

INPUT.TXT:
5
RLLLL

OUTPUT.TXT:
Number of moves is equal to 4.

من این مساله را به چندین روش مختلف و با زبان‌های برنامه‌نویسی متفاوتی حل کرده‌ام اما برخلاف روش معمول حل مساله‌های مربوط به مسابقات که معمولا ورودی از یک فایل متنی خوانده شده و خروجی نیز در یک فایل متنی نوشته می‌شود، جهت سهولت کار و تمرکز بر روی الگوریتم مساله، ورودی از کاربر دریافت می‌شود و خروجی نیز به شکل ساده در صفحه نمایش نشان داده می‌شود. در مطلب «تکنیک‌های برنامه‌نویسی ACM» در مورد تکنیکهای مربوط به ورودی و خروجی مسابقات برنامه‌نویسی بطور مفصل صحبت کرده‌ام.

خروجی برنامه‌ها به شکل زیر است: