مسئله‌ی بشکه‌های آب

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

مسئله

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

ادامه ...

مسئله‌ی تاریخچه‌ی جدول

[برو به فهرست نوشته‌ها]
        بررسی مسئله‌ی تاریخچه‌ی جدول (Grid History)، از سوالات مسابقات برنامه‌نویسی بیان

مسئله

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

ادامه ...