Processing math: 5%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۳:سوال یک

رشته‌ي نزدیک

۱۳۹۲ رشته به طول ۱۳۹۲ از حروف کوچک انگلیسی با نام‌های p1,p2,...,p1392 در اختیار داریم.

فاصله دو رشته A=a1,a2,...,an و ‌B= b_1, b_2, ..., b_n را با d(A,B) نمایش می‌دهیم و این مقدار برابر است با تعداد اندیس‌های i که a_i≠ b_i . به عنوان مثال فاصله‌ی دو رشته salam و palas برابر با ۲ است زیرا تنها در مکان‌های اول و آخر با هم تفاوت دارند.

برای رشته‌ی x به طول ۱۳۹۲ مجموع فاصله‌هایش از این ۱۳۹۲ رشته را D_x می نامیم. به رشته‌ای مانند M به طول ۱۳۹۲،نزدیک می‌گوییم اگر به ازای هر رشته x به طول ۱۳۹۲: Dm≤Dx

الف) به ازای هر سه رشته هم طول دلخواه A,B,C نشان دهید d(A,B)\le d(A,C)+ d(B,C) (۵ نمره)

ب) نشان دهید رشته‌ای مانند \pi_i از این ۱۳۹۲ رشته وجود دارد به طوری که D_m\le D_{p_i}\le 2D_m (۱۰نمره)

پاسخ

الف) کافی است توجه کنیم که اگر دو رشته A و C‌ در جایگاه i‌ ام با هم اختلاف داشته باشند حداقل یکی از دو جفت (A,B) یا (B,C) در جایگاه i‌ ام با هم اختلاف دارند. در نتیجه هر اختلافی که در d(A,C) شمرده می‌شود حداقل در یکی از d(A,B)‌ یا d(B,C) نیز شمرده می‌شود که حکم مسئله را نتیجه می‌دهد.

ب) p_j را نزدیک‌ترین رشته به رشته M در بین ۱۳۹۲ رشته در نظر می‌گیریم و D_{p_j } را محاسبه می‌کنیم:

D_{p_j}=\sum_{i=۱}^{1392} d(p_i,p_j ) ≤\sum_{i=۱}^{1392} d(p_i,M)+d(M,p_j ) =D_M+\sum_{i=۱}^{1392} d(M,p_j ) \quad\quad\quad (1)

اما با توجه به نحوه انتخاب p_jبه ازای هر i می‌دانیم d(M,p_j )≤d(M,p_i) و از این موضوع نتیجه می‌گیریم

\sum_{i=۱}^{1392} d(M,p_j ) ≤\sum_{i=۱}^{1392} d(M,p_i ) =D_M \quad \quad \quad (2)

از (1)‌ و (2)‌ خواهیم داشت D_{p_j }≤2D_M.


ابزار صفحه