回分類題庫
d093: 2.跑長編碼與資料壓縮
關鍵字: 106年彰雲嘉區複賽

測資點 : 3 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 113 Times / 93 Users | Submit : 422 Times / 105 Users | Accepted rate : 89%
題目加入時間 : 2018-09-06 14:00

Content: 简体中文

跑長編碼(Run-Length Coding)是一種常見的資料壓縮技術,特別適用於字串樣式重複頻率高的情況。其編碼格式為(重複樣式,重複次數),例如一個二元字串 0000001111111001111可編碼為(0,6) (1,7) (0,2) (1,4),因為樣式0 重複了 6 次,而之後的樣式1則重複了 7 次。

寫一個程式來壓縮一個長位元串,並輸出壓縮比率(壓縮後位元個數除以原位元個數,四捨五入到整數百分比)。重複位元的長度用3個位元來表示(最大連續長度為7),放在重複位元的後面,形成一個4位元的碼字(code word)。輸入是一長串連續的位元(長度小於500),不可有0、1之外的字元、數字、或空格。輸出則是編碼後的4位元碼字,可能是(0,連續0的長度)或(1,連續1的長度),兩個碼字之間用一個空格分開,最後是四捨五入的壓縮率。如果輸入不是一個2進制位元串,直接輸出-1。 

Input:

輸入資料中第一列為一整數n,代表接下來有n組測試資料。
第二列開始共有n列,每列有一個二元字串。

Output:

輸出跑長編碼後的數個4位元碼字以及壓縮率,各碼字與壓縮率皆用空格分開。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
00010000000111111101111111
11111100000000000000111111111111110000
0011  1111100000101010
HINET0800000123

Sample Output :

0011 1001 0111 1111 0001 1111 92
1110 0111 0111 1111 1111 0100 63
-1
-1

Hint :

Author :

106年彰雲嘉區複賽 (管理員:sagit)

  Solve it!   Status Forum