المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۵

ماتریسی ‎$n\times n$‎ از اعداد حقیقی با درایه‌های ‎$a_{ij}$‎ داده شده است. می خواهیم ‎$n$‎ عدد حقیقی ‎$x_1‎, ‎x_2‎, ‎\dots‎, ‎x_n$‎ را پیدا کنیم که در نامساوی زیر صدق کنند: ‎$$\sum_{1\le i,j\le n} a_{ij}|x_i-x_j|>0$$‎ الگوریتمی با زمان اجرای ‎$O(2^n n^3)$‎ ارائه دهید که بگوید آیا چنین ‎$n$‎ عددی وجود دارند یا نه، و در صورت وجود یکی ازحالت‌های ممکن برای این ‎$n$‎ عدد را مشخص کند.


ابزار صفحه