DWITE '12 R2 #3 - Bitstrings

View as PDF

Submit solution

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 0s and 1s. However, you're only looking for bitstrings with the following properties:

  • There are no two consecutive 1s in the bitstring
  • Every run of 0s is of even length (i.e. every block of 0s has an even number of 0s in it).

1001 is an example of such bitstring, but 10001 is not. Luckily, your Computer Science (or Combinatorics) teacher shares a formula for figuring out how many such bitstrings exist for any given length N:

  • s(0) = 1, s(1) = 1, s(2) = 1
  • s(n) = s(n-2) + s(n-3) for all n > 2

That is, there is only 1 string of size 0 (empty string matches both rules). Only 1 string of size 1 ("1"), and only 1 string of size 2 ("00"). For size 3, you'd need to calculate the sum of s(3-2) and s(3-3), which are known from the results above.

The input will contain 5 test cases, each a line with a single integer 1 \le N \le 75, the length of the bitstring.

The output will contain 5 lines of output, each the number of different bitstrings of the corresponding length N, with the described properties.

Sample Input

1
20

Sample Output

1
200

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments

There are no comments at the moment.