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 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 :
- , ,
- for all
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.