- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شرکت ارتباطات سینا دو عدد رجیستر دارد که در هر کدام از آنها یک عدد در مبنا ۲ و با استفاده از \(n\) حافظه که هر کدام 0 و یا 1 هستند، ذخیره شده است.
میخواهیم دو عدد این رجیسترها را با یکدیگر جمع بزنیم. همانطور که در مبنای ۱۰ وقتی میخواهیم دو عدد را جمع بزنیم، در هر جایگاه یک رقم بین 0 الی 9 به جایگاه بعدی منتقل میشود، در هنگام جمع زدن دو عدد در مبنای ۲، نیز هنگاه جمع زدن دو عدد در هر جایگاه یک رقم که میتواند 0 و یا 1 باشد به جایگاه بعدی منتقل میشود. به این رقم \(carry\) میگوییم.
در این سوال دو عددی که داخل رجیسترها ذخیره شدهاند را داریم. اما در هر دوی رجیسترها بعضی
از رقمها نویز داشتهاند و نمیدانیم داخل آنها 0 نوشته شده است و یا 1. اما میدانیم حداکثر یکی از این ارقام نویز خورده برابر 1 است و بقیه آنها برابر 0 هستند.
کسی خبر رسانده است که وقتی این دو عدد را جمع میکنیم، به ازای هر جایگاهی که \(carry \) آن برابر \(1\) باشد، رجیسترها یک واحد ناراحت میشوند. برای اینکه بتوانیم بیشترین میزان ممکن رجیسترها را ناراحت کنیم سوال زیر از شما پرسیده شده است.
در بین تمام حالاتی که دو عدد ما میتوانند باشند. به این معنی که حداکثر یکی از ارقام نویز گرفته برابر 1 و بقیه برابر 0 باشند، بیشترین تعداد \(carry\) ای که در زمان جمع زدن این دو عدد برابر با 1 خواهد بود چند تا است.
ورودی
در سطر اول ورودی عدد \(n\) داده میشود که نشاندهنده تعداد ارقام دو عدد مورد نظر در مبنا دو است.
\[1 \leq n \leq 100,000\]
سپس در سطر دوم و سوم دو عدد به طول \(n\) رقم و در مبنای دو ورودی داده میشوند. هر رقم از این دو عدد با 0 و یا 1 و یا کاراکتر ؟ نمایش داده میشود. که علامت سوال نشاندهنده نویز در رقم مشخص شده است.
خروجی
در تنها خط خروجی باید یک عدد خروجی دهید که نشاندهنده بیشترین تعداد \(carry\) برابر با 1 ای است که جمع این دو رجیستر میتواند داشته باشد. دقت کنید خروجی شما باید عددی بین \(0\) و \(n\) باشد.
ورودی نمونه ۱
5
101?1
00101
خروجی نمونه ۱
3
در این حالت اگر تنها علامتسوال را برابر عدد 1 در نظر بگیریم بیشترین میزان ممکن که برابر ۳ عدد \(carry\) است را تولید میکنیم.
ورودی نمونه ۲
5
111?1
0001?
خروجی نمونه ۲
5
ورودی نمونه ۳
5
1???1
?1111
خروجی نمونه ۳
5