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

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

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مسئله‌ی دوستان خوب - الگوریتمستان
الگوریتمستان
14 1 4.57 5.00
  »  

        بررسی مسئله‌ی دوستان خوب، از سوالات مسابقات برنامه‌نویسی ACM
آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی دوستان خوب
       »  مسئله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسئله

مسئله

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

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

  

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

  

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

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

  

ورودی برنامه

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

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

  

1   3

2   6

23   9

0   0

  

خروجی برنامه

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

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

  

1

2

4

  

منبع: مسابقه‌ی ACM منطقه‌ای آسیا 2009 - سایت تهران - مسئله‌ی Best Friends

  

حل مسئله

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

سوای مختصات عددی مشخص شده برای دایره‌ها، هر دایره را می‌توان با سه ویژگی شماره‌ی سطر، شماره‌ی قطر اصلی و شماره‌ی قطر فرعی مشخص کرد:

  

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

  

اگر دو دایره در یک سطر یا یک قطر اصلی یا یک قطر فرعی قرار داشته باشند، حرکت فقط روی سطر یا قطر اصلی یا قطر فرعی صورت گرفته و محاسبه‌ی حداقل گام حرکت بسیار آسان است. اما اگر اینگونه نباشد، حرکت به سمت دایره‌ی مبدأ فقط به دو نوع حرکت از سه نوع حرکت سطری و قطری نیاز دارد (چرا؟).

  

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

  

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

به عنوان مثال، اگر دو دوست در دایره‌های 5 و 19 قرار داشته باشند، اختلاف سطری و قطر اصلی و قطر فرعی آنها به ترتیب اعداد 3، 1 و 2 است. بنابراین مسیر حرکت قطر اصلی و قطر فرعی با طول گام‌های 3 انتخاب می‌شود که کوتاهترین راه ممکن است.

  

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

  

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

تنها نکته‌ی باقیمانده نحوه‌ی محاسبه‌ی شماره‌ی سطر و قطرهای هر دایره است. بر اساس ساختار شماره‌گذاری دایره‌ها در شکل فوق، اعداد سطر شماره‌ی R بین اعداد $ 1 + \frac{R \times ( R - 1 )}{2} $ و $ \frac{R \times ( R + 1 )}{2} $ است. پس می‌توان با یک حلقه‌ی تکرار، عدد R را به نحوی که n بین این دو عدد قرار بگیرد پیدا کرد. البته این نامساوی را می‌توان با استفاده از روابط ریاضی حل کرده و به روش مستقیم مقدار R را از روی n محاسبه کرد. علاقه‌مندان می‌توانند آن رابطه را نبز به دست بیاورند.

شماره‌ی قطر اصلی و فرعی نیز به ترتیب از جمع عدد یک با تفاضل عدد دایره (همان n) و بزرگترین شماره‌ی موجود در سطر و تفاضل عدد دایره از کوچکترین شماره‌ی موجود در سطر به دست می‌آید. مثلا عدد 19 در سطر 6 قرار دارد. چرا که رابطه‌ی 16 ≤ 19 ≤ 21 برقرار است. شماره‌ی قطر اصلی برابر 1 + 19 - 21 = 3 و شماره‌ی قطر فرعی برابر 1 + 16 - 19 = 4 است.

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


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

نام: *  

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

وبگاه:

متن پیام: *

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

 


• امیرمحمد
یکشنبه، ۱۳ مرداد ماه ۱۳۹۲، ساعت ۰۳:۴۹

باسمه تعالی

یک راه خوب دیگه:

برای هر دایره یک شماره سطر(مانند راه حل ارائه شده) و یک شماره ستون(اینکه در سطر خودش از سمت چپ چندمین دایره هست) در نظر میگیریم و مختصات هر دایره را با (x,y) نشان میدهیم.

خوب فرض کنیم می خواهیم از خانه(a,b) به(c,d) برویم

عملیات های زیر ثابل انجام است

(x,y)   به (x,y+1)در صورت امکان

(x,y)   به (x,y-1)در صورت امکان

(x,y)   به (x+1,y+1)در صورت امکان

(x,y)   به (x-1,y-1)در صورت امکان

پس اختلاف ردیف دو دوست و اختلاف ستون دو دوست رو پیدا می کنیم و ماکسیمم این دو عدد جواب مسئله هست.


• امیرمحمد
یکشنبه، ۱۳ مرداد ماه ۱۳۹۲، ساعت ۰۴:۳۱

x,y)   به (x+1,y)در صورت امکان

x,y)   به (x-1,y)در صورت امکان

این دو تا هم جزو عملیات هستن که جا انداخته بودم


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

   

   

پیوند کوتاه: عمر نوشته:  ۲۰۸۵ روز
تعداد بازدید:  ۱۲۰۶۵ بازدید
تعداد امتیاز:  ۱۴ امتیاز
میانگین امتیاز:  ۴.۵۷  از  ۵.۰۰
»  مسئله‌ی 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
»  دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
»  مسئله‌ی 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، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی