مسئله‌ی دوستان خوب - الگوریتمستان
الگوریتمستان
1414.575.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 است.

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


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

 


» امیرمحمد

یکشنبه، ۱۳ مرداد ماه ۱۳۹۲، ساعت ۰۳:۴۹
باسمه تعالی
یک راه خوب دیگه:
برای هر دایره یک شماره سطر(مانند راه حل ارائه شده) و یک شماره ستون(اینکه در سطر خودش از سمت چپ چندمین دایره هست) در نظر میگیریم و مختصات هر دایره را با (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)در صورت امکان
این دو تا هم جزو عملیات هستن که جا انداخته بودم