المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۱۶:سوال هشت

آنتونیو

کشور آنتونیو مقررات عجیبی برای خیابان‌کشی دارد. خیابان‌های این کشور باید مستقیم باشند و دو طرف هر خیابان پیاده‌رو داشته باشد. هر خیابان باید از دو طرف از شهر بیرون برود. هم‌چنین در شهرهای این کشور فقط چهارراه وجود دارد٬ یعنی هر تقاطعی محل برخورد تنها دو خیابان است.

مردم پیاده فقط مستقیم بر روی پیاده‌رو حرکت می‌کنند مگر هنگامی که به چهار‌راه برسند٬ که در آن صورت دقیقاً از خط‌کشی عابر پیاده‌ی یکی از خیابان‌های آن چهارراه عبور می‌کنند و در همان جهت عبور به راه خود ادامه می‌دهند.

قرار است نقشه‌ی خیابان‌های یک شهر و محل خانه‌ی شهردار (در کنار یک خیابان) را طوری طراحی کنیم که اگر شهردار برای پیاده‌روی از خانه‌اش بیرون بیاید و مطابق مقررات حرکت کند بتواند به خانه‌اش برگردد.

برای این طراحی حالت‌های زیر را در نظر بگیرید:

  • خیابان‌ها فقط افقی و عمودی باشند.
  • خیابان‌ها می‌توانند در هر راستایی باشند.

در هر حالت فوق تعیین کنید که آیا می‌توان چنین شهری را طراحی کرد یا خیر. در صورت مثبت بودن جواب مثالی بزنید که در آن خانه‌ی شهردار و مسیر حرکت او مشخص شده باشد. برای جواب منفی٬ ادعای خود را ثابت کنید.


ابزار صفحه