โค้ด C++ หาจำนวนกระโดดน้อยที่สุดของกบ

โจทย์: สายบाइनารี S ความยาว n กบเริ่มที่ 1 อยากไป n กระโดดได้สูงสุด d ไปขวา เฉพาะตำแหน่งที่มี '1' (ใบบัว) หาจำนวนกระโดดน้อยที่สุด ไม่ได้คืน -1

Input: S="10010101", d=4 → Output: 2 (กระโดด 1→4→8)

ขั้นตอนแก้

x := 0, y := 0
while x < n-1 and y <= n:
    if s[x] == '1': x += d, y++
    else: x--
if y >= n: return -1 else return y

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;
int solve(string s, int d) {
    int n = s.size(), x = 0, y = 0;
    while (x < n-1 && y <= n) {
        if (s[x] == '1') x += d, ++y;
        else --x;
    }
    return (y >= n) ? -1 : y;
}
int main() {
    string S = "10010101";
    int d = 4;
    cout << solve(S,d) << endl;
}

Input

"10010101", 4

Output

2