A "bit-string" is a series of 0 and 1 forming a string, ex: 0011101110. A bit-string of length L is simply a bit-string that has exactly L digits.
The "Concatenation" of two bit-strings S1 and S2 is the shortest bit-string that has S1 as prefix and S2 as suffix. ex: The concatenation of "011011" and "101100" is "01101100"; the concatenation of "101111" and "111" is "101111"; the concatenation of "001100" and "0110" is "001100110".
The concatenation of several bit-strings S1, S2 ... Sk can be recursively defined as the concatenation of first k-1 strings, concatenated with the last string Sk
Consider a sequence A of bit-strings with equal length L, we want to split A into two subsequence (of bit-strings) B and C. That is, we divide all elements in A into two sets (possibly of different size, and possibly one set is empty), then arrange the elements according to their original orders in sequence A, thus forming two subsequence B and C.
The cost of the subsequence B / C is simply the length of the concatenation of all strings in B / C. Now given A, find for all possible division of elements, the minimum sum of cost for subsequence B and C.
There may multiple testcases.
The first line of each testcase contains an integer n — the number of strings (1 ≤ n ≤ 2·105). Then on n lines follow elements of the sequence — strings whose lengths are from 1 to 20 characters, consisting only of digits 0 and 1. The (i + 1)-th input line contains the i-th element of the sequence. Elements of the sequence are separated only by a newline. It is guaranteed that all lines have the same length.
For each testcase, print a single number — the minimum possible sum of costs.
3 01 10 01 4 000 111 110 001 5 10101 01010 11111 01000 10010
4 8 17
Migrated from old NTUJ.
Codeforce 83E
| No. | Testdata Range | Score |
|---|