المپدیا

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

ابزار کاربر

ابزار سایت


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

تفاوت‌ها

تفاوت دو نسخه‌ی متفاوت از صفحه را مشاهده می‌کنید.

پیوند به صفحه‌ی تفاوت‌ها

سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۲۷:سوال_یک [2018/04/12 13:37]
مهدی بهروزی خواه
سوالات_المپیاد:مرحله_ی_دوم:دوره_ی_۲۷:سوال_یک [2020/07/10 09:00] (فعلی)
امیر محمد ایمانی
خط 1: خط 1:
 ====== رشته (۲۵ نمره) ====== ====== رشته (۲۵ نمره) ======
  
-یک رشته‌ی 𝑛 رقمی از حروف $A$، $B$ و $C$ داریم. در هر مرحله می‌توانیم دو حرف __متوالی__ و __متفاوت__ از رشته در نظر بگیریم و آن‌ها را با حرف سوم جایگزین کنیم. منظور از حرف سوم، حرفی از مجموعه‌ی {$A$, $B$, $C$} است که در میان دو حرف گفته شده نیامده است. برای مثال می‌توانیم با تغییر حروف چهارم و پنجم (از سمت چپ) رشته‌ی $ABCBAA$ آن را به $ABCCCA$ تبدیل کنیم. فرض کنید تعداد حروف $A$، $B$ و $C$ در رشته‌ی گفته شده به ترتیب $a$، $b$ و $c$ باشد. باقیمانده‌ی $a$، $b$ و $c$ در تقسیم بر ۳ را به ترتیب $a_r$، $b_r$ و $c_r$ در نظر بگیرید. ثابت کنید اگر دست کم دو تا از سه عدد $a_r$، $b_r$ و $c_r$ برابر باشند، می‌توانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم.+ 
 +یک رشته‌ی 𝑛 رقمی از حروف $A$، $B$ و $C$ داریم. در هر مرحله می‌توانیم دو حرف __متوالی__ و __متفاوت__ از رشته در نظر بگیریم و آن‌ها را با حرف سوم جایگزین کنیم. منظور از حرف سوم، حرفی از مجموعه‌ی {$A$, $B$, $C$} است که در میان دو حرف گفته شده نیامده است. برای مثال می‌توانیم با تغییر حروف چهارم و پنجم (از سمت چپ) رشته‌ی $ABCBAA$ آن را به $ABCCCA$ تبدیل کنیم. فرض کنید تعداد حروف $A$، $B$ و $C$ در رشته‌ی گفته شده به ترتیب $a$، $b$ و $c$ باشد. باقیمانده‌ی $a$، $b$ و $c$ در تقسیم بر ۳ را به ترتیب $r_a$، $r_b$ و $r_c$ در نظر بگیرید. ثابت کنید اگر دست کم دو تا از سه عدد $a_r$، $b_r$ و $c_r$ برابر باشند، می‌توانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم.
 <​پاسخ>​ <​پاسخ>​
 +
 </​پاسخ>​ </​پاسخ>​
   * [[سوال دو|سوال بعد]]   * [[سوال دو|سوال بعد]]
  

ابزار صفحه