মান লক্ষ্য করুন একটি n বিটের বাইনারি স্ট্রিং S এবং আরেকটি সংখ্যা d। একটি নাম্বার লাইনে, একটি বাঙ পয়েন্ট n-এ পৌঁছাতে চায়, পয়েন্ট ১ থেকে শুরু করে। বাঙ ডানে পার্শ্বে d দূরত্ব পর্যন্ত জাম্প দিতে পারে। ১ থেকে n প্রতিটি পয়েন্টে যদি লিলি ফুল থাকে তবে ১, না থাকলে ০ দিয়ে মার্ক করা আছে। বাঙ শুধু লিলি ফুল থাকা পয়েন্টে জাম্প দিতে পারে। আমাদের বাঙ যে ন্যূনতম জাম্প দিয়ে n-এ পৌঁছাবে তা বের করতে হবে। যদি সম্ভব না হয়, তবে -1 রিটার্ন করুন।
তাই, যদি ইনপুট হয় S = "10010101"; d = 4, তবে আউটপুট হবে ২, কারণ পজিশন ১ থেকে ৪-এ জাম্প, তারপর ইনডেক্স ৮ (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
