LightOJ 1027 - A Dangerous Maze：期望時間數學推導與 GCD 化簡

問題模型

n 扇門，等概率選擇。第 i 扇門：

• x_i > 0：x_i 分鐘後出去
• x_i < 0：|x_i| 分鐘後回到起點，記憶清零

求走出迷宮的期望時間，輸出既約分數 p/q。

數學推導

設：

• m = 可出去的門數
• sumT1 = 所有出去門的時間和
• sumT2 = 所有返回門的時間和（取絕對值）
• p = m/n，q = 1-p
• T1 = sumT1/m，T2 = sumT2/(n-m)

期望 E 滿足：

E = p·T1 + q·(T2 + E)
E - q·E = p·T1 + q·T2
p·E = p·T1 + q·T2
E = T1 + (q/p)·T2

代入化簡得驚人簡單公式：

E = (sumT1 + sumT2) / m

算法

1. 統計 m、sumT1、sumT2（均取絕對值累加）
2. 若 m==0 輸出 inf
3. 否則 p = sumT1+sumT2，q = m，約分輸出 p/q

C++ 代碼

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;

LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }

int main() {
    int T; scanf("%d", &T);
    for (int tc=1; tc<=T; ++tc) {
        int n; scanf("%d", &n);
        LL all = 0; int cnt = 0;
        for (int i=0, x; i 0) ++cnt;
        }
        if (cnt == 0) {
            printf("Case %d: inf\n", tc);
        } else {
            LL g = gcd(all, cnt);
            printf("Case %d: %lld/%lld\n", tc, all/g, cnt/g);
        }
    }
    return 0;
}

樣例驗證

輸入:
3
1
1
2
-10 -3
3
3 -6 -9

輸出:
Case 1: 1/1
Case 2: inf
Case 3: 18/1

Case 3: all = 3+6+9=18, cnt=1 → 18/1。