สมมติว่าเรามีสตริงไบนารี S หนึ่งตัวที่มี n บิตและอีกจำนวนหนึ่งคือ d บนเส้นจำนวน กบต้องการไปถึงจุด n โดยเริ่มจากจุดที่ 1 กบสามารถกระโดดไปทางขวาได้ในระยะไม่เกิน 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
