poj_2506_Tiling.cpp

Problem Links:

poj2506, UVa10359, Hoj2014,

Problem:

Tiling

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5477		Accepted: 2670

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?
Here is a sample tiling of a 2x17 rectangle.

Input

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

Output

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

Sample Input

2
8
12
100
200

Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

Source

The UofA Local 2000.10.14

Solution:

Recursive.

Source Code:

//Thu Jul  8 10:33:36 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define MMAX 251
using namespace std;

vector<int> Tiling(vector<vector<int> > &v, int N)
{
    if (N == 0)
    {
        v[0][0] = 1;
        return v[0];
    }
    if (N == 1)
    {
        v[1][0] = 1;
        return v[1];
    }
    if (N == 2)
    {
        v[2][0] = 3;
        return v[2];
    }
    for (int i = 0; i < MMAX; i++)
        if (v[N][i] != 0)
            return v[N];
    v[N - 1] = Tiling(v, N - 1);
    v[N - 2] = Tiling(v, N - 2);
    int flag = 0;
    int i;
    for (i = 0; i < MMAX; i++)
    {
        v[N][i] = v[N - 1][i] + v[N - 2][i] * 2 + flag;
        if (v[N][i] >= 10)
        {
            flag = v[N][i] / 10;
            v[N][i] %= 10;
        }
        else
            flag = 0;
    }
    return v[N];
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
    vector<vector<int> > v(MMAX, vector<int> (MMAX));
    for (int i = 0; i < MMAX; i++)
        for (int j = 0; j < MMAX; j++)
            v[i][j] = 0;
    for (int i = 0; i < MMAX; i++)
    {
        v[i] = Tiling(v, i);
    }
    int N;
    while (cin >> N)
    {
        string str = "";
        int idx = MMAX - 1;
        while (v[N][idx] == 0)
            idx--;
        while (idx >= 0)
            cout << v[N][idx--];
        cout << endl;
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}