{"problem":{"name":"C. From Y to Y","description":{"content":"_From beginning till end, this message has been waiting to be conveyed._ For a given unordered multiset of _n_ lowercase English letters (\"multi\" means that a letter may appear more than once), we tr","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF849C"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe first and only line of input contains a non-negative integer _k_ (0 ≤ _k_ ≤ 100 000) — the required minimum cost.\n\n## Output\n\nOutput 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.\n\n[samples]\n\n## Note\n\nFor 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"_From beginning till end, this message has been waiting to be conveyed._\n\n对于一个给定的无序多重集（\"multi\" 表示一个字母可以出现多次）包含 #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## Input\n\nThe first and only line of input contains a non-negative integer #cf_span[k] (#cf_span[0 ≤ k ≤ 100 000]) — the required minimum cost.\n\n## Output\n\nOutput a non-empty string of no more than #cf_span[100 000] lowercase English letters — any multiset satisfying the requirements, concatenated to be a string. Note that the printed string doesn't need to be the final concatenated string. It only needs to represent an unordered multiset of letters.\n\n[samples]\n\n## Note\n\n对于多重集 {_'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]，可以证明这是该过程的最小代价。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the target minimum accumulative cost.  \nLet $ S $ be a multiset of lowercase English letters with $ |S| = n \\geq 1 $, and let $ f(c) $ denote the frequency of character $ c $ in $ S $.  \n\n**Constraints**  \n1. $ 0 \\leq k \\leq 100000 $  \n2. $ 1 \\leq |S| \\leq 100000 $  \n\n**Objective**  \nConstruct a multiset $ S $ such that the minimum accumulative cost of repeatedly combining two strings into one (until one remains) is exactly $ k $, where the cost of combining two strings is the sum over all characters $ c $ of the product of their frequencies in the two strings being merged.  \n\nThis minimum cost equals:  \n$$\nk = \\sum_{c} \\binom{f(c)}{2}\n$$  \nwhere the sum is over all distinct characters $ c $ in $ S $.  \n\nThus, find any multiset $ S $ such that:  \n$$\n\\sum_{c} \\frac{f(c)(f(c)-1)}{2} = k\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF849C","tags":["constructive algorithms"],"sample_group":[["12","abababab"],["3","codeforces"]],"created_at":"2026-03-03 11:00:39"}}