ACM 900 Brick Wall Patterns

觀察n值與排列方式。
事實上可以發現有直板跟橫板兩種情況。
直板一個佔用一個面積，橫板一個佔用兩個面積。
所以n = 1時，無橫板，
n = 2時，最多1個橫板，
n = 3時，最多1個橫板，
n = 4時，最多2個橫板，
n = 5時，最多2個橫板，
n = 6時，最多3個橫板。
可以發現最多橫板數為n / 2。
每多一個橫板，組合方式就會多一種。
n = 1時，無橫板的組合，
n = 2時，無橫板的組合 + 1個橫板的組合，
n = 3時，無橫板的組合 + 1個橫板的組合，
n = 4時，無橫板的組合 + 1個橫板的組合 + 2個橫板的組合，
n = 5時，無橫板的組合 + 1個橫板的組合 + 2個橫板的組合，
n = 6時，無橫板的組合 + 1個橫板的組合 + 2個橫板的組合 + 3個橫板的組合。
無橫板的組合，就都是直板：Cn取n。
1個橫板的組合，為n - 2個直板 + 1個橫板：C的n - 1取1。
2個橫板的組合，為n - 4個直板 + 2個橫板：C的n - 2取2。
看出來了嗎？
每多一塊橫板，直板的數目就會少2。
有了直板與橫板的數目，就可以求得組合的情況。
其實就是要算這種問題：
有m塊直板跟n塊橫板，求其組合方式：(m + n)! / (n! * m!)。
把組合數加一加，就是答案了。
可以利用ACM369的方式計算組合。

/* ACM 900 Brick Wall Patterns
 * mythnc
 * 2011/12/30 10:12:43   
 * run time: 0.008
 */
#include <stdio.h>

#define MAXN 50
#define MIN(X, Y) ((X <= Y) ? X : Y)

long long count(int);
long long com(int, int);
int gcd(int, int);

int main(void)
{
    int n, i;

    while (scanf("%d", &n) && n != 0)
        printf("%lld\n", count(n));

    return 0;
}

/* count: return the combination numbers */
long long count(int n)
{
    int i, ver, hor;
    long long times;

    times = 1;
    ver = n - 2;
    hor = 1;
    while (ver >= 0) {
        times += com(ver, hor);
        ver -= 2;
        hor++;
    }

    return times;
}

/* com: return the combination times:
 * (m + n)! / (n! * m!) */
long long com(int m, int n)
{
    int sum, i, j, times, factor, tmp;
    long long ans[MAXN] = { 0 };

    if (m == 0 || n == 0)
        return 1;
    if (m == 1 || n == 1)
        return m + n;

    times = 0;
    sum = m + n;
    /* init */
    for (i = sum - MIN(m, n) + 1; i <= sum; i++)
        ans[times++] = i;
    /* simplify */
    for (i = 2; i <= MIN(m, n); i++) {
        tmp = i;
        for (j = 0; j < times; j++) {
            if (ans[j] % tmp == 0) {
                ans[j] /= tmp;
                break;
            }
            if ((factor = gcd(tmp, ans[j])) != 1) {
                ans[j] /= factor;
                tmp /= factor;
            }
        }
    }
    /* cal ans */
    for (i = 1; i < times; i++)
        ans[0] *= ans[i];

    return ans[0];
}

/* gcd: return gcd */
int gcd(int a, int b)
{
    while ((a %= b) && (b %= a))
        ;

    return a + b;
}