D - aab aba baa Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

A 個の a と B 個の b からなる長さ A + B の文字列のうち、辞書順で K 番目のものを求めてください。

制約

  • 1 \leq A, B \leq 30
  • A 個の a と B 個の b からなる長さ A + B の文字列の総数を S 個とおいたとき、1 \leq K \leq S
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

A B K

出力

答えを出力せよ。

入力例 1

2 2 4

出力例 1

baab

2 個の a と 2 個の b からなる文字列を辞書順に並べると、aabb、abab、abba、baab、baba、bbaa となります。 よって、4 番目である baab を出力します。

入力例 2

30 30 118264581564861424

出力例 2

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

K の値は 32 bit 整数に収まらないことがあります。

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 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.