المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۰:سوال ۳۶

سوال ۳۶

نقشه‌ی شهرهای یک کشور در شکل روبه‌رو داده شده است. در این شکل هر دایره متناظر یک شهر و پاره‌خط‌های بین آن‌ها متناطر جاده‌های بین این شهرهاست. هر شهر دارای یک مخزن بنزین است. همه‌ی این مخزن‌ها در ابتدا تهی هستند به‌جز یک شهر دل‌خواه به‌نام شهر مبدأ که مخزن آن ‎۳۰‎ لیتر بنزین دارد.

در شهر مبدأ ماشینی قرار دارد که می‌تواند حداکثر ‎۳‎ لیتر بنزین حمل کند، و برای رفتن از هر شهر به شهر مجاور یک لیتر از این بنزین را مصرف می‌کند. ماشین می‌تواند مقداری از بنزینی را که حمل می‌کند در مخزن بنزین یک شهر خالی کند، یا از مخزن بنزین آن شهر مقداری بنزین برای حمل بردارد. آیا می‌توان با انتخاب شهر مبدأ مناسب ‎۳۰‎ لیتر بنزین موجود در مخزن آن شهر را به‌وسیله‌ی ماشین طوری بین شهرها پخش کرد که پس از بازگشت ماشین به شهر مبدأ، در مخزن بنزین هر شهر حداقل یک لیتر بنزین مانده باشد؟

پاسخ

برای انتقال یک لیتر بنزین به مخزن شهر مجاور دو لیتر بنزین هدر می‌رود ( یک لیتر برای رفت و یک لیتر برای برگشت). برای انتقال یک لیتر بنزین به مخزن شهری که با شهر مبدا دو واحد فاصله دارد ۸ لیتر بنزین هدر می‌رود٬ زیرا اگر شهر مبدا در شکل مقابل شهر $A$ و شهر مقصد شهر $C$ باشد٬ فاصله بین شهر $A$ و $B$ سه بار و فاصله‌ی بین $B$ تا $C$ یک بار به صورت رفت و برگشت طی می‌شود تا از شهر $A$ به شهر $C$ یک لیتر بنزین منتقل شود.

به همین ترتیب ثابت می‌شود که برای انتقال یک لیتر بنزین به مخزن شهری که با شهر مبدا سه واحد فاصله دارد ۲۶ لیتر بنزین هدر می‌رود. با این توضیحات معلوم می‌شودکه بهترین شهر برای مبدا شهر $A$ می‌باشد که در این صورت برای انتقال یک لیتر بنزین به شهر‌های $F، E ، D ، C ، B$ و $G$ به ترتیب ۸٬۸٬۸٬۲٬۲ و ۲ لیتر بنزین هدر می‌رود که با بنزین‌های موجود در مخازن که باید حداقل یک لیتر در هر مخزن باشد مجموعا ۳۷ لیتر می‌شود که از ۳۰ لیتر بیش‌تر است.


ابزار صفحه