[UVa] 900 Brick Wall Pattern.cpp

#include <cstdio>
using namespace std;
typedef long long int llt;

llt H (int m,int n){
    m = (m+n-1);
    if (n > m/2) n = (m-n);
    int M[100],N[100],i,j;
    for (i=0; i<n; i++){
        M[i] = m - i;
        N[i] = i + 1;
    }
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            if (N[j]!=1 && M[i]%N[j] == 0){
                M[i] = M[i]/N[j];
                N[j] = 1;
                break;
            }
    llt a=1, b=1;
    for (i=0; i<n; i++) {
        a *= M[i];
        b *= N[i];
    }
    return a/b;
}

int main()
{
    int L;
    llt patterns;
    while (scanf("%d",&L))
    {
        if (!L) break;
        patterns = 1;
        for (int i=1; L-2*i >= 0; i++)
            patterns += H(i+1,L-2*i);
        printf ("%lld\n",patterns);
    }
    return 0;
}