#DP #Adhoc #DominoTiling #ClosedFormula #UVa #Solved

10918 - Tri Tiling.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1859
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int cache[35];
int cache2[35];
int n;

int g(int n);

int f(int n) {
    if(n == 0) return 1;
    if(n == 1) return 0;
    int &ret = cache[n];
    if(ret != -1) return ret;

    return  ret = f(n-2) + 2*g(n-1);
}

int g(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;

    int &ret = cache2[n];
    if(ret!= -1) return ret;

    return ret = f(n-1) + g(n-2);
}

int main() {
    clr(cache, -1);
    clr(cache2, -1);
    while(cin>>n && n != -1) {
        if(n&1)
            cout << 0 << endl;
        else
            cout << f(n) << endl;
    }
    return 0;
}