TopCoder problem "RepeatingFreeStrings" used in TCO07 Finals (Division I Level Three)



Problem Statement

    

A binary string s is called "repeating free" if no proper prefix equals a proper suffix of the same lengh. A substring is called "proper" if it differs from the whole string. For example, strings "0101011", "10", "10111100" are repeating free, but the string "01101011" is not.

Return the k-th string among all repeating free strings with length n in lexicographical order (k is a 0-based index). Return an empty string if it doesn't exist.

 

Definition

    
Class:RepeatingFreeStrings
Method:kthString
Parameters:int, int
Returns:String
Method signature:String kthString(int n, int k)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 50, inclusive.
-k will be between 0 and 2000000000, inclusive.
 

Examples

0)
    
2
0
Returns: "01"
All repeating free strings of length 2 are "01" and "10".
1)
    
2
1
Returns: "10"
2)
    
3
2
Returns: "100"
All repeating strings of length 3 are "001", "011", "100", "110".
3)
    
5
2
Returns: "00101"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7849

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10843&pm=7849

Writer:

Mike Mirzayanov

Testers:

PabloGilberto , Yarin , legakis , Olexiy , ivan_metelsky

Problem categories:

Advanced Math