2188 . A. 字串解壓縮

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

syl123456

User's AC Ratio

98.6% (285/289)

Submission's AC Ratio

77.1% (391/507)

Tags

TOI TOI-pre 2020-TOI-pre

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
Submit
Back to Top