مرتب‌سازی کارتی
شرکت YSC دستگاه‌های الکترونیکی مختلفی را تولید و به بازار روانه کرده است. از جمله دستگاه کارت‌خوان٬ دستگاه مقایسه‌گر و کارت‌های مغناطیسی. هر یک از دستگاه‌های کارت‌خوان و نیز هر کارت مغناطیسی یک حافظه دارد که یک عدد در آن ذخیره می‌شود. هنگامی که یک کارت مغناطیسی را به دستگاه کارت‌خوان وارد کنیم دو نوع عمل می‌توانیم انجام بدهیم:
- با فشار دادن دکمه‌ی «سبز» دستگاه کارت‌خوان٬ عدد ذخیره‌شده در کارت پاک می‌شود و به جای آن عدد موجود در حافظه‌ی کارت‌خوان نوشته می‌شود.
- با فشار دادن دکمه‌ی «قرمز» عکس این عمل انجام می‌شود٬ یعنی عدد ذخیره‌شده در حافظه‌ی کارت‌خوان پاک می‌شود و به جای آن عدد موجود در حافظه‌ی کارت نوشته می‌شود.
کار دستگاه مقایسه‌گر آن است که وقتی دو کارت را به طور هم‌زمان به دو ورودی آن وارد کنیم دستگاه نشان می‌دهد که عدد ذخیره شده در کدام یک از کارت‌های بزرگ‌تر است. در صورت مساوی بودن این دو عدد دستگاه آن را نیز مشخص می‌دهد.
در یک روز تعطیل٬ شرکت YSC تصمیم گرفت یک بازی دسته‌جمعی بین ۱۰۰ کارمند خود برگزار کند. برای این بازی ۱۰۰ دستگاه کارت‌خوان روی یک میز طولانی به ترتیب از چپ به راست قرار داده شد. هم‌چنین دو عدد کارت و یک دستگاه مقایسه‌گر و یک قلم و دفترچه‌ی یادداشت به هر کارمند داده شد.
این بازی در ۱۰۱ مرحله انجام می‌شود. در هر مرحله‌ی بازی٬ هر یک از کارمندان می‌تواند یکی از دستگاه‌های کارت‌خوان را انتخاب و یک بار از آن استفاده کند (یعنی یکی از کارت‌های خود را وارد آن دستگاه نماید٬ فقط یکی از کلیدهای سبز یا قرمز را فشار دهد و کارت را خارج کند). توجه کنید که هر دستگاه کارت‌خوان در هر مرحله تنها می‌تواند مورد استفاده‌ی یک کارمند قرار گیرد. اما هر کارمند می‌تواند به هر تعداد و در هر زمان از دستگاه مقایسه‌گر خود استفاده کند.
چون اعداد به صورت الکترونیکی در حافظه‌ها ذخیره می‌شوند کارمندان به هیچ روشی نمی‌توانند از مقدار عددهای ذخیره شده در حافظه‌ی کارت‌خوان‌ها یا کارت‌ها مطلع شوند. هم‌چنین هیچ‌یک از کارمندان نمی‌تواند کارت خود را در اختیار همکارانش بگذارد یا به دستگاه مقایسه‌گر دیگران وارد کند.
در ابتدای بازی در حافظه‌ی هر یک از دستگاه‌های کارت‌خوان یک عدد ذخیره شده است به طوری که این اعداد از هم متمایزند. هدف آن است که اعدادی که در ابتدای بازی در حافظه‌ی کارت‌خوان‌ها ذخیره شده بودند در انتهای مرحله‌ی ۱۰۱ام به صورت مرتب‌شده از چپ به راست در حافظه‌ی کارت‌خوان‌ها قرار داشته باشند. یعنی کوچک‌ترین عدد از بین ۱۰۰ عدد اولیه٬ در پایان بازی در حافظه‌ی سمت چپ‌ترین کارت‌خوان٬ دومین عدد در حافظه‌ی کارت‌خوان بعدی و … و به همین ترتیب بزرگ‌ترین عدد در حافظه‌ی سمت راست‌ترین کارت‌خوان ذخیره شده باشد.
یک شیوه طراحی کنید که اگر کارمندان براساس آن قبل از شروع بازی هماهنگ شوند و بر طبق آن بازی کنند٬ به هدف بازی دست پیدا کنند. برای این کار نشان دهید که یک کارمند دل‌خواه در هر مرحله چه کاری و با کدام کارت‌خوان انجام می‌دهد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
