DWITE, November 2012, Problem 3
A 'bitstring' is a string consisting of s and
s. However, you're only looking for bitstrings with the following properties:
- There are no two consecutive
s in the bitstring.
- Every run of
s is of even length (i.e. every block of
s has an even number of
s in it).
is an example of such a bitstring, but
is not. Luckily, your Computer Science (or Combinatorics) teacher shares a formula for figuring out how many such bitstrings exist for any given length
:
That is, there is only string of size
(empty string matches both rules). Only
string of size
("
"), and only
string of size
("
"). For size
, you'd need to calculate the sum of
and
, which are known from the results above.
The input will contain 5 test cases, each a line with a single integer , the length of the bitstring.
The output will contain 5 lines of output, each the number of different bitstrings of the corresponding length , with the described properties.
Sample Input
1
20
Sample Output
1
200
Problem Resource: DWITE
Comments