ZeroJudge M283: 螞蟻的擴散

題目敘述

本題採EOF方式收資料，每筆資料有兩個整數a和b。座標平面上，當螞蟻在(a,b)時，可隨機移動到點(a-1,b), (a,b-1), 或(a-1,b-1)之中的一點，且移動到上述任一點的機率均為1/3，又接下來每次移動都與前次移動無關。現有一螞蟻從 (x,y) 開始移動，直到第一次遇到任意座標軸即停止移動，請問此螞蟻最後一次停止的點不是在原點 (0,0) 機率為何?

範例輸入 #1

3 3

2 2

1 1

範例輸出 #1

70/81

22/27

2/3

解題思路

因為使用分數較難運算，所以可以將原點的機率 (也就是100%或1) 乘以3的a+b次方。可以使用二維陣列來存每個點的移動機率，使用雙For迴圈將每個點都走過一遍。答案的分子就是原本的點-(0, 0)的點的機率，分母就是原來的點的機率。最後將分數約分到最簡分數再輸出即可。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int x, y;
    while (cin >> x >> y)
    {
        long long int arr[20][20] = {0};
        long long int og = pow(3, x+y);
        arr[y][x] = og;
        for (int yy = y; yy>0; yy--)
        {
            for (int xx = x; xx>0; xx--)
            {
                long long int tmp = arr[yy][xx] / 3;
                arr[yy-1][xx] += tmp;
                arr[yy][xx-1] += tmp;
                arr[yy-1][xx-1] += tmp;
            }
        }
        long long int up = og - arr[0][0];
        long long int down = og;
        bool stop = false;
        while (!stop)
        {
            stop = true;
            for (long long int i = 2; i<=sqrt(up)+1; i++)
            {
                if (up % i == 0 && down % i == 0)
                {
                    up /= i;
                    down /= i;
                    stop = false;
                }
            }
        }
        cout << up << "/" << down << "\n";
    }
}