# UVa 900

##  Summary

Given wall bricks of size 2x1 units, what is the number of all possible brick patterns for a wall of height 2 units and a length of $n \le 50$ units?

##  Explanation

Let fn be the number of ways to assembly a wall of length n.

There are two ways of assembling a wall of length n, and a height of 2 units. We either place a vertical bar at its beginning and assemble a wall of length n - 1 or we place two horizontal bars on top of one another and assemble then a wall of length n - 2. That is,

fn: = fn - 1 + fn - 2.

The base cases are already given in the example, which leads us to:

$f_n:= \begin{cases} 1, &n=1 \\ 2, &n=2 \\ f_{n-1} + f_{n-2}, & n > 2 \\ \end{cases}$

Which is the fibonacci series, with a slightly different base! (This proof was originally written by Schultz, on 21:20, 26 May 2007 (EDT))

You can solve the series blazingly fast in O(n) using a bottom-up dynamic programming solution.

## Gotchas

Use a 64-bit field to hold the results; f50 > 232 - 1.

## Input

1
2
3
4
5
6
7
50
0


## Output

1
2
3
5
8
13
21
20365011074