المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۶:سوال ۱۴

سوال ۱۴

رشته‌ای از حروف الفبای انگلیسی داده شده است. در هر مرحله٬ می‌توان یکی از دو عمل زیر را انجام داد:

  • جای دو حرف را در رشته به دل‌خواه تغییر داد؛
  • دو حرف الفبا را (مانند $c_1$ و $c_2$) انتخاب کرده٬ و سپس تمام حروف $c_1$ در رشته‌‌ی موردنظر را به $c_2$ تغییر داده و بالعکس.

دو نمونه در این‌جا ذکر می‌کنیم: با انجام عمل اول می‌توان از SALAM به رشته‌‌ی SALMA رسید. با انجام عمل دوم می‌توان از SALAM به ASLSM و BALAM رسید. در کدام‌یک از گزینه‌های زیر می‌توان با انجام تعدادی از حرکات فوق‌الذکر٬ از رشته‌ی اول به رشته‌ی دوم رسید؟

  1. MASWQ $\leftarrow$ SALAM
  2. ZYXXWWQQP $\leftarrow$ ABCDDDEFF
  3. UDHQOYQOYOOY $\leftarrow$ HHIJJIJJKHOL
  4. UOOQWERPPP $\leftarrow$ IDKLMLJMJM
  5. QWKIOPX $\leftarrow$ IDJKER

پاسخ

گزینه (۳) درست است.

اگر در رشته‌ای حرفی وجود داشته باشد که $n$بار تکرار شده باشد٬ آن‌گاه در رشته نهایی نیز باید حرفی وجود داشته باشد که $n$بار تکرار شده باشد چون هیچ یک از دو عمل یاد شده تکرار حرفی در یک رشته به‌تعداد $n$بار را تغییر نمی‌دهد. همچنین شرط لازم برای آن‌که رشته‌ای بتواند از روی رشته دیگر به‌وجود آید آن است که تعداد حروف آن‌ها یکسان باشد. بنابراین اگر تعداد حروف تکراری دو رشته را به صورت دنباله‌ای مثلا نزولی بنویسیم باید دنباله‌های متناظر به دو رشته کاملا یکسان باشد. دنباله‌های متناظر به کلمات داده شده در گزینه‌ها به شکل زیر می‌باشند:

$\left\{ \begin{array}{l l}(4,3,2,1,1,1)\\(4,3,2,1,1,1)\end{array} \right.$=(ج $\left\{ \begin{array}{l l}(3,2,1,1,1,1)\\(2,2,2,1,1,1)\end{array} \right.$=(ب $\left\{ \begin{array}{l l}(1,1,1,1,1,1)\\(1,1,1,1,1,1,1)\end{array} \right.$=(الف

$\left\{ \begin{array}{l l}(3,2,2,1,1,1)\\(3,2,1,1,1,1,1)\end{array} \right.$=(ه $\left\{ \begin{array}{l l}(2,1,1,1)\\(1,1,1,1,1)\end{array} \right.$=(د


ابزار صفحه