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

»    محاسبه‌ی دترمینان ماتریس

»    اشاره‌گرها در زبان ++C

»    حلقه‌های تکرار در ++C

»    معمای هشت وزیر

»    الگوریتم جستجوی اول سطح (BFS)

»    مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 406

»    درخت جستجوی دودویی

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی دوستان خوب - الگوریتمستان
الگوریتمستان
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 است.

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


نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسأله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب Art of Programming Contest
        بررسی مسأله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی
        بررسی مسأله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
        معرفی کتاب Introduction to Algorithms: A Creative Approach
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        بررسی مسأله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

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

 


» امیرمحمد

یکشنبه، ۱۳ مرداد ماه ۱۳۹۲، ساعت ۰۴:۳۱
x,y)   به (x+1,y)در صورت امکان
x,y)   به (x-1,y)در صورت امکان
این دو تا هم جزو عملیات هستن که جا انداخته بودم

» امیرمحمد

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

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