بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی بشکه‌های آب - الگوریتمستان
الگوریتمستان
315.005.00
  »  

       

بررسی مسأله‌ی بشکه‌های آب (Water Barrels)، از سوالات مسابقات برنامه‌نویسی بیان

آنچه در این نوشته می‌خوانید:
   •  مسأله‌ی بشکه‌های آب
       »  مسأله
       »  ورودی مسأله
       »  خروجی مسأله
       »  حل مسأله

مسأله

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

    $n$ بشکه‌ی آب با تعدادی لوله به هم وصل شده‌اند. هر بشکه استوانه‌ای عمودی با سطح مقطع یک متر مربع و ارتفاع نامحدود است که با عدد یکتا بین 1 تا $n$ شماره‌گذاری شده است. $i$-امین لوله بشکه‌ی $ x_i $ و $y_i$ را به هم متصل می‌کند. یک سر این لوله در ارتفاع $h_i$ متر به بشکه‌ی $ x_i $ متصل است و سر دیگر آن در همان ارتفاع به بشکه‌ی $y_i$ متصل است. در زمان صفر بشکه‌ها خالی هستند و یک جریان آب به صورت پیوسته با سرعت یک متر مکعب بر ساعت در بشکه‌ی شماره‌ی یک می‌ریزد. اگر آب بشکه‌ای به ارتفاع لوله‌ای برسد، آب در لوله جریان پیدا می‌کند و می‌تواند وارد بشکه‌ی دیگر شود. فرض کنید قطر لوله‌ها ناچیز است و سرعت آب در لوله‌ها بسیار زیاد است.

    شما باید برای هر بشکه اولین زمانی را حساب کنید که آب وارد آن می‌شود.

      

ورودی مسأله

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

در سطر اول ورودی عدد صحیح $T$، تعداد تست‌ها آمده است. پیش از هر تست، یک سطر خالی آمده است. برای هر تست در یک سطر ورودی اعداد $n$، نشان‌دهنده‌ی تعداد بشکه‌ها و $m$ نشان‌دهنده‌ی تعداد لوله‌ها را بخوانید. سپس در $m$ سطر بعدی در هر سطر اعداد $x_i$، $y_i$ و $h_i$ آمده است که به ترتیب نشان‌دهنده‌ی بشکه‌ی دو سر لوله $(x_i \neq y_i)$ و ارتفاع نقطه‌ی اتصال هر انتهای آن است. می‌دانیم برای هر بشکه زمانی وجود دارد که آب وارد آن بشکه می‌شود.

    متغیرها به صورت $ 1 \leq T \leq 100 $ ، $ 1 \leq n \leq 1000 $ ، $ n - 1 \leq m \leq 1000 $ و $ 1 \leq h_i \leq 10^6 $ محدود بوده و $h_i$-ها متمایز از یکدیگر هستند.

  

3

  

2   1

1   2   10

  

3   2

1   2   10

2   3   20

  

3   3

1   2   10

2   3   20

1   3   15

  

خروجی مسأله

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

به ازای هر تست، ابتدا یک سطر شامل ":Case #x" بنویسید که در آن x نشان‌دهنده‌ی شماره‌ی تست است، با شروع از عدد 1. در سطر بعدی $n$ عدد را با فاصله از هم چاپ کنید. $i$-امین عدد زمانی است که آب برای اولین بار وارد بشکه‌ی $i$ می‌شود.

  

Case #1:

0   10

Case #2:

0   10   40

Case #3:

0   10   30

  

    منبع: مرحله‌ی انتخابی مسابقات برنامه‌نویسی بیان 1393، مسأله‌ی بشکه‌های آب (Water Barrels)

      

حل مسأله

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

