UNICA - Unique Strings
Some people who love strings have decided to call a special group of strings as the “unique strings.”
Let’s define a(S) as the number of characters “a” the string S contains, and b(S) as the number of characters “b” the string S contains.
S is a unique string if:
- S only contains the characters “a” and “b”
- For every substring S’ of S, | a(S’) – b(S’) | <= 3
For example, “abbab” is a unique string. However, “abbbba” is not because it includes the substring “bbbb” for which | a(“bbbb”) – b(“bbbb”) | = 4 > 3.
Let’s say we sort the unique strings – first by length and then lexicographically. The Nth unique string is the string that appears in the position N in the sorted list. The first unique string is assigned the number 1.
The first 12 unique strings in the sorted list are: a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab
Input
A single number N (1 <= N <= 1014). Your task is to find the Nth unique string in the sorted list.
Output
A single line: the Nth unique string in the sorted list.
Example
Input: 10 Output: abb
Input: 19 Output: abab
hide comments
Raju:
2014-11-09 15:07:40
IO from AC solution:
|
|
Nikolay Nedelchev:
2012-03-26 21:12:30
123456
|
Added by: | Angel Paredes |
Date: | 2012-02-13 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Cuban Olympiad in Informatics 2011 - Day 2 Problem A |