المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۸:الگوریتم ها:سوال ۱۰

نسبتاً قشنگ

‎$n$‎ عدد دودویی متمایزِ ‎$k$‎ بیتی با نام‌های ‎$x_1, \ldots, x_n$‎ به شما داده شده است. تعداد زوج‌مرتب‌هایی به شکل ‎$(x_i,x_j)$‎ از این ‎$n$‎ عدد به طوری که ‎$x_i$‎ و ‎$x_j$‎ دقیقاً در دو بیت متفاوت باشند چند تاست؟ الگوریتمی با زمان اجرای ‎$O(nk^2)$ ‎ ارائه دهید.


ابزار صفحه