المپدیا

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

ابزار کاربر

ابزار سایت


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

برش نواحی

یک جدول $n \times n$ در اختیار داریم. در ابتدا جدول از $n^2$ ناحیه تشکیل شده است ($n^2$ مربع $۱ \times ۱$). در هر مرحله می‌توانیم تمام دو ناحیه‌ی مجاور (یعنی دو ناحیه که لااقل یک پاره‌خط مشترک دارند) را از جدول انتخاب کنیم و این دو ناحیه را با هم ادغام کنیم؛ یعنی مرز مشترک بین این دو ناحیه را پاک کنیم. فرض کنید طول این مرز مشترک در مرحله‌ی $i$ام $a_i$ باشد. اگر بعد از $k$ مرحله٬ تنها یک ناحیه باقی بماند (یعنی یک مربع $n \times n$٬ اعداد $a_۱,...,a_k$ به دست می‌آیند. برای مثال٬ در شکل سمت چپ بالا اگر نواحی $D$ و $C$ را بخواهیم با هم ادغام کنیم٬ محیط مشترک بین این دو ناحیه ۳ واحد بوده و نهایتاً به شکل پایین می‌رسیم.

الف) روشی ارائه دهید که در آن هر یک از $a_i$ها ۱ یا ۲ باشد.

ب) نشان دهید کم‌ترین مقدار $\sum_{i=1}^k a_i^2$ وقتی رخ می‌دهد که هر یک از $a_i$ها ۱ یا ۲ باشد و با استفاده از این نکته جواب مسئله٬ یعنی کم‌ترین مقدار $\sum_{i=1}^k a_i^2$ را به دست آورید.


ابزار صفحه