الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مسابقه‌ی برنامه‌نویسی CodeCup 2018 - الگوریتمستان
الگوریتمستان
1 1 5.00 5.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 قرار بگیرد.


امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

وبگاه:

متن پیام: *

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

 


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۲۰۵ روز
تعداد بازدید:  ۹۸۹ بازدید
تعداد امتیاز:  ۱ امتیاز
میانگین امتیاز:  ۵.۰۰  از  ۵.۰۰
»  مسئله‌ی Column Addition
        بررسی مسئله‌ی Column Addition، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی آتش‌سوزی در برره
        بررسی مسئله‌ی آتش در برره، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی حداکثر مجموع
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
»  کتاب راهنمای برنامه‌نویسان رقابتی
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
»  مسئله‌ی Turn the Lights Off
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
»  مسئله‌ی Jolly Jumpers
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
»  مسئله‌ی The Trip
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی 3n+1 Problem
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی Encrypted SMS
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
»  مسئله‌ی Gholam's Simple Game
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
»  راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
»  مسئله‌ی What Base Is This
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
»  ویدئوهای آموزشی کلاس Programming Challenges
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی