De Bruijn sequences (1) P85110


Statement
 

pdf   zip

html

A binary de Bruijn sequence of order n is a cyclic sequence of zeros and ones such that every possible subsequence of n consecutive digits appears exactly once. Please compute the lexicographically smallest de Bruijn sequence of order n.

Input

Input consists of several cases, each with an integer number n between 1 and 15.

Output

For every case, print the lexicographically smallest de Bruijn sequence of order n.

Hint

A “reasonable” backtracking algorithm should be fast enough to get this problem accepted.

Public test cases
  • Input

    2
    3
    4
    

    Output

    0011
    00010111
    0000100110101111
    
  • Information
    Author
    Xavier Martínez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Vuitè Concurs de Programació de la UPC - Semifinal
    Date
    2010-06-30