UVa 900

Summary

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

Explanation

Let ${\displaystyle f_{n}}$ be the number of ways to assembly a wall of length ${\displaystyle n}$.

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

${\displaystyle f_{n}:=f_{n-1}+f_{n-2}}$.

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

${\displaystyle 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 ${\displaystyle O(n)}$ using a bottom-up dynamic programming solution.

Gotchas

Use a 64-bit field to hold the results; ${\displaystyle f_{50}>2^{32}-1}$.

Input

1
2
3
4
5
6
7
50
0


Output

1
2
3
5
8
13
21
20365011074