TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

68.4% (26/38)

Description

為降低資料儲存的空間或增加資料傳送的速度,編碼是常用的方法。

假設有一個字元集,每個字元出現的頻率是已知的。現在要把每個字元編碼成為一個二元字串(例如把‘A’編碼作101),採用的編碼必須合乎以下條件:一個字元的編碼不可以是另一個字元的前置(prefix)。前置的定義如下:若一個字串s1為另一個字串s2的前置,則從s2的最後一個字元開始,連續刪除一定數量的字元後可以得到s1(s2本身也是s2的前置),舉例而言:如果字元‘A’的編碼是101,而字元‘B’的編碼為01,則‘B’的編碼不為‘A’編碼的前置;如果字元‘C’的編碼為1100,而字元‘D’的是11,則‘D’的編碼是‘C’編碼的前置。以下的編碼方式可以在符合這個條件下給出最經濟的編碼,請找出使用下述方法做最經濟編碼時,一個字元編碼的預期長度。

編碼法
1.如以下所述建立一棵二元樹。
先從字元集選取兩個出現頻率最低的字元作合併,合併後以一個全新的虛擬字元取代這兩個字元,新字元的頻率等於這兩個舊字元頻率的總和,並令這兩個舊字元為此新字元的兩個子樹,左右不拘。重覆以上動作,直至字元集剩下一個字元為止。如下圖(i)到(iv)。

2.再依照以下所述方法將各字元作編碼。
由上一步驟所得之二元樹,將每個內部節點(internal node)連往左子樹的邊(edge)標記為‘0’,連往右子樹的邊標記為‘1’,如下圖(v)所示。一字元的編碼即為從樹根(root)至此字元,經過的每一個邊的標記所成之字串。在此‘a’編碼作000,‘?’編碼作01。


在按照上述的編碼法完成最經濟編碼之後,就可以計算這個字元編碼的預期長度。首先算出每個字元的預期長度 = 編碼長度 × 出現頻率,然後把所有字元的預期長度總合起來,就可以得到此字元編碼的預期長度。下表是上述編碼的計算範例。

Input Format

第一行為一整數n,代表字元集的大小(0<n≤200)。
然後每一個字元分行列出,每行列出一字元外,並列出它出現的頻率,字元與頻率之間以一個空白分隔。(所有字元頻率的總和等於1)

Output Format

預期一個字元編碼的長度。精確至小數點後兩位,小數點後第三位四捨五入。

Sample Input

Sample Input #1:

4
a 0.1
b 0.1
? 0.3
8 0.5

Sample Input #2:

6
* 0.3
b 0.3
< 0.05
H 0.25
( 0.05
h 0.05

Sample Output

Sample Output #1:

1.70

Sample Output #2:

2.25

Hints

Problem Source

原TIOJ1155 / 93全國賽(prob 4)。

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536