## Saturday, October 30, 2010

### poj_2506_Tiling.cpp

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

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;
}