Processing math: 28%

المپدیا

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

ابزار کاربر

ابزار سایت


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

واﻟﯿﺒﺎل

فرض کنید یک جدول با تعدادی عدد پر شده باشد. جمع اعداد سطر ‎i‎اٌم آن را ‎ai‎ و جمع اعداد ستون ‎i‎اٌم آن را ‎bi‎ می نامیم. دنباله کلیدی یک جدول ‎m×n‎ را به صورت زیر تعریف می‌کنیم: ‎[a1,a2,,am,b1,b2,,bn]

تمام پاسخ‌های ارائه شده در این سوال با فرض Δ=229939 محاسبه شده‌اند.

2- الف (7 نمره) : بعد از بازی خوب ایران مقابل صربستان علی کوچولو تمامی حالات پر کردن یک جدول ‎4×4‎ با ‎0‎ و 1 را به همراه دنباله کلیدی هر کدام روی کاغذ نوشته است. اگر تعداد دنباله‌های متمایز تولید شده برابر ‎M_1‎ باشد باقی‌مانده‌ی ‎M_1^4 (عدد ‎M_1‎ به توان 4)‎ بر ‎\Delta‎ چند است؟‎

پاسخ

28932

2- ب (10 نمره) : سپس علی تصمیم گرفت یک جدول‎7 \times 7‎ را با 0 و 1 پر کند حال او می‌خواهد بداند در چند جدول تمامی اعداد دنباله کلیدی برابر 3 هستند. اگر این مقدار برابر ‎M_2‎ باشد، باقی‌مانده‌ی عدد ‎M_2‎ بر ‎\Delta‎ چند است؟‎

پاسخ

187039

2- ج (13 نمره) : فرض کنید تمامی حالات پر کردن جدول ‎5 \times 5‎ با 0 و 1 و 2 که حداقل یک عدد 2 در جدول آمده باشد را بنویسیم و دنباله ی کلیدی هر کدام از آن‌ها را نیز محاسبه کنیم. اگر تعداد دنباله‌های متمایز تولید شده برابر‎M_3‎ باشد، باقی‌مانده‌ی عدد ‎M_3‎ بر ‎\Delta‎ چقدر است؟

پاسخ

172227


ابزار صفحه