المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۱۷ و ۱۸

کاخ آبولف به شکل جدولی ۱۰ $×$ ۱۰ است. در هر خانه از این جدول، دو دریچه وجود دارد که بر دو گوشە‌ی مقابل از آن خانه نصب شدە اند. هر دریچه می‌تواند با چرخش ۹۰ درجە‌ای (حول گوشە‌ای که بر آن نصب شده)، از حالت افقی به عمودی یا برعکس، تغییر وضعیت بدهد. برای مثال در شکل زیر، با چرخش دریچە‌ای که به گوشە‌ی بالا چپ خانە‌ی جدول متصل است، می‌توانیم از وضعیت سمت چپ به وضعیت سمت راست برسیم: در صورتی که دو خانە‌ی مجاور (دارای ضلع مشترک) دو دریچە‌ی کاملا به هم چسبیده (و با نصب در گوشە‌ی یکسان) داشته باشند، یک فرد می‌تواند از یکی از این خانە‌ها به دیگری برود. برای مثال در شکل زیر، در حالت سمت چپ امکان جابە‌جایی بین دو خانه وجود دارد، اما در دو حالت دیگر خیر:

سوال ۱۷

در شکل زیر، آبولف در خانە‌ی پایین چپ جدول قرار دارد و می‌خواهد به خانە‌ی بالا راست برود. او هر زمان که بخواهد، می‌تواند یکی از دریچە‌های یکی از خانە‌ها را انتخاب کند و به مأمور آن دریچه دستور دهد که آن را بچرخاند (لزومی ندارد دریچە‌ی انتخاب شده در خانە‌ی فعلی آبولف باشد). آبولف حداقل چند دستور باید بدهد تا بتواند به مقصد برسد؟

  1. ۱۹
  2. ۱۶
  3. ۱۸
  4. ۱۷
  5. ۲۰

سوال ۱۸

در بازسازی کاخ، آبولف می‌خواهد تمام دریچە‌ها را بردارد و برای خانە‌ها از نو دریچه بگذارد (هم‌چنان برای هر خانه، باید دو دریچه در دو گوشە‌ی مقابل، هر یک به صورت افقی یا عمودی، قرار داده شود). او به چند طریق می‌تواند این کار را انجام دهد، طوری که از هر خانه بتوان با تعدادی گام به هر خانە‌ی دیگر رسید (می‌توان دریچە‌ها را حین پیمودن مسیر هم چرخاند)؟

  1. $2^{201}$
  2. $2^{101}$
  3. $2^{200}$
  4. $2^{300}$
  5. $3 \times 2^{300}$

ابزار صفحه