در حالت کلی روند جریان آب و پر شدن بشکه‌ها بر اساس قوانین فیزیکی بوده و راهکار حل مسأله شبیه‌سازی روند به صورت گام به گام با در نظر گرفتن این قوانین است. یک شبیه‌سازی می‌تواند به صورت ساعت به ساعت (تغییر به ازای ورود هر متر مکعب آب) باشد که در هر تکرار سطح آب بشکه‌ها مشخص شده و هر گام بر اساس گام قبلی محاسبه می‌گردد. اما چنین راهکاری چه از نظر زمان پیاده‌سازی و چه از نظر زمان اجرا مقرون به صرفه نیست. به ویژه آنکه در حل مسأله نیاز به آگاهی از سطح آب بشکه‌ها در زمان‌های مختلف نداریم و تنها باید زمان شروع پر شدن بشکه‌ها مشخص گردد. یک شبیه‌سازی دیگر می‌تواند بر اساس لحظه‌ی رسیدن سطح آب یک بشکه به یک لوله (مستقل از میزان زمان مورد نیاز) باشد. در این حالت حداکثر $m$ گام محاسباتی برای رسیدن به جواب نیاز است. در ادامه منظور از بشکه‌های فعال بشکه‌هایی هستند که جریان آب به آنها رسیده است. همچنین منظور از لوله‌ی فعال لوله‌هایی هستند که آب در آنها جریان دارد. بدیهی است که در ابتدای کار تمامی بشکه‌ها و لوله‌ها غیرفعال هستند و با شروع جریان آب بشکه‌ی شماره‌ی یک به بشکه‌ی فعال تبدیل می‌شود.

    مسأله را می‌توان به صورت گراف وزن‌دار بدون جهتی مدل کرد که گره‌های آن نماینده‌ی بشکه‌ها و یال‌های آن همان لوله‌های بین بشکه‌ها هستند. در این گراف وزن هر یال برابر ارتفاع لوله‌ی معادل آن است. برای حل مسأله باید پیمایشی از گراف ردیابی شود که از گره شماره‌ی یک (یا همان بشکه‌ی شماره‌ی یک) شروع شده و تمامی گره‌ها به مرور زمان بازدید می‌شوند. خروجی مراحل چنین پیمایشی زیرگراف همبندی است که رفته رفته گسترده‌تر می‌شود.

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

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

     با توجه به توضیحات ارائه شده اگر گراف $G=(V,E) $ را معادل شبکه‌ی بشکه‌ها، $W$ را مجموعه‌ی گره‌های معادل بشکه‌های فعال، $H_i$ را ارتفاع سطح آب در بشکه‌ی $v_i$ و $t_i$ را زمان ورود آب به بشکه‌ی $v_i$ در نظر بگیریم، الگوریتم حل مسأله به این ترتیب خواهد بود:

    0- گره $v_1$ را به $W$ اضافه کن و مقدار $t$ (زمان سپری شده) را برابر صفر قرار بده.

    1- مراحل 2 تا 4 را تا زمانی که $ V-W $ تهی نیست تکرار کن.

    2- یال $e_s$ با کمترین وزن را که گره $ v_s \in V - W $ را به گرهی از $W$ متصل می‌کند انتخاب و $ v_s $ را به $W$ اضافه کن.

    3- به ازای هر $v_i \in W $ اگر رابطه‌ی $ H_i < \vert e_s \vert $ برقرار باشد (ارتفاع سطح آب بشکه‌‌ی فعال i از ارتفاع لوله‌ی $ e_s $ کمتر باشد) مقدار $ \vert e_s \vert - H_i $ (زمان لازم برای بالا آمدن سطح آب تا ارتفاع لوله‌ی $e_s$) را به $ t $ اضافه کرده و $H_i$ را برابر $ \vert e_s \vert $ قرار بده.

    4- مقدار $ t $ را (به عنوان زمان سپری شده تا شروع جاری شدن آب در بشکه‌ی $v_s$) در $ t_s $ قرار بده.

    در شروع اجرای این الگوریتم مجموعه‌ی $ W $ تهی بوده و مقادیر $ H_i $ و $ t_i $ برای هر بشکه صفر هستند. در طی هر تکرار بند 2 بشکه‌ی بعدی انتخاب شده (مشابه الگوریتم پریم) و با تکرارهای بند 3 مقدار $t$ به عنوان زمان جاری بودن آب پیش از رسیدن به این بشکه و ارتفاع جدید آب در بشکه‌های فعال قبلی به روز رسانی می‌شوند. در انتهای اجرای الگوریتم $ t_i $-ها پاسخ مسأله هستند.

    پیاده‌‌سازی ساده‌ی این الگوریتم از مرتبه‌ی $O(n^2m)$ است (چرا؟) که با توجه به محدودیت‌های مقادیر $n$ و $m$ در زمان قابل قبولی خروجی مطلوب را تولید می‌کند.


این نوشته آخرین بار در تاریخ سه‌شنبه، ۸ دی ماه ۱۳۹۴ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 397
        نبرد هوش مصنوعی شریف ۹۵
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 396
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 395
        مسابقه برنامه‌نویسی دانشگاه شیخ بهایی
        برگزاری مجدد مسابقه‌ی برنامه‌نویسی ACM
        مسابقه‌ی برنامه‌نویسی آنلاین 15 Quera
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 394
        مسابقه‌ی تمرینی المپیاد کامپیوتر هندوستان
        مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 17
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

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

 


» محمد مسیح

دوشنبه، ۱۴ تیر ماه ۱۳۹۵، ساعت ۰۱:۴۰
با سلام
لطفا نحوه حل سوال برج ها از سوالات مرحله دوم سومین دوره مسابقات برنامه نویسی بیان را در سایت قرار دهید