TopCoder

User's AC Ratio

98.8% (241/244)

Submission's AC Ratio

77.6% (346/446)

Tags

Description

運行長度編碼(run-length encoding)為一字串壓縮方式,針對一給定的原始字串 $S$,若 $S$ 中有一子字串由 $t$ 個字元 $x$ 構成且該子字串的前一個與後一個字元皆非 $x$,則會以 tx 表示該子字串。若要壓縮的子字串僅為一個字元(即 $t = 1$),則會將 $1$ 省略以讓儲存空間更節省。舉例來說,aaabcccccccccccbaba 從最前面開始 a 連續出現 $3$ 次,b 出現 $1$ 次,c 出現 $11$ 次⋯,因此經過長度編碼後可以表示為 3ab11cbaba。假設構成原始字串的字元僅有 $26$ 個小寫英文字母,請撰寫一解碼器,將長度編碼過後的字串 $C$ 還原為原始字串 $S$。

Input Format

輸入為一行字串 $C$ 代表長度編碼過後的字串,長度至多 $1000$。原始字串僅由 $26$ 個小寫英文字母構成,每個字母連續出現的次數至多 $100$。

Output Format

輸出一行字串 $S$,為輸入運行長度編碼對應的原始字串,測資保證解壓縮後的字串長度不超過 $10^ 5$。

Sample Input 1

mi4si2si3pi

Sample Output 1

missssissipppi

Sample Input 2

14ops

Sample Output 2

oooooooooooooops

Hints

• $1 \leq |C| \leq 1000$。
• $C$ 僅由小寫英文字元 a-z 以及字元 0-9 組成。
• $C$ 是一個合法的長度編碼字串,意即 $C$ 是由 $S$ 經過長度編碼壓縮所得的結果。
• $S$ 僅由字元 a-z 組成。
• $S$ 中任意字母連續出現次數不超過 $100$。

本題共有二組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆
需答對才會獲得該組分數。
1. ($40\%$) 編碼前字串每個字元連續出現的次數至多為 $9$。
2. ($60\%$) 無額外限制。

Problem Source

2020 TOI 入營考
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 編碼前字串每個字元連續出現的次數至多為 $9$。 40
2 0~29 無額外限制。 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 1 2
3 1000 524288 65536 1 2
4 1000 524288 65536 1 2
5 1000 524288 65536 1 2
6 1000 524288 65536 1 2
7 1000 524288 65536 1 2
8 1000 524288 65536 1 2
9 1000 524288 65536 1 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2