المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۴:سوال ۲۲

سوال ۲۲

جدولی ۱۳۹۲ × ۱۳۹۲ داریم. خانه‌های این جدول را به ترتیب با اعداد ۰ تا $1392^{2}-1$ به ترتیب سطری از بالا به پایین و سپس ستونی از چپ به راست شماره‌گذاری می‌کنیم. به این ترتیب خانه‌های سطر iام با اعداد $1392 \times i$ تا $1392 \times (i+1) - 1$ از چپ به راست شماره‌گذاری شده‌اند. دو خانه از جدول را مجاور می‌نامیم در صورتی که در یک ضلع اشتراک داشته باشند و آن ضلع توسط هیچ‌کدام از آن دو خانه بسته نشده باشد. طریقه‌ی بسته‌ شدن اضلاع جدول این‌گونه است که عدد نوشته شده در خانه را به صورت دودویی می‌نویسیم. در صورتی که این عدد کمتر از چهار رقم داشت با گذاشتن ۰ در پشت عدد، آن را چهار رقمی می‌کنیم. حال یک بودن هر کدام از چهار رقم اول این عدد باعث بسته شدن ضلع متناظرش می‌شود. ارقام اول تا چهارم به ترتیب با ضلع‌های بالا، راست، پایین و چپ آن خانه متناظرند. (رقم اول کم ارزش‌ترین رقم در نمایش دودویی است). یک حرکت مجاز را رفتن از خانه‌ای به یکی از خانه‌های مجاورش تعریف می‌کنیم. حال در جدول ساخته‌شده به یک مجموعه از خانه‌ها «همبند» می‌گوییم اگر هر دو ‌خانه با انجام تعدادی حرکت مجاز از یک‌دیگر قابل دسترسی باشند. اندازه‌ی بزرگ‌ترین مجموعه‌ی همبند این جدول را محاسبه کنید.

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

راهنمایی

وضعیت خانه‌های سطر اول و خانه‌های ستون اول را بررسی کنید. وضعیت این خانه‌ها را با وضعیت خانه‌های سطر دوم و خانه‌های ستون دوم مقایسه کنید.

راهنمایی

با توجه به راهنمایی قبل، آیا الگویی در وضعیت خانه‌های هم‌سطر و یا هم‌ستون وجود دارد؟ با توجه به این الگو ابعاد مسئله را کوچک کنید به طوری که مجموعه‌های هم‌بند جدول کوچک‌تر نمونه‌ای از مجموعه‌های هم‌بند جدول اصلی باشد.

پاسخ

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

با توجه به این‌که ۱۳۹۲ بر ۱۶ بخش‌پذیر است، تمامی اعضای یک ستون به یک صورت ضلع‌های مجاورشان را می‌بندند. همچنین الگوی جدول در هر ۱۶ ستون تکرار می‌شود. بنابراین کافی است تنها ۱۶ ستون اول را بررسی کنیم.


ابزار صفحه