ZeroJudge 解題筆記：g541. 類題:兔子跳躍(TOIP)

作者：王一哲
日期：2025年3月27日



ZeroJudge 題目連結：g541. 類題:兔子跳躍(TOIP)

解題想法

雖然看起來是g498. 兔子跳躍 (Rabbit)的加強版，但其實用相同的寫法跑迴圈測試是否能走到 $d$ 一定會超時，即使用字典儲存已經跑過的值還是會超時，需要從數學上分析題目才行。如果兩種步數 $m$、$n$ 的最大公因數為 $G$、最小公倍數為 $L$，則所有 $L + kG, k = 0, 1, 2, 3, \dots$ 的數皆可以用大於等於 0 個 $m$、$n$ 組合而成，若以 $m = 9$、$n = 12$ 為例，$G = 3$、$L = 36$，則

1. $36 = 4 \times 9 = 3 \times 12$
2. $39 = 3 \times 9 + 1 \times 12$
3. $42 = 2 \times 9 + 2 \times 12$
4. $45 = 1 \times 9 + 3 \times 12$
5. $48 = 0 \times 9 + 4 \times 12$
6. $51 = 3 \times 9 + 2 \times 12$
7. $54 = 2 \times 9 + 3 \times 12$
8. $57 = 1 \times 9 + 4 \times 12$
9. $60 = 0 \times 9 + 5 \times 12 = 4 \times 9 + 2 \times 12$
10. $63 = 3 \times 9 + 3 \times 12$

Python 程式碼

寫法1，根據g498. 兔子跳躍 (Rabbit)的寫法改寫而成，第2筆測資開始超時。

import sys

def solve(m, n, d):  # 自訂函式，測是是否能走到 d
    for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
        if (d-i)%n == 0: return True  # 如果 d-i 可以被 n 整除，能走到 d
    return False  # 如果能跑完 for 迴圈，走不到 d

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(m, n, d) else "NO")  # 印出答案

寫法2，根據以上的寫法並改用 map 儲存已經測試過的值，第2筆測資開始超時。

import sys

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q
    memo = dict()  # 記憶已經算過的數據
    def solve(d):  # 自訂函式，測是是否能走到 d
        if d in memo: return memo[d]
        for i in range(0, d+1, m):  # 依序測試 0, m, 2m, 3m, ...
            if (d-i)%n == 0:
                memo[d] = True
                return True  # 如果 d-i 可以被 n 整除，能走到 d
        memo[d] = False
        return False  # 如果能跑完 for 迴圈，走不到 d
    for d in list(map(int, input().split())):  # 執行 q 次
        print("YES" if solve(d) else "NO")  # 印出答案

寫法3，利用數學關係，使用時間約為 1.4 s，記憶體約為 147 MB，通過測試。

import sys
from math import gcd  # 3.9 版才有 lcm

for line in sys.stdin:
    m, n, q = map(int, line.split())  # 可跳距離 m、n，詢問次數 q，目標距離 d
    #G, L = gcd(m, n), lcm(m, n)  # 最大公因數、最小公倍數
    G = gcd(m, n); L = m*n//G  # 最大公因數、最小公倍數
    dp = [False]*L  # d < L 的部分是否能走到需要先建表格
    for i in range(0, L, m):  # 依序測試 0, m, 2m, 3m, ..., L-1
        for j in range(0, L-i, n):  # 依序測試 0, n, 2n, 3n, ..., L-i-1
            dp[i+j] = True  # 能走到 i+j
    for d in list(map(int, input().split())):  # 執行 q 次
        if d >= L: print("YES" if d%G == 0 else "NO")
        else: print("YES" if dp[d] else "NO")

C++ 程式碼

寫法1，第4筆測資開始超時。

#include <cstdio>
using namespace std;

bool solve(int m, int n, int d) {  // 自訂函式，測是是否能走到 d
    for(int i=0; i<=d; i+=m) {  // 依序測試 0, m, 2m, 3m, ...
        if ((d-i)%n == 0) return true;  // 如果 d-i 可以被 n 整除，能走到 d
    }
    return false;  // 如果能跑完 for 迴圈，走不到 d
}

int main() {
    int m, n, q, d;  // 可跳距離 m、n，詢問次數 q，目標距離 d
    while(scanf("%d %d %d", &m, &n, &q) != EOF) {
        if (m < n) {  // 如果 m 較小，交換 m、n
            int t = m;
            m = n; n = t;
        }
        for(int i=0; i<q; i++) {  // 執行 q 次
            scanf("%d", &d);
            if (solve(m, n, d)) printf("YES\n");  // 印出答案
            else printf("NO\n");
        }
    }
    return 0;
}

寫法2，改用 map 儲存已經測試過的值，第4筆測資開始超時。

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

bool solve(int m, int n, int d, map<int, bool>& memo) {  // 自訂函式，測是是否能走到 d
    if (memo.find(d) != memo.end()) return memo[d];  // 如果 d 已經在 memo 之中，回傳 memo[d]
    for(int i=0; i<=d; i+=m) {  // 依序測試 0, m, 2m, 3m, ...
        if ((d-i)%n == 0) {  // 如果 d-i 可以被 n 整除，能走到 d
            memo[d] = true;
            return true;
        }
    }
    memo[d] = false;  // 如果能跑完 for 迴圈，走不到 d
    return false;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n, q, d;  // 可跳距離 m、n，詢問次數 q，目標距離 d
    while(cin >> m >> n >> q) {
        if (m < n) swap(m, n);  // 如果 m 較小，交換 m、n
        map<int, bool> memo;  // 記錄已經算過的 d 是否能走到
        for(int i=0; i<q; i++) {  // 執行 q 次
            int d; cin >> d;
            if (solve(m, n, d, memo)) cout << "YES\n";  // 印出答案
            else cout << "NO\n";
        }
    }
    return 0;
}

寫法3，使用時間約為 0.3 s，記憶體約為 356 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>  // for __gcd
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n, q;  // 可跳距離 m、n，詢問次數 q
    while(cin >> m >> n >> q) {
        int G = __gcd(m, n);  // 最大公因數
        int L = m*n/G;  // 最小公倍數
        vector<bool> dp (L, false);  // d < L 的部分是否能走到需要先建表格
        for(int i=0; i<L; i+=m) {  // 依序測試 0, m, 2m, 3m, ..., L-1
            for(int j=0; j<L-i; j+=n) {  // 依序測試 0, n, 2n, 3n, ..., L-i-1
                dp[i+j] = true;  // 能走到 i+j
            }
        }
        for(int i=0; i<q; i++) {  // 執行 q 次
            int d; cin >> d;  // 目標距離 d
            if (d >= L) cout << (d%G == 0 ? "YES\n" : "NO\n");  // 印出答案
            else cout << (dp[d] ? "YES\n" : "NO\n");
        }
    }
    return 0;
}