Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Fixing Codes
Description A binary string is a string of characters from the set {0, 1}. A code is a multiset of binary strings (i.e., a string can be repeated arbitrary number of times). A fixed code is a code that none of its strings is a prefix of another string. We say that a code A = {a1, a2, . . . , an} is extended to code B = {b1, b2, . . . , bn} if and only if for 1 <= i <= n, ai be a prefix of bi. The cost of this extension is where |ai| is the number of characters in ai.
For this problem you are given a fixed code C, and a new binary string s. You have to find the minimum needed cost to extend the code C ∪ {s} into a fixed code. In other words, you are to append the minimum number of bits to zero or more codes in C ∪ {s} to make it a fixed code. Input The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test cases in the input. For 1 ≤ i ≤ t the line i+1 consists a nonzero number of binary strings. The number of binary strings in each line is at most 41, and the length of each binary string is no more than 40 characters. The last string in each line stands for the new incoming string s and the other strings in that line make the fixed code of the relevant test case.
Output The output consists m lines. The solution to ith test case should be written in the line i of the output. Sample Input 2 001 01 00 000 001 010 011 100 101 110 1 Sample Output 1 2 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator