Processing math: 37%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۵

ماتریسی ‎n×n‎ از اعداد حقیقی با درایه‌های ‎aij‎ داده شده است. می خواهیم ‎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‎ عدد را مشخص کند.


ابزار صفحه