English · Original
Chinese · Translation
Formal · Original
Stepan had a favorite string _s_ which consisted of the lowercase letters of the Latin alphabet.
After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. But Stepan remembers some information about the string, namely the sequence of integers _c_1, _c_2, ..., _c__n_, where _n_ equals the length of the string _s_, and _c__i_ equals the number of substrings in the string _s_ with the length _i_, consisting of the **same** letters. The substring is a sequence of consecutive characters in the string _s_.
For example, if the Stepan's favorite string is equal to "_tttesst_", the sequence _c_ looks like: _c_ = \[7, 3, 1, 0, 0, 0, 0\].
Stepan asks you to help to repair his favorite string _s_ according to the given sequence _c_1, _c_2, ..., _c__n_.
## Input
The first line contains the integer _n_ (1 ≤ _n_ ≤ 2000) — the length of the Stepan's favorite string.
The second line contains the sequence of integers _c_1, _c_2, ..., _c__n_ (0 ≤ _c__i_ ≤ 2000), where _c__i_ equals the number of substrings of the string _s_ with the length _i_, consisting of the same letters.
It is guaranteed that the input data is such that the answer always exists.
## Output
Print the repaired Stepan's favorite string. If there are several answers, it is allowed to print any of them. The string should contain only lowercase letters of the English alphabet.
[samples]
## Note
In the first test Stepan's favorite string, for example, can be the string "_kkrrrq_", because it contains 6 substrings with the length 1, consisting of identical letters (they begin in positions 1, 2, 3, 4, 5 and 6), 3 substrings with the length 2, consisting of identical letters (they begin in positions 1, 3 and 4), and 1 substring with the length 3, consisting of identical letters (it begins in the position 3).
Stepan 有一个最喜欢的字符串 #cf_span[s]，它由拉丁字母的小写字母组成。
毕业后，他决定回忆起这个字符串，但已经过去很久了，所以他现在记不起来了。但 Stepan 记得关于这个字符串的一些信息，即整数序列 #cf_span[c1, c2, ..., cn]，其中 #cf_span[n] 等于字符串 #cf_span[s] 的长度，而 #cf_span[ci] 等于字符串 #cf_span[s] 中长度为 #cf_span[i] 且由 *相同* 字母组成的子串的数量。子串是字符串 #cf_span[s] 中连续的字符序列。
例如，如果 Stepan 最喜欢的字符串是 "_tttesst_"，那么序列 #cf_span[c] 为：#cf_span[c = [7, 3, 1, 0, 0, 0, 0]]。
Stepan 请你根据给定的序列 #cf_span[c1, c2, ..., cn] 修复他最喜欢的字符串 #cf_span[s]。
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2000]) —— Stepan 最喜欢的字符串的长度。
第二行包含整数序列 #cf_span[c1, c2, ..., cn] (#cf_span[0 ≤ ci ≤ 2000])，其中 #cf_span[ci] 等于字符串 #cf_span[s] 中长度为 #cf_span[i] 且由相同字母组成的子串的数量。
保证输入数据满足答案一定存在。
请输出修复后的 Stepan 最喜欢的字符串。如果有多个答案，允许输出任意一个。字符串应仅包含英文的小写字母。
在第一个测试用例中，Stepan 最喜欢的字符串可以是 "_kkrrrq_"，因为它包含 #cf_span[6] 个长度为 #cf_span[1] 且由相同字母组成的子串（它们分别起始于位置 #cf_span[1], #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[5] 和 #cf_span[6]），#cf_span[3] 个长度为 #cf_span[2] 且由相同字母组成的子串（它们分别起始于位置 #cf_span[1], #cf_span[3] 和 #cf_span[4]），以及 #cf_span[1] 个长度为 #cf_span[3] 且由相同字母组成的子串（它起始于位置 #cf_span[3]）。
## Input
第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2000]) —— Stepan 最喜欢的字符串的长度。第二行包含整数序列 #cf_span[c1, c2, ..., cn] (#cf_span[0 ≤ ci ≤ 2000])，其中 #cf_span[ci] 等于字符串 #cf_span[s] 中长度为 #cf_span[i] 且由相同字母组成的子串的数量。保证输入数据满足答案一定存在。
## Output
请输出修复后的 Stepan 最喜欢的字符串。如果有多个答案，允许输出任意一个。字符串应仅包含英文的小写字母。
[samples]
## Note
在第一个测试用例中，Stepan 最喜欢的字符串可以是 "_kkrrrq_"，因为它包含 #cf_span[6] 个长度为 #cf_span[1] 且由相同字母组成的子串（它们分别起始于位置 #cf_span[1], #cf_span[2], #cf_span[3], #cf_span[4], #cf_span[5] 和 #cf_span[6]），#cf_span[3] 个长度为 #cf_span[2] 且由相同字母组成的子串（它们分别起始于位置 #cf_span[1], #cf_span[3] 和 #cf_span[4]），以及 #cf_span[1] 个长度为 #cf_span[3] 且由相同字母组成的子串（它起始于位置 #cf_span[3]）。
Let $ n $ be the length of the string. Given a sequence $ c = (c_1, c_2, \dots, c_n) $, where $ c_i $ is the number of contiguous substrings of length $ i $ consisting of identical characters.
Define $ x_k $ as the number of maximal contiguous blocks (runs) of identical characters of length exactly $ k $.
Then, for each $ i \in \{1, 2, \dots, n\} $, the number of contiguous substrings of length $ i $ made of identical characters is:
$$
c_i = \sum_{k=i}^{n} (k - i + 1) \cdot x_k
$$
We can recover $ x_k $ from $ c_i $ using backward substitution:
$$
x_n = c_n
$$
$$
x_{n-1} = c_{n-1} - 2x_n
$$
$$
x_{k} = c_k - \sum_{j=k+1}^{n} (j - k + 1) \cdot x_j \quad \text{for } k = n-1, n-2, \dots, 1
$$
Once $ x_k $ is known for all $ k $, construct the string by concatenating $ x_k $ blocks, each of $ k $ identical characters, using distinct letters for distinct blocks (e.g., use 'a', 'b', 'c', ... in order).
Output any such string.
API Response (JSON)
{
"problem": {
"name": "H. Repairing Of String",
"description": {
"content": "Stepan had a favorite string _s_ which consisted of the lowercase letters of the Latin alphabet. After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF795H"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Stepan had a favorite string _s_ which consisted of the lowercase letters of the Latin alphabet.\n\nAfter graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Stepan 有一个最喜欢的字符串 #cf_span[s]，它由拉丁字母的小写字母组成。\n\n毕业后，他决定回忆起这个字符串，但已经过去很久了，所以他现在记不起来了。但 Stepan 记得关于这个字符串的一些信息，即整数序列 #cf_span[c1, c2, ..., cn]，其中 #cf_span[n] 等于字符串 #cf_span[s] 的长度，而 #cf_span[ci] 等于字符串 #cf_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ be the length of the string. Given a sequence $ c = (c_1, c_2, \\dots, c_n) $, where $ c_i $ is the number of contiguous substrings of length $ i $ consisting of identical characters.\n\nDefine...",
"is_translate": false,
"language": "Formal"
}
]
}