{"raw_statement":[{"iden":"statement","content":"_From beginning till end, this message has been waiting to be conveyed._\n\nFor a given unordered multiset of _n_ lowercase English letters (\"multi\" means that a letter may appear more than once), we treat all letters as strings of length 1, and repeat the following operation _n_ - 1 times:\n\n*   Remove any two elements _s_ and _t_ from the set, and add their concatenation _s_ + _t_ to the set.\n\nThe cost of such operation is defined to be , where _f_(_s_, _c_) denotes the number of times character _c_ appears in string _s_.\n\nGiven a non-negative integer _k_, construct any valid non-empty set of no more than 100 000 letters, such that the minimum accumulative cost of the whole process is **exactly** _k_. It can be shown that a solution always exists."},{"iden":"input","content":"The first and only line of input contains a non-negative integer _k_ (0 ≤ _k_ ≤ 100 000) — the required minimum cost."},{"iden":"output","content":"Output a non-empty string of no more than 100 000 lowercase English letters — any multiset satisfying the requirements, concatenated to be a string.\n\nNote that the printed string doesn't need to be the final concatenated string. It only needs to represent an unordered multiset of letters."},{"iden":"examples","content":"Input\n\n12\n\nOutput\n\nabababab\n\nInput\n\n3\n\nOutput\n\ncodeforces"},{"iden":"note","content":"For the multiset {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}, one of the ways to complete the process is as follows:\n\n*   {_\"ab\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_}, with a cost of 0;\n*   {_\"aba\"_, _\"b\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_}, with a cost of 1;\n*   {_\"abab\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_}, with a cost of 1;\n*   {_\"abab\"_, _\"ab\"_, _\"a\"_, _\"b\"_}, with a cost of 0;\n*   {_\"abab\"_, _\"aba\"_, _\"b\"_}, with a cost of 1;\n*   {_\"abab\"_, _\"abab\"_}, with a cost of 1;\n*   {_\"abababab\"_}, with a cost of 8.\n\nThe total cost is 12, and it can be proved to be the minimum cost of the process."}],"translated_statement":[{"iden":"statement","content":"_From beginning till end, this message has been waiting to be conveyed._\n\n对于一个给定的无序多重集（“多重”表示一个字母可以出现多次）包含 #cf_span[n] 个小写英文字母，我们将所有字母视为长度为 #cf_span[1] 的字符串，并重复以下操作 #cf_span[n - 1] 次：\n\n此类操作的代价定义为 ，其中 #cf_span[f(s, c)] 表示字符 #cf_span[c] 在字符串 #cf_span[s] 中出现的次数。\n\n给定一个非负整数 #cf_span[k]，构造一个包含不超过 #cf_span[100 000] 个字母的任意有效非空多重集，使得整个过程的最小累积代价 *恰好* 为 #cf_span[k]。可以证明，解总是存在的。\n\n输入的第一行且唯一一行包含一个非负整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——所需的最小代价。\n\n请输出一个非空字符串，包含不超过 #cf_span[100 000] 个小写英文字母——任意满足要求的多重集，以字符串形式拼接而成。\n\n注意：输出的字符串不需要是最终拼接后的字符串，它只需表示一个无序的字母多重集。\n\n对于多重集 {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}，完成该过程的一种方式如下：\n\n总代价为 #cf_span[12]，且可证明这是该过程的最小代价。\n\n"},{"iden":"input","content":"输入的第一行且唯一一行包含一个非负整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——所需的最小代价。"},{"iden":"output","content":"请输出一个非空字符串，包含不超过 #cf_span[100 000] 个小写英文字母——任意满足要求的多重集，以字符串形式拼接而成。注意：输出的字符串不需要是最终拼接后的字符串，它只需表示一个无序的字母多重集。"},{"iden":"examples","content":"输入\n12\n输出\nabababab\n\n输入\n3\n输出\ncodeforces"},{"iden":"note","content":"对于多重集 {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}，完成该过程的一种方式如下：\n{_\"ab\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_}，代价为 #cf_span[0]；\n{_\"aba\"_, _\"b\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_}，代价为 #cf_span[1]；\n{_\"abab\"_, _\"a\"_, _\"b\"_, _\"a\"_, _\"b\"_}，代价为 #cf_span[1]；\n{_\"abab\"_, _\"ab\"_, _\"a\"_, _\"b\"_}，代价为 #cf_span[0]；\n{_\"abab\"_, _\"aba\"_, _\"b\"_}，代价为 #cf_span[1]；\n{_\"abab\"_, _\"abab\"_}，代价为 #cf_span[1]；\n{_\"abababab\"_}，代价为 #cf_span[8]。总代价为 #cf_span[12]，且可证明这是该过程的最小代价。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the required minimum accumulative cost.  \nLet $ S $ be a multiset of lowercase English letters, with $ |S| = n \\geq 1 $, and let $ f(S, c) $ denote the frequency of character $ c $ in $ S $.  \n\n**Operation**  \nRepeatedly select two distinct characters $ c_1, c_2 \\in S $, remove one occurrence of each, and add one new character (arbitrary, but not affecting cost) back to $ S $. This reduces the multiset size by 1. Repeat $ n - 1 $ times until one character remains.  \n\n**Cost of Operation**  \nThe cost of removing one occurrence of $ c_1 $ and one of $ c_2 $ is $ f(S, c_1) + f(S, c_2) $, evaluated *before* the removal.  \n\n**Objective**  \nConstruct any multiset $ S $ with $ 1 \\leq |S| \\leq 100{,}000 $ such that the *minimum possible total cost* over all valid sequences of operations is exactly $ k $.  \n\n**Key Insight**  \nThe minimum total cost is independent of the order of operations and equals:  \n$$\nk = \\sum_{c \\in \\Sigma} f(S, c) \\cdot (f(S, c) - 1) / 2\n$$  \nThat is, the sum over all characters of the number of unordered pairs of identical letters.  \n\n**Equivalent Formulation**  \nLet $ n_i $ be the frequency of the $ i $-th distinct character in $ S $. Then:  \n$$\nk = \\sum_{i} \\binom{n_i}{2} = \\sum_{i} \\frac{n_i(n_i - 1)}{2}\n$$  \nWe must find non-negative integers $ n_1, n_2, \\dots, n_m $ (for some $ m \\geq 1 $) such that:  \n$$\n\\sum_{i=1}^m \\binom{n_i}{2} = k, \\quad \\sum_{i=1}^m n_i \\leq 100{,}000\n$$  \n\n**Construction**  \nUse at most two distinct characters:  \n- If $ k = 0 $, output any single character (e.g., `\"a\"`).  \n- Otherwise, find the largest integer $ a $ such that $ \\binom{a}{2} \\leq k $.  \n  Let $ r = k - \\binom{a}{2} $.  \n  - If $ r = 0 $, use $ a $ copies of one letter (e.g., `'a' * a`).  \n  - If $ r > 0 $, use $ a $ copies of `'a'` and $ b = r + 1 $ copies of `'b'` (since $ \\binom{b}{2} = \\binom{r+1}{2} $, but we only need $ r = \\binom{b}{2} - \\binom{b-1}{2} = b-1 $, so set $ b = r + 1 $, then $ \\binom{b}{2} - \\binom{b-1}{2} = r $, and total cost is $ \\binom{a}{2} + r = k $).  \n\nThus, construct:  \n- If $ k = 0 $: `\"a\"`  \n- Else:  \n  Let $ a = \\left\\lfloor \\frac{1 + \\sqrt{1 + 8k}}{2} \\right\\rfloor $  \n  Let $ r = k - \\binom{a}{2} $  \n  If $ r = 0 $: output `'a' * a`  \n  Else: output `'a' * a + 'b' * (r + 1)`  \n\n**Constraints**  \n$ |S| = a + (r + 1) \\leq 100{,}000 $ (guaranteed since $ k \\leq 100{,}000 $, and $ a \\leq \\sqrt{2k} + 1 \\ll 100{,}000 $).  \n\n**Output**  \nA string representing the multiset $ S $, as described.","simple_statement":null,"has_page_source":false}