- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک شرکت برنامه‌نویسی با یک الگو از اعداد دودویی مواجه می‌شود. این الگو به این صورت است که در بعضی از خانه‌های آن علامت سوال گذاشته شده است و در بقیه‌ی خانه‌ها ۰ یا ۱ آمده است. هدف این است که در هر کدام خانه‌هایی که در آن‌ها علامت سوال آمده است ۰ یا ۱ نوشته شوند. این شرکت از شما می‌خواهد برنامه‌ای بنویسید که تمامی اعداد ممکن از این الگو را به صورت نزولی چاپ کنید.
دقت کنید ترتیب نزولی به این معنا است که بزرگترین عدد دودویی در ابتدا بیاید و هر عدد دودویی در این ترتیب از عدد قبلی کوچک‌تر باشد.
هم‌چنین، عدد دودویی $x$ از عدد دودویی $y$ بزرگتر است اگر و تنها اگر در اولین محل اختلاف این دو عدد، $x$ شامل ۱ و $y$ شامل ۰ باشد. برای مثال اگر $x = 1100$ و $y = 1011$ باشد؛ $x$ از $y$ بزرگتر است، زیرا اولین محل اختلاف خانه‌ی دوم است که در $x$ آن خانه ۱ و در $y$ آن خانه ۰ است.
برای درک بهتر مسئله به مثال‌ها مراجعه کنید.
ورودی
ورودی این برنامه یک الگوی دودویی است که ارقام نامشخص، با علامت سوال مشخص شده‌اند. اگر طول رشته را $l$ و تعداد علامت‌سوال‌ها را $n$ در نظر بگیریم، داریم:
$$ 1 \le l \le 1000 $$$$ 1 \le n \le 10 $$
خروجی
خروجی برنامه باید تمامی حالات ممکن برای الگو را به صورت نزولی در سطر‌های مختلف نمایش دهد.
مثال
ورودی نمونه ۱
?
خروجی نمونه ۱
1
0
در این حالت جای علامت سوال هم می‌تواند یک و هم می‌تواند صفر بیاید. پس به ترتیب نزولی ابتدا ۱ و سپس ۰ می‌آید.
ورودی نمونه ۲
1?101?
خروجی نمونه ۲
111011
111010
101011
101010
دو علامت سوال داریم که هر کدام از آن‌ها می‌توانند صفر یا یک باشند، پس در کل ۴ حالت خواهیم داشت. اگر این ۴ حالت را به صورت نزولی چاپ کنیم به صورت بالا می‌شود، زیرا $111011$ بزرگترین عدد و $101010$ کوچکترین عدد است.
ارسال پاسخ برای این سؤال