e522: 106 彰雲嘉區複賽 - Q2 跑長編碼與資料壓縮
Tags : 106學年度 小崴 彰雲嘉 複賽 資訊學科能力
Accepted rate : 68人/77人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-29 15:10

Content

二、跑長編碼與資料壓縮 ( 10分 )

   

    跑長編碼(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。

 

* 測資均為官方測資

* 為模擬正式競賽,WA 時 不公開正確答案!

* 加油~ !

Input

輸入資料中第一列為一整數n,代表接下來有n組測試資料。

第二列開始共有n列,每列有一個二元字串。

Output

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

 

Sample Input #1
4
00010000000111111101111111
11111100000000000000111111111111110000
0011  1111100000101010
HINET0800000123
Sample Output #1
0011 1001 0111 1111 0001 1111 92%
1110 0111 0111 1111 1111 0100 63%
-1
-1
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (50%): 1.0s , <1K
不公開 測資點#1 (50%): 1.0s , <1K
Hint :
Tags:
106學年度 小崴 彰雲嘉 複賽 資訊學科能力
出處:
106彰雲嘉資訊學科能力複賽 [管理者:
jackyname1@g... (☆♬○♩程式家小崴●♪✧♩)
]


ID User Problem Subject Hit Post Date
22792
joeliao (RRRrrrr!!!)
e522
C++ 基本
203 2020-10-02 16:53