English · Original
Chinese · Translation
Formal · Original
Polycarp is mad about coding, that is why he writes Sveta encoded messages. He calls the _median letter_ in a word the letter which is in the middle of the word. If the word's length is even, the median letter is the left of the two middle letters. In the following examples, the median letter is highlighted: _con**t**est_, _i**n**fo_. If the word consists of single letter, then according to above definition this letter is the median letter.
Polycarp encodes each word in the following way: he writes down the median letter of the word, then deletes it and repeats the process until there are no letters left. For example, he encodes the word _volga_ as _logva_.
You are given an encoding _s_ of some word, your task is to decode it.
## Input
The first line contains a positive integer _n_ (1 ≤ _n_ ≤ 2000) — the length of the encoded word.
The second line contains the string _s_ of length _n_ consisting of lowercase English letters — the encoding.
## Output
Print the word that Polycarp encoded.
[samples]
## Note
In the first example Polycarp encoded the word _volga_. At first, he wrote down the letter _l_ from the position 3, after that his word looked like _voga_. After that Polycarp wrote down the letter _o_ from the position 2, his word became _vga_. Then Polycarp wrote down the letter _g_ which was at the second position, the word became _va_. Then he wrote down the letter _v_, then the letter _a_. Thus, the encoding looked like _logva_.
In the second example Polycarp encoded the word _no_. He wrote down the letter _n_, the word became _o_, and he wrote down the letter _o_. Thus, in this example, the word and its encoding are the same.
In the third example Polycarp encoded the word _baba_. At first, he wrote down the letter _a_, which was at the position 2, after that the word looked like _bba_. Then he wrote down the letter _b_, which was at the position 2, his word looked like _ba_. After that he wrote down the letter _b_, which was at the position 1, the word looked like _a_, and he wrote down that letter _a_. Thus, the encoding is _abba_.
Polycarp 热爱编程，因此他编写了 Sveta 编码的消息。他将单词中的_中位字母_定义为位于单词正中间的字母。如果单词长度为偶数，则中位字母是两个中间字母中靠左的那个。在以下示例中，中位字母被高亮显示：_con*t*est_、_i*n*fo_。如果单词仅由一个字母组成，则根据上述定义，该字母即为中位字母。
Polycarp 按以下方式对每个单词进行编码：他写下该单词的中位字母，然后删除它，并重复此过程，直到没有字母剩余。例如，他将单词 _volga_ 编码为 _logva_。
你被给予某个单词的编码 #cf_span[s]，你的任务是解码它。
第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2000]) —— 编码单词的长度。
第二行包含一个长度为 #cf_span[n]、由小写英文字母组成的字符串 #cf_span[s] —— 编码结果。
请输出 Polycarp 编码的原单词。
在第一个示例中，Polycarp 编码了单词 _volga_。首先，他写下位置 #cf_span[3] 的字母 _l_，此时单词变为 _voga_。接着，他写下位置 #cf_span[2] 的字母 _o_，单词变为 _vga_。然后，他写下位于第二个位置的字母 _g_，单词变为 _va_。之后，他写下字母 _v_，再写下字母 _a_。因此，编码结果为 _logva_。
在第二个示例中，Polycarp 编码了单词 _no_。他写下字母 _n_，单词变为 _o_，然后写下字母 _o_。因此，在此示例中，原单词与编码结果相同。
在第三个示例中，Polycarp 编码了单词 _baba_。首先，他写下位于位置 #cf_span[2] 的字母 _a_，此时单词变为 _bba_。接着，他写下位于位置 #cf_span[2] 的字母 _b_，单词变为 _ba_。然后，他写下位于位置 #cf_span[1] 的字母 _b_，单词变为 _a_，并写下该字母 _a_。因此，编码结果为 _abba_。
## Input
第一行包含一个正整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2000]) —— 编码单词的长度。第二行包含一个长度为 #cf_span[n]、由小写英文字母组成的字符串 #cf_span[s] —— 编码结果。
## Output
请输出 Polycarp 编码的原单词。
[samples]
## Note
在第一个示例中，Polycarp 编码了单词 _volga_。首先，他写下位置 #cf_span[3] 的字母 _l_，此时单词变为 _voga_。接着，他写下位置 #cf_span[2] 的字母 _o_，单词变为 _vga_。然后，他写下位于第二个位置的字母 _g_，单词变为 _va_。之后，他写下字母 _v_，再写下字母 _a_。因此，编码结果为 _logva_。在第二个示例中，Polycarp 编码了单词 _no_。他写下字母 _n_，单词变为 _o_，然后写下字母 _o_。因此，在此示例中，原单词与编码结果相同。在第三个示例中，Polycarp 编码了单词 _baba_。首先，他写下位于位置 #cf_span[2] 的字母 _a_，此时单词变为 _bba_。接着，他写下位于位置 #cf_span[2] 的字母 _b_，单词变为 _ba_。然后，他写下位于位置 #cf_span[1] 的字母 _b_，单词变为 _a_，并写下该字母 _a_。因此，编码结果为 _abba_。
Let $ n $ be the length of the encoded string $ s $, and let $ s[0..n-1] $ be the encoded string (0-indexed).
Define the decoding process as reconstructing the original word $ t $ of length $ n $, such that applying Polycarp’s encoding procedure to $ t $ yields $ s $.
Polycarp’s encoding procedure:
- At each step, extract the **median letter** of the current string, where:
- If the current length $ m $ is odd, the median is at index $ \left\lfloor \frac{m-1}{2} \right\rfloor $.
- If $ m $ is even, the median is at index $ \frac{m}{2} - 1 $.
- Remove the median letter and append it to the encoded result.
To decode, we reverse this process:
- We are given the sequence of median letters $ s[0], s[1], \dots, s[n-1] $, in the order they were extracted.
- We reconstruct the original string $ t $ by simulating the reverse: starting with an empty list, and at step $ i $, insert $ s[i] $ into the position that would have been the median position **at that step** in the original encoding.
Let $ t $ be an initially empty list (or array) of length $ n $.
Let positions be the indices of the original string $ t $, from $ 0 $ to $ n-1 $.
We simulate the encoding process in reverse:
At step $ i = 0 $ to $ n-1 $:
- The current string length is $ m = n - i $.
- The median index in a string of length $ m $ is:
$$
\text{median\_idx}(m) =
\begin{cases}
\left\lfloor \frac{m-1}{2} \right\rfloor & \text{if } m \text{ is odd} \\
\frac{m}{2} - 1 & \text{if } m \text{ is even}
\end{cases}
$$
This simplifies to: $ \text{median\_idx}(m) = \left\lfloor \frac{m-1}{2} \right\rfloor $ for all $ m \geq 1 $.
We maintain a list of available positions in the original string $ t $: initially $ [0, 1, 2, \dots, n-1] $.
At step $ i $, we:
- Compute the median index in the current string of length $ m = n - i $: $ p = \left\lfloor \frac{m - 1}{2} \right\rfloor $.
- Take the $ p $-th available position (0-indexed) from the list of available positions.
- Assign $ s[i] $ to that position in $ t $.
- Remove that position from the list of available positions.
After processing all $ n $ steps, $ t $ is the decoded word.
**Formal Output:**
Let $ s \in \Sigma^n $, $ \Sigma = \{a, b, \dots, z\} $, $ n \in \mathbb{N} $, $ 1 \leq n \leq 2000 $.
Let $ P = [0, 1, 2, \dots, n-1] $ (list of available indices).
For $ i = 0 $ to $ n-1 $:
- Let $ m = n - i $
- Let $ p = \left\lfloor \frac{m - 1}{2} \right\rfloor $
- Let $ pos = P[p] $
- Set $ t[pos] = s[i] $
- Remove $ P[p] $ from $ P $
Then output $ t $.
API Response (JSON)
{
"problem": {
"name": "B. Decoding",
"description": {
"content": "Polycarp is mad about coding, that is why he writes Sveta encoded messages. He calls the _median letter_ in a word the letter which is in the middle of the word. If the word's length is even, the medi",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF746B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Polycarp is mad about coding, that is why he writes Sveta encoded messages. He calls the _median letter_ in a word the letter which is in the middle of the word. If the word's length is even, the medi...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Polycarp 热爱编程，因此他编写了 Sveta 编码的消息。他将单词中的_中位字母_定义为位于单词正中间的字母。如果单词长度为偶数，则中位字母是两个中间字母中靠左的那个。在以下示例中，中位字母被高亮显示：_con*t*est_、_i*n*fo_。如果单词仅由一个字母组成，则根据上述定义，该字母即为中位字母。\n\nPolycarp 按以下方式对每个单词进行编码：他写下该单词的中位字母，然后删除它...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ be the length of the encoded string $ s $, and let $ s[0..n-1] $ be the encoded string (0-indexed).\n\nDefine the decoding process as reconstructing the original word $ t $ of length $ n $, su...",
"is_translate": false,
"language": "Formal"
}
]
}