المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۶:الگوریتم ها:سوال ۴

کادوی پیمان

یک جدول $n \times m (m \geq 10)$ تشکیل شده از اعداد صحیح در اختیار داریم. می‌خواهیم برای تولد پیمان تعدادی از سطر‌های این جدول را انتخاب کنیم و به او کادو بدهیم. پیمان به عدد $x$ خیلی علاقه دارد. به همین دلیل می‌خواهد به ازای هر دو سطری که در کادوی او وجود دارد هیچ ستونی نباشد که اختلاف دو عدد نوشته شده در تقاطع این ستون و این دو سطر بیش از $x$ باشد.

الف) الگوریتمی از $O(m \times n^{m + 1})$ ارائه کنید که بیش‌ترین تعداد سطری که می‌توان به پیمان کادو داد را حساب کند.

ب) الگوریتمی از $O(m \times n^{m})$ ارائه کنید که بیش‌ترین تعداد سطری که می‌توان به پیمان کادو داد را حساب کند.


ابزار صفحه