گردنبندي عتيقه از سنگ‌هاي قيمتي رنگي (هر مهره دو رنگ دارد) که به يک برنامه‌نويس رسيده بود، در يک حادثه پاره مي‌شود و اين فرد به‌هر ترتيب که هست، مي‌خواهد سنگ‌هاي پيدا شده را دوباره به هم بچسباند.
تنها اطلاعاتي که از اين گردنبند دارد اين است که هر دو دانه رنگي در نقطه مشتركي كه به هم برخورد مي‌كردند، هم‌رنگ بودند. از آنجا که او مطمئن نيست كه تمام دانه‌ها را جمع كرده يا نه، مي‌خواهد بداند كه آيا ممكن است تا گردنبند را مثل اول درست كند؟ اگر اين امكان هست، چگونه مي‌توان آن را مرتب كرد؟
برنامه‌نويس پرکار هم به‌جاي حل مساله به‌شيوه ذهني، يک مساله برنامه‌نويسي مطرح کرده است که ورودي آن به اين صورت است:
اولين خط ورودي‌ها شامل int t است كه تعداد حالات مختلف آزمايش را به ما مي‌دهد.
اولين خط از هر حالت تست شامل N?X?
1000)int N) كه تعداد دانه‌هايي است كه پيدا شده است.
هر كدام از N خط‌هاي بعدي شامل دو تا int است كه رنگ‌هاي يك دانه را تشريح مي‌كند. رنگ‌ها به‌صورت 1 تا 50 ارائه مي‌شوند.
خروجي
براي هر حالت آزمايش، شماره حالت آزمون را در خروجي چاپ كنيد (همان‌طور كه در جواب نمونه آورده شده). اگر گردآوري دوباره دانه‌ها غيرممكن بود، جمله تعدادي از دانه‌ها احتمالا گم شده است را چاپ كنيد. در غير اين صورت N خط كه هر كدام با تك دانه‌اي كه شرح داده شده براي 1 ? i ? N- 1 را چاپ كنيد.
دومين عدد int در هر خط بايد با اولين int خط بعدي يكي باشد. همچنين در آخرين خط عدد int دومي بايد با عدد int خط اول يكي باشد. (يك خط خالي بين دو حالت متوالي جواب‌هايتان چاپ كنيد.)
راه‌هاي مختلفي براي حل اين مساله وجود دارد كه هر كدام از آنها از سوي شما قابل قبول خواهد بود.
نمونه ورودي
2
5
1 2
2 3
3 4
4 5
5 6
5
2 1
2 2
3 4
3 1
2 4
نمونه خروجي
Case #1
some beads may be lost
Case #2
2 1
1 3
3 4
4 2
2 2
اما روش حل مساله! براي حل اين مساله ممکن است راه‌هاي مختلفي وجود داشته باشد ما يکي از راه‌هاي موجود که با توجه به مساله‌اي که سه هفته پيش مطرح کرديم (يعني مساله وزيران)، در همان مقاله توضيح داديم که براي حل مساله از روش پسگرد (BackTracking) استفاده کرده‌ايم يعني عملي را انجام مي‌دهيم تا زماني که درست باشد، وقتي به يک جواب غلط رسيديم به حالت درست بعدي که در مرحله قبل وجود دارد بررسي مي‌کنيم، بسيار خب از همين روش براي حل اين مساله استفاده مي‌کنيم.
خب اول يک سري شرط را بررسي مي‌کنيم تا ببينيم اين مساله با داده‌هاي بيان شده در صورت مساله حل مي‌شود يا نه؟
اولين شرط اين است که چون گردنبد به‌صورت حلقه‌ است و اگر مهره‌اي با رنگ آبي-قرمز به عنوان اولين مهره انتخاب شود بايد حداقل يک مهره وجود داشته باشد که به‌صورت قرمز-* باشد، يعني حداقل مهره‌اي وجود داشته باشد که با رنگ قرمز شروع شود (مهره‌ها به‌صورت يک زوج مرتب هستند)، همان‌طور که در روش پسگرد توضيح داده شده است، اول بايد يک درخت رسم کنيم، ريشه درخت يکي از مهره‌هاي ماست که يک زوج مرتب است که به‌صورت «Tuple«int,int تعريف شده، در سطح بعدي بايد مهر‌ه‌هايي انتخاب شوند که در شرط زير صادق باشند:
if (tuple1.Item2 == tuple2.Item1)
يعني اگر مهره آبي-قرمز انتخاب شود بايد مهر‌ه‌هايي انتخاب شوند که به‌صورت قرمز-* باشند، بعد از اين مرحله يکسري مهره مي‌ماند يکي از آنها انتخاب مي‌شود که به‌صورت قرمز-سبز است، از باقي مهره‌ها مهر‌هايي انتخاب مي‌شوند که بصورت سبز-* باشند اين عمل را تا زماني انجام مي‌دهيم که تمام مهره‌ها تمام شود، و اگر مهره‌‌ها تمام شد و گردنبند درست شد، به جواب درست رسيده‌ايم و مهره‌ها را به‌ترتيب در خروجي چاپ مي‌کنيم (همان‌طور که در صورت سوال توضيح داده شده‌است).
اميربهاالدين سبط‌الشيخ