// 演算法 / Algorithm: dp[i] = 下標 i 是否可達。用滑動視窗 + 前綴計數 pre 記錄
// 前驅區間 [i-maxJump, i-minJump] 內有多少可達位置，整段掃描只需 O(n)。
// dp[i] = is index i reachable. A sliding-window running count `pre` tracks how
// many reachable predecessors lie in [i-maxJump, i-minJump]; one O(n) pass.
#include <string.h>   // strlen
#include <stdlib.h>   // calloc / free
#include <stdbool.h>  // bool, true, false

bool canReach(char* s, int minJump, int maxJump) {
    int n = strlen(s);                 // 字串長度 / length of the string
    if (s[n - 1] == '1') return false; // 末端是 '1' 就永遠落不上去 / last cell '1' is unreachable

    // calloc 配置 n 個 bool 並全部清為 0(false) / allocate n bools, all zero(false)
    bool* dp = (bool*)calloc(n, sizeof(bool));
    dp[0] = true;                      // 起點一定可達 / the start is always reachable
    int pre = 0;                       // 視窗內可達前驅的個數 / count of reachable predecessors in window

    for (int i = 1; i < n; i++) {      // 從 1 開始逐一判斷每個下標 / decide each index from 1 onward
        // 視窗右端新進來的元素是 dp[i-minJump]；i>=minJump 時它才存在
        // The element entering the window's right edge is dp[i-minJump]; valid when i>=minJump
        if (i >= minJump && dp[i - minJump]) pre += 1;

        // 視窗左端滑出的元素是 dp[i-maxJump-1]；i>maxJump 時它才曾在視窗內
        // The element leaving the window's left edge is dp[i-maxJump-1]; valid when i>maxJump
        if (i > maxJump && dp[i - maxJump - 1]) pre -= 1;

        // 當前格是 '0' 且視窗裡至少有一個可達前驅，則本格可達
        // Current cell is '0' and at least one reachable predecessor exists → reachable
        if (s[i] == '0' && pre > 0) dp[i] = true;
    }

    bool ans = dp[n - 1];              // 答案就是能否到達最後一格 / answer = is the last cell reachable
    free(dp);                          // 釋放動態記憶體，避免洩漏 / free heap memory to avoid a leak
    return ans;
}