ধরুন আমাদের একটি বাইনারি স্ট্রিং S আছে n বিট সহ এবং আরেকটি সংখ্যা 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
