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

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

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

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

بستن پنجره
امتیاز دهید:
به وبگاه

به این صفحه
بستن پنجره
وبگاه     این صفحه
مسئله‌ی بشکه‌های آب - الگوریتمستان
الگوریتمستان
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$ در زمان قابل قبولی خروجی مطلوب را تولید می‌کند.


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

نام: *  

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

وبگاه:

متن پیام: *

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

 


» محمد مسیح

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