دیوار رنگی رنگی

هوشنگ به تازگی با بازی تلفن همراه «دیوار» آشنا شده است. هدف بازی تخریب دیواری است که با آجر‌های رنگی ساخته شده است. دیوار را می‌توانیم به صورت یک جدول $n \times n$ نشان‌ دهیم که هر خانه‌اش یا خالی است و یا با یک آجر رنگی پر شده است. در ابتدای بازی تمامی خانه‌ها، پر هستند. سطرهای این دیوار از پایین به بالا و ستون‌های آن از چپ به راست با اعداد $0$ تا $n-1$ شماره گذاری شده اند. خانه‌ی واقع در تقاطع سطر $i$ و ستون $j$ را با $(i, j)$ نشان می‌دهیم. رنگ آجر واقع در خانه‌ی $(i, j)$ در ابتدا $a_{i, j}$ است.

دو آجر همسایه اند اگر و تنها اگر هم‌رنگ باشند و یک ضلع مشترک داشته باشند. یک مسیر آجری به دنباله‌ای (با طول حداقل ۱) از آجرها می‌گوییم که هر دو آجر متوالی دراین دنباله همسایه باشند. دو آجر $x$ و $y$ به هم مسیر دارند اگر و تنها اگر یک مسیر آجری وجود داشته باشد که با $x$ شروع شود و به $y$ ختم شود. یک مؤلفه آجری به مجموعه‌ای بیشین (ماکسیمال) از آجرها می‌گوییم که هر دو آجر در این مجموعه به یکدیگر مسیر داشته باشند. می‌توان دید که هر آجر عضو دقیقا یک مؤلفه آجری است.

در هر مرحله از بازی بازیکن یکی از آجرهای موجود را انتخاب می‌کند. پس از آن کل مؤلفه‌ی آجری شامل آجر انتخاب شده حذف می‌شود. سپس همه‌ی آجرهایی که زیرشان خالی است به پایین سقوط می‌کنند و روی آجرهای دیگر یا پایین دیوار قرار می‌گیرند (یعنی در این بازی جاذبه وجود دارد). بعد از آن همه‌ی ستون های خالی حذف می‌شوند و ستون های سمت راست آن‌ها به چپ می آیند (ابعاد دیوار عوض میشود). بازی تا زمانی ادامه پیدا می‌کند که همه‌ی آجرهای جدول حذف شوند. اگر در یک مرحله $x$ آجر از دیوار حذف شوند، امتیاز آن مرحله برابر با $x^3$ است. امتیاز کل بازی برابر با مجموع امتیاز تمام مراحل بازی است.

در ابتدای هر مرحله آجرها به ترتیب از خانه‌ی پایین-چپ با اعداد $0$ تا $t-1$ (که $t$ تعداد‌ آجرهاست) شماره‌گذاری می‌شوند. به این صورت که شماره‌ی یک آجر از آجر دیگری کمتر است اگر و تنها اگر شماره‌ی ستونش کوچک‌تر باشد، یا هر دو در یک ستون باشند و شماره‌ی سطر آجر اول کوچک‌تر باشد.

شماره‌ی آجر واقع در خانه‌ی $(i, j)$ برابر با $e_{i, j}$ است. یک نمونه از شماره گذاری آجرها در زیر آمده است:

هوشنگ یک المپیاد کامپیوتری است. او با روش های مخصوصی کد این بازی را به دست آورده و می‌خواهد رباتی بنویسد که با تقلب در این بازی رکورد جهانی آن را بشکند. او بعد از خواندن کد این بازی با تابع زیر مواجه شد:

‌‌BST.cpp

int rand(int x, int m)
{
    return (123*x*x + 1234*x + 12345) % m;
}

هوشنگ از شما خواسته است تا در نوشتن رباتش به او کمک کنید و به سوالات زیر پاسخ دهید.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10289$ محاسبه شده‌اند.

$4$- الف ($11$ نمره) : هوشنگ می‌داند که $n = 50$ و $a_{i, j} = i \times n + j + 1$ است. هم چنین اگر در مرحله $i$ ام (با شروع از ۱)، $t$ آجر در دیوار مانده باشد، ربات او آجر شماره‌ی $rand(i, t)$ را انتخاب می‌کند.

هوشنگ می‌خواهد تمام حرکات رباتش را زیر نظر بگیرد. به طور دقیق تر او مجموع وضعیت مراحل بازی (از جمله مرحله ی آغازین) را می‌خواهد بداند. وضعیت یک مرحله برابر است با مجموع $e_{i,j} \times c_{i,j}$ برای تمام آجرهای دیوار، که $c_{i, j}$ رنگ آجر واقع در خانه‌ی $(i, j)$ در آن مرحله است.

باقیمانده‌ی تقسیم مجموع وضعیت های مراحل بازی بر $\Delta$ چند است؟

$4$- ب ($11$ نمره) : هوشنگ می‌داند که $n = 50$ و $a_{i, j} = rand(i \times n + j, 12)$ است.

اگر در مرحله $i$ ام (با شروع از ۱)، $t$ آجر در دیوار مانده باشد، ربات او آجر شماره‌ی $rand(2500 + i, t)$ را انتخاب می‌کند.

باقیمانده‌ی تقسیم امتیاز بازی ربات بر $\Delta$ چند است؟

$4$- ج ($11$ نمره) : هوشنگ می‌داند که $n = 6$ و $a_{i, j} = rand(i \times n + j, 4)$ است.

او از شما خواسته رباتی برای او طراحی کنید که بیش‌ترین امتیاز را کسب کند. باقیمانده‌ی تقسیم این بیش‌ترین امتیاز بر $\Delta$ چند است؟

• سوال قبل
• سوال بعد