المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۷

شکل روبه‌رو نشان‌دهنده‌ی تعدادی خیابان و تقاطع‌های بین آن‌هاست. خیابان‌ها در جهت فلش‌ها یک‌طرفه هستند. عرض هر خیابان هم به‌اندازه یک ماشین است؛ یعنی ماشین‌ها نمی‌توانند از یکدیگر سبقت بگیرند. هم‌چنین ماشین‌ها نمی‌توانند در محل تقاطع‌ها بایستند. درنتیجه در هرلحظه هر ماشین فقط می‌تواند در یک خیابان قرار بگیرد. می‌دانیم که یک ایستگاه عوارضی در خیابان $B$ قرار دارد و از هر ماشین که عبور می‌کند مبلغ ۱۰ تومان دریافت می‌کند. نقطه‌ی $A$ که در شکل دیده می‌شود یک پارکینگ است. ماشین‌های با شماره‌ی ۱ تا ۶ پشت سر هم قرار دارند. می‌خواهیم این ماشین‌ها را به پارکینگ $A$ منتقل کنیم. کم‌ترین مجموع مقدار عوارض پرداختی چه قدر است تا این ماشین‌ها به ترتیب شماره‌هایشان (اول ۱ بعد ۲، …) وارد پارکینگ شوند؟

  1. ۱۲۰
  2. ۱۳۰
  3. ۱۴۰
  4. ۱۵۰
  5. ۱۶۰

پاسخ

گزینه (۳) درست است.

بهترین الگوریتم برای حرکت ماشین‌ها به شکل زیر می‌باشد:

  • همه ماشین‌ها از عوارضی رد شده و ماشین‌های ۴ و ۲ در خیابان سمت راست و ماشین‌های ۵٬۶ و ۳ در خیابان سمت چپ ردیف شده و ماشین ۱ ره خروجی می‌رود که در این حالت مجموعا ۶۰ تومان عوارض پرداخت می‌شود.
  • ماشین ۴ از عوارضی رد شده و در پشت آخرین ماشین سمت چپ یعنی ماشین ۳ قرار می‌گیرد که در این حالت نیز ۱۰ تومان عوارض پرداخت می‌شود.
  • تنها ماشین موجود در سمت راست یعنی ماشین ۲ از عوارضی رد شده و وارد پارکینگ می‌شود که ۱۰ تومان عوارض پرداخت می‌شود.
  • ماشین‌های ۶ و ۵ از عوارضی رد شده و ماشین ۶ به خیابان سمت راست و ماشین ۵ به خیابان سمت چپ و به پشت ماشین ۴ منتقل می‌شوند و در این حالت مجموعا ۲۰ تومان به عوارضی پرداخت می‌شود.
  • ماشین‌های ۴٬۳ و ۵ که در خیبان سمت چپ و به همین ترتیب قرار دارند از عوارضی رد شده و به ترتیب در پارکینگ قرار می‌گیرند و بعد از آن‌ها ماشین شماره ۶ از خیابان سمت راست به عوارضی رفته و از آن‌جا به پارکینگ منتقل می‌شود. در این حالت نیز مجموع عوارض پرداخت شده برابر ۴۰ تومان می‌باشد.

باتوجه به حالت‌بندی فوق مجموع کل عوارض برابر $60+10+10+20+40$ یعنی ۱۴۰ تومان به‌دست آید.


ابزار صفحه