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

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

مسابقه‌ی برنامه‌نویسی CodeCup 2018 - الگوریتمستان
الگوریتمستان
115.005.00
آنچه در این نوشته می‌خوانید:

مسابقه‌ی برنامه‌نویسی CodeCup 2018

مسابقه‌ی برنامه‌نویسی CodeCup 2018 با موضوع پیاده‌سازی بازی Black Hole (سیاه‌چاله) روز شنبه، ۳۰ دی ماه ۱۳۹۶ برگزار می‌شود. علاقه‌مندان به شرکت در این مسابقه‌ی برنامه‌نویسی چالشی تا ساعت ۱۲ ظهر آن روز (به وقت گرینویچ) فرصت دارند کد نهایی خود را ارسال کنند. زبان‌های برنامه‌نویسی مجاز به شرح زیر است.

C, C++, C++11, FreePascel, Java, Python,  Python 3, Haskell

    در ادامه توضیح فارسی مسابقه آمده است. جهت ثبت نام و مشاهده‌ی جزئیات بیشتر به نشانی زیر مراجعه نمایید.

CodeCup 2018

      

معرفی بازی

  [بازگشت به فهرست]

بازی سیاه‌چاله (Black Hole) یک بازی دو نفره روی یک صفحه‌ی مثلثی متشکل از ۳۶ خانه‌ی شش‌ضلعی مجاور هم است. زمان شروع بازی تمام خانه‌ها به غیر از پنج محل خالی هستند و آن پنج محل با سنگ‌های قهوه‌ای رنگ پوشیده شده است.

      

مسابقه‌ی برنامه‌نویسی CodeCup 2018

      

    بازیکن اول ۱۵ کاشی شش‌ضلعی قرمز و بازیکن دوم ۱۵ کاشی شش‌ضلعی آبی دارند که برای هر کدام از ۱ تا ۱۵ شماره‌گذاری شده‌اند. هر بازیکن در نوبت خود می‌تواند یکی از کاشی‌های در اختیارش را در یکی از خانه‌های خالی صفحه بگذارد. بازی زمانی خاتمه پیدا می‌کند که همه‌ی کاشی‌ها روی صفحه قرار گرفته باشند. در نهایت یک خانه‌ی خالی باقی می‌ماند. این خانه‌ی خالی سیاه‌چاله که تمام کاشی‌های مجاور خود را می‌بلعد!

      

روش محاسبه‌ی امتیاز

  [بازگشت به فهرست]

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

امتیاز نفر اول: 75 + R - B

امتیاز نفر دوم: 75 + B - R

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

      

    مثال

    فرض کنید صفحه به صورت زیر پر شده باشد:

      

مسابقه‌ی برنامه‌نویسی CodeCup2018

      

    سه کاشی قرمز با اعداد 4، 7 و 14 و دو کاشی آبی با اعداد 2 و 11 در مجاورت سیاه‌چاله قرار دارند. بنابراین R = 25 و B = 13، امتیاز نفر اول 87 و امتیاز نفر دوم 63 می‌شود.

    اگر اجرای یک حرکت بیشتر از حد مجاز طول بکشد یا حرکت غیرمجازی صورت گیرد (مثلا قرار دادن کاشی در محلی که قبلا کاشی گذاشته شده) بازی با صفر امتیاز تمام شده و امتیاز رقیب بر اساس مواردی که در قوانین مسابقات آمده است، محاسبه خواهد شد.

      

روش دریافت ورودی و ارسال خروجی

  [بازگشت به فهرست]

ارتباط بازیکنان با کنترل‌کننده‌ی بازی از طریق ورودی و خروجی استاندارد (standard in and out) صورت می‌گیرد. همچین امکان استفاده از درگاه استاندارد خطا (standard error) وجود دارد.

    شکل زیر برچسب خانه‌های صفحه‌ی بازی را مشخص کرده است:

      

مسابقه‌ی برنامه‌نویسی CodeCup 2018

      

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

    دستور قرار دادن کاشی در خانه‌ای از صفحه باید به شکل زیر باشد:

<position>=<number>

    مثلا A3 = 6 یعنی کاشی با عدد 6 در خانه‌ی A3 قرار بگیرد.


نوشته‌های مرتبط
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left