TopCoder

User's AC Ratio

98.6% (285/289)

Submission's AC Ratio

77.1% (391/507)

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,為輸入運行長度編碼對應的原始字串,測資保證解壓縮後的字串長度不超過 105

Sample Input 1

mi4si2si3pi

Sample Output 1

missssissipppi

Sample Input 2

14ops

Sample Output 2

oooooooooooooops

Hints

1|C|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