سوال ۱۲
دو دنباله‌ی ۱۰ تایی $A$ و $B$ از ارقام ۰ و ۱ داده شده‌اند. در هر حرکت می‌توانیم وضعیت ارقام $A$ را از سمت چپ تا جای دلخواهی عوض کنیم (یعنی هر رقم ۰ را به ۱ و هر رقم ۱ را به ۰ تبدیل کنیم.) اگر ۱۰۱۱۱۰۰۱۰۰ =$A$ و ۰۰۱۱۰۱۰۰۱۰ =$B$ باشد٬ حداقل چند حرکت لازم است تا $A$ به $B$ تبدیل شود؟
- ۵
- ۶
- ۱۰
- ۱۱
- نمی‌توان از $A$ به $B$ رسید.
پاسخ
گزینه (۱) درست است.
اولین رقم از سمت راست $A$ که با معادلش در $B$ متفاوت باشد را $i$ می‌نامیم. در هر مرحله٬ از اولین رقم از سمت چپ $A$ شروع کرده و تا رقم $i$ تمام ارقام را تعویض می‌کنیم که بعد از ۵ مرحله به شکل زیر به دنباله $B$ خواهیم رسید.
$A_0= \underline{101110010}0 \longrightarrow A_1= \underline{0100011}010 \longrightarrow A_2= \underline{101110}0010 \longrightarrow$
$A_3= \underline{0100}010010 \longrightarrow A_4= \underline{1}011010010 \longrightarrow A_5=0011010010=B$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
