لو سمحت! كيفية حل هذا السؤال؟ (ج++)

إليك سؤال مررت به أثناء ممارسة التمارين اليومية:

لدى المزارع جون عدد N من الأبقار في خط (1≥N≥3⋅10^5). لسوء الحظ، هناك مرض منتشر في كل مكان. في البداية، تبدأ بعض الأبقار بالعدوى. في كل ليلة، تنشر بقرة مصابة المرض إلى الأبقار التي على يسارها ويمينها (إن وجدت). بمجرد إصابة البقرة بالعدوى، فإنها تظل مصابة. بعد مرور بعض الوقت، يدرك المزارع جون أن المشكلة قد خرجت عن نطاق السيطرة، لذلك يقوم باختبار أبقاره لتحديد من هو المصاب بالمرض. أوجد أقل عدد ممكن من الأبقار التي يمكن أن تكون قد بدأت بالمرض.

نمط الإدخال
يحتوي السطر الأول على N، وهو عدد الأبقار التي يملكها المزارع جون.
يحتوي السطر التالي على سلسلة بت من الأحرف N مكونة من 1s و0 s فقط حيث يمثل 1 بقرة مصابة ويمثل 0 بقرة غير مصابة بعد عدد من الليالي.

تنسيق الإخراج
إخراج عدد صحيح واحد: الحد الأدنى لعدد الأبقار التي يمكن أن تكون قد بدأت بالمرض.

إدخال العينة:
5
11111
إخراج العينة:
1
لنفترض أن البقرة الوسطى هي البقرة الوحيدة التي أصيبت بالعدوى. ثم تصاب الأبقار بالترتيب التالي:

0 ليلة: 00100 (البقرة الثالثة تصاب في البداية)
ليلة واحدة: 01110 (البقرتان الثانية والرابعة مصابتان الآن)
ليلتان: 11111 (البقرة الأولى والخامسة مصابتان الآن)
3 ليال: 11111 (جميع الأبقار مصابة بالفعل، لذا لا توجد أبقار أخرى مصابة)

وبعد ليلتين أو أكثر، ستبدو الحالة النهائية للأبقار مثل المدخلات. هناك العديد من الحالات الأولية الأخرى وعدد الليالي التي كان من الممكن أن تنتج حالة الإدخال، مثل:

0 ليال: 10001
ليلة واحدة:11011
ليلتان:11111
أو:

0 ليالي:01001
ليلة واحدة:11111
أو:

0 ليالي:01000
ليلة واحدة:11100
ليلتان:11110
3 ليال:11111
تحتوي كل هذه الحالات الأولية على بقرة واحدة مصابة على الأقل.

إدخال العينة:
6
011101
إخراج العينة:
4
الحالة الأولية الوحيدة وعدد الليالي التي يمكن أن تؤدي إلى هذه الحالة النهائية هي إذا لم تمر ليالٍ وبدأت كل من الأبقار الأربع المصابة في الإدخال بالمرض.

التسجيل:

* المدخلات 3-7: N ≥1000
* المدخلات 8-12: لا توجد قيود إضافية.

كنت بحاجة لحل هذا السؤال باستخدام C++.

ما حاولت:

لقد حاولت التفكير في حل، ولكن الآن أعتقد أنني أعرف فقط كيفية القيام بعكس هذا السؤال 🙁 لا أستطيع التفكير في حل. الرجاء مساعدتي! أنا من النوع الذي يحتاج إلى حل سؤال عندما أراه أنا مجرد مبتدئ، لذا يرجى المساعدة!