P8719 [Lanqiao Cup 2020 NOI Qualifier AB2] String Sorting

Xiao Lan has recently learned some sorting algorithms, and bubble sort impressed him a lot. In bubble sort, each time you can only swap two adjacent elements. Xiao Lan found that if you sort the characters in a string and only allow swapping two adjacent characters, then among all possible sorting methods, bubble sort uses the fewest total swaps. For example, sorting the string lan only needs $1$ swap. Sorting the string qiao needs a total of $4$ swaps. Xiao Lan’s lucky number is $V$. He wants to find a string that contains only lowercase English letters, such that performing bubble sort on the characters of this string requires exactly $V$ swaps. Please help Xiao Lan find such a string. If there are multiple possible strings, output the shortest one. If there are still multiple shortest ones, output the lexicographically smallest one. Note that the string may contain repeated characters.

The first line contains an integer $V$, Xiao Lan’s lucky number.

Output one line containing the required string.

For $30\%$ of the testdata, $1 \leq V \leq 20$. For $50\%$ of the testdata, $1 \leq V \leq 100$. For all testdata, $1 \leq V \leq 100000$. Lanqiao Cup 2020, Second Round of the Provincial Contest, Group A, Problem J (Group B, Problem J). Translated by ChatGPT 5