C. From Y to Y

Codeforces

IDCF849C

Time1000ms

Memory256MB

Difficulty—

constructive algorithms

English · Original

Chinese · Translation

Formal · Original

_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 treat all letters as strings of length 1, and repeat the following operation _n_ - 1 times: * Remove any two elements _s_ and _t_ from the set, and add their concatenation _s_ + _t_ to the set. The cost of such operation is defined to be , where _f_(_s_, _c_) denotes the number of times character _c_ appears in string _s_. Given 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. ## Input The first and only line of input contains a non-negative integer _k_ (0 ≤ _k_ ≤ 100 000) — the required minimum cost. ## Output Output a non-empty string of no more than 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. [samples] ## Note For the multiset {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}, one of the ways to complete the process is as follows: * {_"ab"_, _"a"_, _"b"_, _"a"_, _"b"_, _"a"_, _"b"_}, with a cost of 0; * {_"aba"_, _"b"_, _"a"_, _"b"_, _"a"_, _"b"_}, with a cost of 1; * {_"abab"_, _"a"_, _"b"_, _"a"_, _"b"_}, with a cost of 1; * {_"abab"_, _"ab"_, _"a"_, _"b"_}, with a cost of 0; * {_"abab"_, _"aba"_, _"b"_}, with a cost of 1; * {_"abab"_, _"abab"_}, with a cost of 1; * {_"abababab"_}, with a cost of 8. The total cost is 12, and it can be proved to be the minimum cost of the process.

_From beginning till end, this message has been waiting to be conveyed._ 对于一个给定的无序多重集（"multi" 表示一个字母可以出现多次）包含 #cf_span[n] 个小写英文字母，我们将所有字母视为长度为 #cf_span[1] 的字符串，并重复以下操作 #cf_span[n - 1] 次：该操作的代价定义为，其中 #cf_span[f(s, c)] 表示字符 #cf_span[c] 在字符串 #cf_span[s] 中出现的次数。给定一个非负整数 #cf_span[k]，构造一个任意有效的非空集合，包含不超过 #cf_span[100 000] 个字母，使得整个过程的最小累积代价恰好为 #cf_span[k]。可以证明解一定存在。输入的第一行且唯一一行包含一个非负整数 #cf_span[k]（#cf_span[0 ≤ k ≤ 100 000]）——所需的最小代价。请输出一个非空字符串，长度不超过 #cf_span[100 000] 的小写英文字母——任意满足要求的多重集，以字符串形式拼接输出。注意：输出的字符串不需要是最终拼接后的字符串，它仅需表示一个无序的字母多重集。对于多重集 {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}，完成该过程的一种方式如下：总代价为 #cf_span[12]，可以证明这是该过程的最小代价。 ## Input The first and only line of input contains a non-negative integer #cf_span[k] (#cf_span[0 ≤ k ≤ 100 000]) — the required minimum cost. ## Output Output 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. [samples] ## Note 对于多重集 {_'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_, _'a'_, _'b'_}，完成该过程的一种方式如下： {_"ab"_, _"a"_, _"b"_, _"a"_, _"b"_, _"a"_, _"b"_}，代价为 #cf_span[0]； {_"aba"_, _"b"_, _"a"_, _"b"_, _"a"_, _"b"_}，代价为 #cf_span[1]； {_"abab"_, _"a"_, _"b"_, _"a"_, _"b"_}，代价为 #cf_span[1]； {_"abab"_, _"ab"_, _"a"_, _"b"_}，代价为 #cf_span[0]； {_"abab"_, _"aba"_, _"b"_}，代价为 #cf_span[1]； {_"abab"_, _"abab"_}，代价为 #cf_span[1]； {_"abababab"_}，代价为 #cf_span[8]。总代价为 #cf_span[12]，可以证明这是该过程的最小代价。

**Definitions** Let $ k \in \mathbb{Z}_{\geq 0} $ be the target minimum accumulative cost. Let $ 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 $. **Constraints** 1. $ 0 \leq k \leq 100000 $ 2. $ 1 \leq |S| \leq 100000 $ **Objective** Construct 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. This minimum cost equals: $$ k = \sum_{c} \binom{f(c)}{2} $$ where the sum is over all distinct characters $ c $ in $ S $. Thus, find any multiset $ S $ such that: $$ \sum_{c} \frac{f(c)(f(c)-1)}{2} = k $$

Samples

Input #1

Output #1

abababab

Input #2

Output #2

codeforces

API Response (JSON)

{
  "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 tr...",
      "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该操作的代价定义为 ，...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments