المپدیا

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

ابزار کاربر

ابزار سایت


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

تفاوت‌ها

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

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

سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:سوال_یک [2018/04/12 13:37]
مهدی بهروزی خواه
سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۷:سوال_یک [2018/04/12 13:41] (فعلی)
مهدی بهروزی خواه
خط 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$ در تقسیم بر ۳ را به ترتیب $a_r$، $b_r$ و $c_r$ در نظر بگیرید. ثابت کنید اگر دست کم دو تا از سه عدد $a_r$، $b_r$ و $c_r$ برابر باشند، می‌توانیم با تعدادی مرحله تمام حروف رشته را برابر کنیم.

ابزار صفحه