「CF83E」Two Subsequences

2015年2月1日4,84029

On an IT lesson Valera studied data compression. The teacher told about a new method, which we shall now describe to you.

Let {a1, a2, …, an} be the given sequence of lines needed to be compressed. Here and below we shall assume that all lines are of the same length and consist only of the digits 0 and 1. Let’s define the compression function:

  • f(empty sequence) = empty string
  • f(s) = s.
  • f(s1, s2) =  the smallest in length string, which has one of the prefixes equal to s1 and one of the suffixes equal to s2. For example, f(001, 011) = 0011, f(111, 011) = 111011.
  • f(a1, a2, …, an) = f(f(a1, a2, an - 1), an). For example, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Valera faces a real challenge: he should divide the given sequence {a1, a2, …, an} into two subsequences{b1, b2, …, bk} and {c1, c2, …, cm}, m + k = n, so that the value of S = |f(b1, b2, …, bk)| + |f(c1, c2, …, cm)| took the minimum possible value. Here |p| denotes the length of the string p.

Note that it is not allowed to change the relative order of lines in the subsequences. It is allowed to make one of the subsequences empty. Each string from the initial sequence should belong to exactly one subsequence. Elements of subsequences b and c don’t have to be consecutive in the original sequence a, i. e. elements of b and c can alternate in a (see samples 2 and 3).

Help Valera to find the minimum possible value of S.

Input

The first line of input data 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.

Output

Print a single number — the minimum possible value of S.

Sample test(s)
input

output

input

output

input

output

Note

Detailed answers to the tests:

  • The best option is to make one of the subsequences empty, and the second one equal to the whole given sequence. |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
  • The best option is: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
  • The best option is: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 1

题解

xhr神犇的cf题目泛做中有详细题解,第42页

 

avatar
29 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
提醒
trackback

clutch bottega veneta

Mas eu estava brincando com meu marido, e fazê-lo para ele, tanto do nosso deleite.

trackback

giuseppe zanotti design outlet neum¨¹nster

Supreme Post¡­Tanks 4 sharing!

trackback

ray ban 3025 hangover

Super! I love these delicate posts.

trackback

wedding dress patterns plus size free

Nice post.

trackback

new coach bags 2014

nice site, all posts are very nice.

trackback

herve leger gold foil jewellery

I love this post !! totally kewl!!! Well done! I’m coming back to this one ¡­

trackback

ray ban aviators black frame green lens kullananlar

wonderful post, thank you.

trackback

halter camo wedding dresses

Thanks for such a great post and the review, I am totally impressed!

trackback

coach discount uk

more wait .. ;)

trackback

mens louis vuitton resale

thanks, nice post.

trackback

giuseppe zanotti nyc showroom address

Interesting site.

trackback

gafas ray ban 4068

Thanks ! Supper Post !!

trackback

ray-ban wayfarer folding sunglasses rb4105

JUST AWESOME!!!!!!Gr888 Job

trackback

wedding dresses 6th ave tacoma

Thanks for such a great post and the review, I am totally impressed!

trackback

executive coach repair

So cool! Thanks.

trackback

nike air max 180 london

a very successful site. Also very revealing article. Thanks to the contributors.

trackback

vintage wedding dresses in london

Thanks for sharing this, its great :)

trackback

nike coach catalog

I greatly appreciate all the info I’ve read here. I will spread the word about your blog to other people. Cheers.

trackback

authentic herve leger dress sale australia

Thanks. Very nice post. Your web site is very beautiful.

trackback

coach shoes loafers

Excellent post. Thanks.

trackback

ray ban original wayfarer asian fit

Good post, I always like them.

trackback

mens louis vuitton wallet

Thank for very good work!

trackback

giuseppe zanotti black and white stripe

wonderful post, thank you.

trackback

lace wedding dresses for sale

nice post,thanks for share.

trackback

ray ban 4039 polarizado

This is good, helps me a lot, thanks.

trackback

champagne colored ball gown wedding dresses

This post is so help to me! Thanks for share.

trackback

ray ban 3025 gold l0205

Great post! Thx.

trackback

coach legacy purses

Thanks. Very nice post. Your web site is very beautiful.

trackback

coach poppy purse purple

hey good job man.