المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۳۱:تئوری نهایی دوم:سوال ۲

سوال ۲

منظور از یک زیر جدول در یک جدول، جدولی است که از خانه های واقع در تقاطع تعدادی سطر متوالی و تعدادی ستون متوالی از جدول ساخته می شود. در ورودی، جدولی $n×n$ با اعداد متمایز به شما داده می شود. هدف، یافتن عددی در جدول است که در بیش ترین تعداد زیرجدول، عدد بیشینه باشد. الگوریتمی از $O(n^3)$ برای این کار ارائه دهید.

نکته: در صورتی که نتوانستید سوال را به صورت کامل حل کنید، می توانید با ارائه ی الگوریتم از $O(n^{3.99})$ تا ۵۰ امتیاز یا با ارائه ی الگوریتم از $O(n^4)$ تا ۱۵ امتیاز بگیرید.


ابزار صفحه