102023: [AtCoder]ABC202 D - aab aba baa
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $400$ points
Problem Statement
Among the strings of length $A + B$ containing $A$ occurrences of a
and $B$ occurrences of b
, find the string that comes $K$-th in the lexicographical order.
Constraints
- $1 \leq A, B \leq 30$
- $1 \leq K \leq S$, where $S$ is the number of strings of length $A + B$ containing $A$ occurrences of
a
and $B$ occurrences ofb
. - All values in input are integers.
Input
Input is given from Standard Input in the following format:
$A$ $B$ $K$
Output
Print the answer.
Sample Input 1
2 2 4
Sample Output 1
baab
Here are the strings containing two a
s and two b
s in the lexicographical order: aabb
, abab
, abba
, baab
, baba
, and bbaa
.
The fourth string, baab
, should be printed.
Sample Input 2
30 30 118264581564861424
Sample Output 2
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
$K$ may not fit into a $32$-bit integer type.