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

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

انتخاب واحد نیمسال اول 88

انتخاب واحد دانشجویان ورودی 86 روز دوشنبه 88/6/9 است. لیست دروس ارایه شده را در اینجا ببینید.

Summer Games, The Next!

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

به ستون چپ صفحه منتقل شد.

تحویل پروژه اختیاری ساختمان داده ها

پوزش مرا بابت ناهماهنگی ایجاد شده در تحویل پروژه اختیاری درس ساختمان داده بپذیرید.
تحویل این پروژه ( مشابه پروژه های قبلی) بصورت حضوری و در هفته اول مهر ماه (۵ تا ۸ مهر) انجام خواهد شد.
نمره نهایی قبل از ترمیم اعلام می شود.

SG2009 - The Problems

دوستانی که در بازیها شرکت می‌کنند اگر به مشکلی در حل سوالات برمی‌خورند حتما سعی کنند در قسمت نظرات با دیگران مشورت کنند. فعلا تا راه‌اندازی سیستم فروم گروه، تنها راه مناسب بحث درباره سوالات، بخش نظرات است.

سوال یازدهم: ارتش
آدرس سوال: https://www.spoj.pl/problems/ARMY
سطح: دو
زمان حل: 2 روز
منابع مطالعاتی: بخش 9.1 کتاب [۱]، شما بگید!
کلمات کلیدی حل: ماکزیمم، شما بگید!
نکات کلیدی حل: شما بگید!
کد حل: دریافت کنید.

سوال دوازدهم: آقای جرج
آدرس سوال: https://www.spoj.pl/problems/GEORGE
سطح: چهار
زمان حل: 5 روز
منابع مطالعاتی: بخش 24.3 کتاب [۱]، بخش 4.2 کتاب [۲]، شما بگید!
کلمات کلیدی حل: دیکسترا، شما بگید!
نکات کلیدی حل: شما بگید!
توضیحات حل: حل با تغییر جزیی الگوریتم دیکسترا ممکن است. کافیست علاوه بر ماتریس مجاورت w، ماتریس A دیگری از جاده ها داشته باشیم که در خانه ij آن زمان ورود جرج به آن جاده قرار دارد. در الگوریتم دیکسترا با فرض این که در هر لحظه راسی که کوتاه ترین مسیر آن تعیین شده است u باشد، برای هر راس v متصل به u اگر d[u]>=A[u,v]&&d[u]<A[u,v]+w[u,v] برقرار باشد باید زمانی اضافی را متناسب با مقادیر ماتریس های A و w و بردار d به زمان عادی بین u و v (w[u,v]) افزود.
کد حل: شما بگید!

موفق باشید.

-------------------
[۱] Introduction to Algorithms, 2nd Edition
[۲] طراحی الگوریتمها با شبه کدهای ++C، جعفرنژاد قومی، جهاد دانشگاهی

SG2009 - The Problems

سوال نهم: فیل‌ها
آدرس سوال: https://www.spoj.pl/problems/BISHOPS
سطح: سه
زمان حل: 3 5 6 روز
منابع مطالعاتی: شما بگید!
کلمات کلیدی حل: شما بگید!
نکات کلیدی حل: 1. ابتدا فرمول آن را محاسبه کنید. 2. توابع لازم برای کار با اعداد بزرگ را بنویسید. 3. شما بگید!
کد حل: دریافت کنید.

سوال دهم: شمارش لغت
آدرس سوال: https://www.spoj.pl/problems/WORDCNT
سطح: سه
زمان حل: 3 5 6 روز
منابع مطالعاتی: شما بگید!
کلمات کلیدی حل: شما بگید!
نکات کلیدی حل: 1. بیشترین تعداد کلمات هم‌طول که کنار هم هستند را محاسبه کنید¹. 2. شما بگید!
کد حل: دریافت کنید.

-----------
^۱ در تست اول سه تا کلمه با طول دو کنار هم قرار دارند. در تست دوم پنج کلمه یک حرفی کنار هم، وجود دارد.

استاد حمیدی دست به کار شد

پس از مدت ها انتظار نمرات درس شیوه ارائه مطالب علمی و فنی که در ترم گذشته توسط استاد حمیدی ارائه شده بود، اعلام شد.
درس شیوه ارائه هرچند یک درس 2 واحدی به نظر می آمد ولی نسبت به بسیاری از درس های تخصصی سخت تر بود و تحویل پروژه این درس بسیار زمان بر و طاقت فرسا بود و بسیاری از دانشجویان حتی ممتاز(!) را به چالش کشید اما به هر تقدیر پروژه ها تحویل استاد شد.
از لحظاتی پیش نمرات این درس البته به صورت تایید نشده بر روی سامانه جامع آموزشی گلستان قرار گرفت. ظاهرا قید تایید نشده در جلوی نمره این درس راه اعتراض را بر روی دانشجویان همچنان بازگذاشته است. خبرهای اولیه رسیده نشان می دهد استاد حمیدی نکات زیادی را برای نمره دهی در این درس لحاظ کرده است و دقت نظر خاصی را مانند همیشه از خود به نمایش گذاشته است. تا این لحظه ازبین دوستانی که نمره خود را مشاهده کرده اند گزارش اعتراض آمیزی دریافت نشده است.
امیدواریم هرچه زودتر استاد حمیدی نمرات درس طراحی الگوریتم را نیز اعلام کند.

SG2009 - The Problems

لطفا دوستانی که سوالات رو حل می‌کنند سعی کنند بخش‌های "شما بگید" سوالات را هم تکمیل و در بخش نظرات اعلام کنند.

سوال ششم: میزها
آدرس سوال: https://www.spoj.pl/problems/AE1B
سطح: یک
زمان حل: 4 روز
منابع مطالعاتی: شما بگید!
کلمات کلیدی حل: مرتب‌سازی، شما بگید!
نکات کلیدی حل: 1. مرتب‌سازی نزولی و انتخاب حداقل تعداد مورد نیاز 2. شما بگید!
کد حل: یک کد خوب، دریافت کنید.

سوال هفتم: کیمیا
آدرس سوال: https://www.spoj.pl/problems/BYTESM2
سطح: دو
زمان حل: 4 روز
منابع مطالعاتی: شما بگید!
کلمات کلیدی حل: Dynamic Programming، شما بگید!
نکات کلیدی حل: 1. حرکت سطری از سطر دوم تا آخر 2. بررسی کنید به هر سلول سطر دوم بهترین راه از سطر اول کدام است، سپس به هر سلول سطر سوم بهترین راه از سطر دوم، و الی آخر 3. شما بگید!
کد حل: دریافت کنید.

سوال هشتم: تقسیمات
آدرس سوال: https://www.spoj.pl/problems/EQDIV
سطح: سه
زمان حل: 4 روز
منابع مطالعاتی: لینک ۱، شما بگید!
کلمات کلیدی حل: Backtracking، شما بگید!
نکات کلیدی حل: 1. استفاده از یک تابع بازگشتی که خانه‌های مجاور و هم‌شماره را پیمایش می‌کند 2.شما بگید!
کد حل: دریافت کنید.