DWITE '12 R2 #3 - Bitstrings

View as PDF

Points: 3
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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.

Sample Input

1
20

Sample Output

1
200