أقصى عدد من الأسئلة
Problem
كان لماكس سلسلان بطول n و t بطول m مكتوبان في دفتر ملاحظاتها ، ويتكون من الحرفين "a" ؛ وب" الأبجدية اللاتينية. علاوة على ذلك ، يعرف ماكس أن السلسلة t لها شكل “abab ...” ، أي الحرف “a” موجود في المواضع الفردية من السلسلة ، والحرف & [مدش] ؛ "ب".
فجأة ، في الصباح ، اكتشف ماكس أن شخصًا ما أفسد خيوطها. تم تغيير بعض من s إلى "؟".
دعنا نسمي تسلسل المواضع i، & thinsp؛ i & thinsp؛ + & thinsp؛ 1، & thinsp؛ ... ؛ i & thinsp؛ & le؛ & thinsp؛ n & thinsp؛ - & thinsp؛ m & thinsp؛ + & thinsp؛ 1 and t
1 & thinsp؛ = & thinsp؛ s
i ، & thinsp؛ t
2 & thinsp؛ = & thinsp؛ s
i & thinsp؛ + & thinsp؛ 1 ، & thinsp؛ ...، & thinsp؛ t
m & thinsp؛ = & thinsp؛ s
i & thinsp؛ + & thinsp؛ m & thinsp؛ - & thinsp؛ 1 .
يتم قياس جمال الأوتار على أنها الحد الأقصى لعدد التكرارات غير المتداخلة للسلسلة t فيها. ماكس يمكن أن يحل محل بعض "؟" على" أو "ب" (يمكن استبدال الأحرف في مواضع مختلفة بأحرف مختلفة). يريد ماكس إجراء استبدالات بحيث يصبح جمال الوتر s أكبر ما يمكن. من بين كل هذه الخيارات ، تريد استبدال أقل عدد ممكن من الأحرف "؟". اكتشف عدد الاستبدالات التي يتعين عليها إجراؤها.
الإدخال:
يحتوي السطر الأول على عدد صحيح واحد n (1 & thinsp؛ & le؛ & thinsp؛ n & thinsp؛ & le؛ & thinsp؛ 10 5 ) & mdash؛ طول السلسلة s.
يحتوي السطر الثاني من الإدخال على سلسلة من الطول n تتكون فقط من الأحرف "a" ؛ وب" الأبجدية اللاتينية ، وكذلك الرموز "؟".
يحتوي السطر الثالث على العدد الصحيح m (1 & thinsp؛ & le؛ & thinsp؛ m & thinsp؛ & le؛ & thinsp؛ 10 5 ) & mdash؛ طول السلسلة ر. تحتوي السلسلة t نفسها على "a" ؛ في المواضع الفردية ، و "ب" على الأعداد الزوجية.
الإخراج:
طباعة عدد صحيح واحد و [مدش] ؛ الحد الأدنى من عدد الاستبدالات التي يجب على Vasya إجراؤها لجعل جمال السلسلة أكبر قدر ممكن.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
5
bb؟ a؟
1 |
2 |
9
أب ؟؟ أب ؟؟؟
3 |
2 |
التفسيرات:
في المثال الأول ، تكون السلسلة t من الشكل "a". الخيار الأمثل الوحيد و [مدش]. استبدال كافة الأحرف "؟" إلى "أ".
في المثال الثاني ، باستخدام بديلين ، يمكنك الحصول على السلسلة النصية "aba؟ aba ؟؟". لا يمكنك الحصول على أكثر من إدخالين.