آیدا قصد دارد جشن تولد بگیرد. متاسفانه به دلیل مشغله‌ی زیاد٬ تصمیم گرفته است مسئولیت کلیه‌ی تدارکات مراسم عروسی را به دوستش آقای «کاف» بدهد! آقای کاف پس از جست وجوی فراوان برای تدارکات نور عروسی٬ موفق به خرید یک «ریسه‌»ی ۱۰۰ لامپی (شامل ۱۰۰ عدد سرپیچ لامپ و ۱۰۰ عدد لامپ) شده است. ریسه تعدادی سرپیچ متصل به هم است که در صورتی که به آن‌ها لامپ بسته شود٬ به زیبایی روشن می‌شوند. البته فروشنده گفته است که دقیقاً ۵۰ تا از لامپ‌ها سالم و ۵۰ تای بقیه خراب‌اند. هم‌چنین دقیقاً ۵۰ تا از سرپیچ‌ها سالم و بقیه خراب‌اند!

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

ضمناً می‌دانیم که باز کردن یک لامپ از یک سرپیچ دقیقاً یک دقیقه طول می‌کشد ولی از آن‌جا آقای کاف در بستن لامپ به سرپیچ مهارت زیادی دارد٬ زمان بستن یک لامپ صفر ثانیه فرض می‌شود.

الگوریتمی برای آقای کاف بنویسید (یعنی مراحل دقیق انجام کار را مشخص کنید) که در حداقل زمان بتواند لامپ‌های سالم و نیز سرپیچ‌های سالم را پیدا کرده و ریسه را با ۵۰ لامپ روشن برای جشن تولد آماده کند. دقت کنید که لزومی ندارد که در انتهای کار تمامی لامپ‌ها به تمامی سرپیچ‌ها متصل باشند. یک الگوریتم درست (ولی با زمان بد) چنین است:

1. یکی از لامپ‌ها که تاکنون آزموده نشده است بردار.
2. لامپ‌ برداشته شده را با تمام سرپیچ‌هایی که خالی هستند امتحان کن٬ در صورتی که روشن شد٬ لامپ را در آن سرپیچ رها کرده وگرنه به سراغ سرپیچ بعدی برو.
3. اگر لامپ آزموده نشده‌ای باقی مانده است به مرحله‌ی ۱ برو.

می‌توان ثابت کرد این الگوریتم در بدترین حالت٬ ۷۵۵۰ دقیقه طول می‌کشد.

الف. الگوریتمی بنویسید که حداکثر در ۵۰۰ دقیقه٬ ریسه را با ۵۰ لامپ روشن آماده کند.

ب. الگوریتمی بنویسید که حداکثر در ۲۵۰ دقیقه٬ ریسه را با ۵۰ لامپ روشن آماده کند.

توجه: حتماً در سطر اول پاسخ‌نامه٬ حداکثر زمان الگوریتم خود را بنویسید. در صورتی که فقط قسمت «ب» را به درستی حل کنید٬ نمره‌ی کامل این مسئله را خواهید گرفت.

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