0121. Fibonacci Strings
| Input file name: | fib.in |
| Output file name: | fib.out |
| Time limit: | 500 ms |
| Memory limit: | 64 megabytes |
A Fibonacci string is a string of 0s and 1s that does not contain consecutive 1s.
Output a Fibonacci string by its position in the lexicographically ordered set of all Fibonacci strings of the same length.
Input file
The input file contains two integers n and k; n is the length of the Fibonacci string (1 ≤ n ≤ 44), and k is the postion of the string to be displayed (valid k ≥ 1).
Output file
Output n-th Fibonacci string in the only line of output.
Examples:
| fib.in | fib.out |
|---|---|
| 3 3 | 010 |
Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov
Discuss Submit a solution