المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱

تعداد ‎$n$‎ جعبه که در هر کدام یک مهره قرار داده‌شده است داریم. در یک ماتریس ‎$n \times n$‎ فاصله دو‌به‌دوی جعبه‌ها آمده است، یعنی در درایه ‎$ij$‎ ماتریس فاصله جعبه ‎$i$‎ از ‎$j$‎ داده شده است. در هر لحظه هر مهره از جعبه خود به جعبه‌ای می‌رود که کمترین فاصله را دارد. در صورت یکتا نبودن این جعبه به یکی از جعبه‌ها با کمترین فاصله به دلخواه ما می‌تواند برود. الگوریتمی از ‎$O(n^2) $‎ ارائه دهید که مشخص کند آیا زمانی وجود دارد که همه‌ی مهره‌ها در یک جعبه قرار بگیرند یا خیر.‎


ابزار صفحه