{"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. 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_.\n\nFor example, if the Stepan's favorite string is equal to \"_tttesst_\", the sequence _c_ looks like: _c_ = \\[7, 3, 1, 0, 0, 0, 0\\].\n\nStepan asks you to help to repair his favorite string _s_ according to the given sequence _c_1, _c_2, ..., _c__n_.\n\n## Input\n\nThe first line contains the integer _n_ (1 ≤ _n_ ≤ 2000) — the length of the Stepan's favorite string.\n\nThe 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.\n\nIt is guaranteed that the input data is such that the answer always exists.\n\n## Output\n\nPrint 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.\n\n[samples]\n\n## Note\n\nIn 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).","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_span[s] 中长度为 #cf_span[i] 且由 *相同* 字母组成的子串的数量。子串是字符串 #cf_span[s] 中连续的字符序列。\n\n例如，如果 Stepan 最喜欢的字符串是 \"_tttesst_\"，那么序列 #cf_span[c] 为：#cf_span[c = [7, 3, 1, 0, 0, 0, 0]]。\n\nStepan 请你根据给定的序列 #cf_span[c1, c2, ..., cn] 修复他最喜欢的字符串 #cf_span[s]。\n\n第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2000]) —— Stepan 最喜欢的字符串的长度。\n\n第二行包含整数序列 #cf_span[c1, c2, ..., cn] (#cf_span[0 ≤ ci ≤ 2000])，其中 #cf_span[ci] 等于字符串 #cf_span[s] 中长度为 #cf_span[i] 且由相同字母组成的子串的数量。\n\n保证输入数据满足答案一定存在。\n\n请输出修复后的 Stepan 最喜欢的字符串。如果有多个答案，允许输出任意一个。字符串应仅包含英文的小写字母。\n\n在第一个测试用例中，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]）。\n\n## Input\n\n第一行包含整数 #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] 且由相同字母组成的子串的数量。保证输入数据满足答案一定存在。\n\n## Output\n\n请输出修复后的 Stepan 最喜欢的字符串。如果有多个答案，允许输出任意一个。字符串应仅包含英文的小写字母。\n\n[samples]\n\n## Note\n\n在第一个测试用例中，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]）。","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 $ x_k $ as the number of maximal contiguous blocks (runs) of identical characters of length exactly $ k $.\n\nThen, for each $ i \\in \\{1, 2, \\dots, n\\} $, the number of contiguous substrings of length $ i $ made of identical characters is:\n$$\nc_i = \\sum_{k=i}^{n} (k - i + 1) \\cdot x_k\n$$\n\nWe can recover $ x_k $ from $ c_i $ using backward substitution:\n$$\nx_n = c_n\n$$\n$$\nx_{n-1} = c_{n-1} - 2x_n\n$$\n$$\nx_{k} = c_k - \\sum_{j=k+1}^{n} (j - k + 1) \\cdot x_j \\quad \\text{for } k = n-1, n-2, \\dots, 1\n$$\n\nOnce $ 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).\n\nOutput any such string.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF795H","tags":["constructive algorithms","math"],"sample_group":[["6\n6 3 1 0 0 0","kkrrrq"],["4\n4 0 0 0","abcd"]],"created_at":"2026-03-03 11:00:39"}}