मान लीजिए हमारे पास n बिट्स के साथ एक बाइनरी स्ट्रिंग S है और एक और संख्या d है। एक संख्या रेखा पर, एक मेंढक बिंदु 1 से शुरू करके बिंदु n तक पहुंचना चाहता है। मेंढक दाईं ओर अधिकतम d दूरी तक कूद सकता है। 1 से n तक प्रत्येक बिंदु के लिए यदि वहां लिली फूल है तो इसे 1 के रूप में चिह्नित किया जाता है, और 0 यदि नहीं। मेंढक केवल लिली वाले बिंदुओं पर कूद सकता है। हमें मेंढक को n तक पहुंचने के लिए आवश्यक न्यूनतम जंप की संख्या ज्ञात करनी है। यदि संभव नहीं है, तो -1 लौटाएं।
इसलिए, यदि इनपुट S = "10010101"; d = 4 है, तो आउटपुट 2 होगा, क्योंकि स्थिति 1 से, यह 4 पर कूदता है, फिर इंडेक्स 8 (n) पर।
चरण
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
n := size of s x := 0 y := 0 while (x < n - 1 and y <= n), do: if s[x] is same as '1', then: x := x + d increase y by 1 Otherwise (decrease x by 1) if y >= n, then: return -1 Otherwise return y
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(string s, int d){ int n = s.size(); int x = 0, y = 0; while (x < n - 1 && y <= n){ if (s[x] == '1') x += d, ++y; else --x; } if (y >= n) return -1; else return y; } int main(){ string S = "10010101"; int d = 4; cout << solve(S, d) << endl; }इनपुट
"10010101", 4
आउटपुट
2
