Codeforces Beta Round 72 (Div. 1 Only) |
---|
Закончено |
На уроке информатики Валерий изучал сжатие данных. Учитель рассказал новый метод, который мы сейчас вам опишем.
Пусть {a1, a2, ..., an} — данная последовательность строк, которую необходимо сжать. Здесь и далее будем считать, что все строки имеют одинаковую длину и состоят только из символов 0 и 1. Определим функцию сжатия:
Перед Валерой стоит серьезная задача — разделить данную последовательность {a1, a2, ..., an} на две подпоследовательности {b1, b2, ..., bk} и {c1, c2, ..., cm}, m + k = n, так, чтобы величина S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.
Обратите внимание, что запрещается менять относительный порядок строк в подпоследовательностях. Разрешается делать одну из подпоследовательностей пустой. Каждый элемент исходной последовательности должен принадлежать ровно одной из получившихся подпоследовательностей. Элементы подпоследовательностей b и c не обязательно должны идти подряд в исходной последовательности a, то есть они могут чередоваться (смотрите примеры 2 и 3).
Помогите Валере найти минимальное возможное значение S.
В первой строке входных данных содержится целое число n — количество строк (1 ≤ n ≤ 2·105). Далее в n строках даны элементы последовательности — строки длиной от 1 до 20 символов, состоящие только из символов 0 и 1. На i + 1 строке входных данных находится i-ый член последовательности. Элементы последовательности разделены исключительно символом перевода строки. Гарантируется, что все строки имеют одинаковую длину.
Выведите единственное число — минимально возможное значение S.
3
01
10
01
4
4
000
111
110
001
8
5
10101
01010
11111
01000
10010
17
Подробные ответы к тестам:
Название |
---|