Submit | All submissions | Best solutions | Back to list |
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
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 |
hide comments
2014-11-09 15:07:40 Raju
IO from AC solution: 52 bbabb 60 aababb 70 ababbb 100 aaababb 102 aaabbab 150 bababaa 225 abbaaaba 500 bbaabbbab 1000 aabbabaaabb 2569 aaababbaababb 10000 babaaabbbaaabba 100005 ababaaababbabaababba 1234567 abbaabababaababbabababbaa 12345678 aabbabbaaabbababbaababbaaababa 87654321 abaababaabbabbaaabbabbabaababaabbb 100000000 abbbaaabbaabababbabbaababbaabbabab 9999999999 aabababaababbbaababbabaaabbbaabbaaabbbaabbab 10000000000 aabababaababbbaababbabaaabbbaabbaaabbbabaaab 100000000006 bbaabababbabaabaabababbaabbaabbababbaabaabbaabbb 9999999999990 ababbbabaabaabbabaabbbabaaabbaabbbaabbaaabbaabbbaabaabbaba 100000000000000 aabbbaabbaaabbbaaabbabaabbabbabaabaababbbaabbaabbaabbabaabbabaa Last edit: 2014-11-09 15:08:12 |
|
2012-03-26 21:12:30 Nikolay Nedelchev
123456 babababbaaababbbabaa 987654321 abaababbbabaabbaaabbbaababbababaaabbbab 65536 abbaabababaababbaab |