कृपया! इस प्रश्न को कैसे हल करें? (सी++)

यहां एक प्रश्न है जिसका दैनिक अभ्यास करते समय मैंने सामना किया:

किसान जॉन के पास एक पंक्ति में N गायें हैं (1≤N≤3⋅10^5)। दुर्भाग्य से, चारों ओर एक बीमारी फैल रही है। प्रारंभ में, कुछ गायें संक्रमित होने लगती हैं। हर रात, एक संक्रमित गाय बायीं और दायीं ओर (यदि मौजूद हो) गायों में बीमारी फैलाती है। एक बार जब गाय संक्रमित हो जाती है, तो वह संक्रमित ही रहती है। कुछ रातों के बाद, किसान जॉन को एहसास हुआ कि समस्या नियंत्रण से बाहर हो गई है, इसलिए वह यह निर्धारित करने के लिए अपनी गायों का परीक्षण करता है कि बीमारी किसे है। गायों की न्यूनतम संख्या ज्ञात कीजिए जिनकी बीमारी की शुरुआत हो सकती है।

इनपुट प्रारूप
पहली पंक्ति में N शामिल है, किसान जॉन के पास गायों की संख्या।
अगली पंक्ति में केवल 1s और 0 s का N वर्ण बिटस्ट्रिंग है, जहां 1 एक संक्रमित गाय का प्रतिनिधित्व करता है और 0 कुछ रातों के बाद एक असंक्रमित गाय का प्रतिनिधित्व करता है।

आउटपुट स्वरूप
एक पूर्णांक आउटपुट करें: गायों की न्यूनतम संख्या जो बीमारी से शुरू हो सकती थी।

नमूना इनपुट:
5
11111
नमूना आउटपुट:
1
मान लीजिए कि बीच वाली गाय ही एकमात्र ऐसी गाय थी जो संक्रमित होने लगी। फिर गायें निम्नलिखित क्रम में संक्रमित होंगी:

0 रातें: 00100 (तीसरी गाय प्रारंभ में संक्रमित है)
1 रात:01110 (अब दूसरी और चौथी गायें संक्रमित हैं)
2 रातें:11111 (पहली और पांचवीं गायें अब संक्रमित हैं)
3 रातें: 11111 (सभी गायें पहले से ही संक्रमित थीं, इसलिए कोई अतिरिक्त गाय संक्रमित नहीं हैं)

दो या अधिक रातों के बाद, गायों की अंतिम स्थिति इनपुट की तरह दिखेगी। ऐसी कई अन्य प्रारंभिक अवस्थाएँ और रातों की संख्या हैं जो इनपुट अवस्था उत्पन्न कर सकती थीं, जैसे:

0 रातें: 10001
1 रात:11011
2 रातें:11111
या:

0 रातें:01001
1 रात:11111
या:

0 रातें:01000
1 रात:11100
2 रातें:11110
3 रातें:11111
इन सभी प्रारंभिक अवस्थाओं में कम से कम एक संक्रमित गाय है।

नमूना इनपुट:
6
011101
नमूना आउटपुट:
4
एकमात्र आरंभिक अवस्था और रातों की संख्या जो इस अंतिम अवस्था तक ले जा सकती थी, वह यह है कि यदि कोई रातें न बीती हों और इनपुट में चार संक्रमित गायों में से प्रत्येक की शुरुआत बीमारी से हुई हो।

स्कोरिंग:

* इनपुट 3-7: N≤1000
* इनपुट 8-12: कोई अतिरिक्त बाधा नहीं।

मुझे C++ का उपयोग करके इस प्रश्न को हल करने की आवश्यकता थी।

मैंने क्या प्रयास किया है:

मैंने एक समाधान के बारे में सोचने की कोशिश की है, लेकिन अब मुझे लगता है कि मैं केवल इस प्रश्न का उल्टा करना जानता हूं 🙁 मैं कोई समाधान नहीं सोच सकता। कृपया मेरी मदद करें! मैं उस प्रकार का व्यक्ति हूं जिसे इसकी आवश्यकता है जब मैं कोई प्रश्न देखूं तो उसे हल करें। मैं अभी नौसिखिया हूं, इसलिए कृपया मदद करें!