SG2009 - The Final Problem

خوب است به عنوان آخرین مسئله‌ای که در بازی‌های تابستانی امسال مطرح می‌کنیم، به مسئله‌ای کاربردی بپردازیم که خود شما و سایر دانشجویان نیز بتوانید در عمل از نتیجه آن استفاده کنید.

سوال سیزدهم: بیشترین واحد
سطح: سه
زمان حل: ۳ روز
کلمات کلیدی حل: NP-Complete، شما بگید!
نکات کلیدی حل: ۱. از هر راهی که جواب می‌دهد، حل کنید. ۲. این گونه مسایل را سعی کنید با دید گرافی حل کنید. ۳. این مسئله یک مسئله کلی‌تر نسبت به پروژه هشتم طراحی الگوریتم است. ۴. شما بگید!
فایل اجرایی: دریافت کنید: ویندوز  لینوکس
توضیحاتِ پس از حل: { با توجه به NP-hard بودن مسئله، اکثر راه حل‌های ساده، جواب می‌دهد. راه حلی که لینک دریافت آن قرار داده شده است دارای پیچیدگی O(n²2ⁿ) است. در کامپیوترهای امروزی یک میلیارد دستور در کمتر از یک ثانیه اجرا می‌شوند از این رو چنین برنامه‌ای در عمل قابل استفاده است و دانشجویان می‌توانند برنامه‌ریزی انتخاب واحد خود را به آن بسپارند. الگوریتم‌های تقریب نیز برای این مسئله وجود دارد ولی خطای آن بیش از اندازه‌ای است که قابل چشم‌پوشی در یک انتخاب واحد، با دروس اندک باشد. همچنین می‌توانید سلایق خود را بیشتر در نحوه برنامه‌ریزی برنامه‌ای که نوشته‌اید دخیل کنید. مثلا ممکن است فردی به جهت مسافت دور تمایل داشته باشد تا شنبه صبح حدالامکان درسی نداشته باشد یا برخی مایلند بیشتر برنامه‌هایشان در نیمه اول روز باشد یا حتی در صورت امکان درس‌ها در چند روز بخصوصی از هفته باشد و مابقی هفته برنامه‌ای نداشته باشد. این‌ها همه ویژگی‌هایی است که می‌توانید در برنامه خود اعمال کنید. فکر می‌کنید در اطرافتان چه موضوعات دیگری برای برنامه‌ریزی خودکار وجود دارد؟ }

و اما صورت مسئله:

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

ورودی:
ورودی شامل دروس قابل انتخاب برای یک دانشجو است. در خط اول، تعداد رکوردهای دروس 1<=N<=30 قرار دارد. در N خط بعدی رکوردها با قالب زیر قرار دارند:

[CourseID: a base 30 number: 0-9a-tA-T][Name: a string of up to 30 alphabetical characters (a-zA-Z)][Units: 1-9][L:Lecture times per week: 1-9][L times: DHHMM-HHMMT]

قسمت اول حاوی شناسه هر رکورد و عددی در مبنای 30 است که با کاراکترهای 0 تا 9 یا a/A تا t/T معین می‌شود. در صورت وجود چندین درس با شناسه یکسان فقط یکی از آن‌ها می‌تواند در خروجی وجود داشته باشد.
قسمت دوم نام درس است، رشته‌ای از کاراکترهای الفبایی با طول حداکثر ۳۰ کاراکتر.
قسمت سوم تعداد واحدهای آن درس قرار دارد و عددی یک رقمی است.
قسمت چهارم تعداد جلسات در هفته آن درس را مشخص می‌کند و عددی یک رقمی است.
قسمت پنجم به تعداد جلسات درس، زمان هر جلسه را مشخص می‌کند. زمان در قالب DHHMM-HHMMT است که HHMM نخست ساعت شروع HHMM دوم ساعت پایان جلسه را مشخص می‌کند. T زوج یا فرد بودن جلسه را مشخص می‌کند، برای جلسات زوج E، برای جلسات فرد O و برای جلسات عادی A است. D روز جلسه را به صورت زیر مشخیص می کند:
شنبه: A
یکشنبه: S
دوشنبه: M
سه‌شنبه: T
چهارشنبه: W
پنج‌شنبه: U
جمعه: F

خروجی:
خروجی باید سه برنامه قابل انتخاب (در صورت وجود) با بیشترین واحد قابل انتخاب را معرفی کند. فرمت خروجی باید همانند نمونه باشد.

نمونه ورودی:

6
1MemariA33W0800-1000OW1000-1200AW1300-1500A
1MemariB33W0800-1000ET1300-1500AW1000-1200A
2TarrahiA33M1700-1900OA1300-1500AS1700-1900A
2TarrahiB33M1700-1900ES1300-1500AW0800-1000A
4HushA33A1700-1900OM0800-1000AM1700-1900A
4HushB33M1300-1500ET1000-1200AT0800-1000A

نمونه خروجی:

Program #1:
Courses:
 1. MemariB    2. TarrahiA    3. HushB
Units: 9
Program #2:
Courses:
 1. MemariA    2. TarrahiA    3. HushB
Units: 9
Program #3:
Courses:
 1. MemariB    2. HushA
Units: 6

برنامه‌های خود را به وبلاگ ارسال کنید.
موفق باشید.