Score : $400$ points

问题描述

在包含 $A$ 个 a 和 $B$ 个 b 的长度为 $A + B$ 的字符串中，找出第 $K$ 个字典序排列的字符串。

以上为通义千问 qwen-max 翻译，仅供参考。

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 of b.
• 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 as and two bs 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.

update @ 2024/3/10 09:14:32