|
2010-2011
|
Реверсивная игра (100 баллов)
Недавно компания “Gold & Silver Software” анонсировала выход новой игры для мобильных телефонов под названием «Реверсивная игра». Игра является пошаговой и предназначена для одного игрока. Игровое поле представляет собой горизонтальную полосу, разделенную на N клеток, пронумерованных целыми числами от 1 до N слева направо. Каждая клетка может быть черного либо белого цвета. Целью игры является приведение всей полосы к белому либо к черному цвету за минимальное количество ходов. За один ход игрок может выделить произвольное количество подряд идущих клеток и программа изменит цвет выделенных клеток на противоположный. То есть все выделенные клетки черного цвета станут белыми, а белые выделенные клетки станут черными.
Рисунок №1. Описание второго примера.
Выше приведен пример игры, при которой за два хода можно получить полосу черного цвета. Ваша задача - определить минимальное количество ходов, которое потребуется для того, чтобы из заданной полосы получить одноцветную. Входные данные Первая строка входного файла содержит ровно одно целое число N (1 ≤ N ≤ 1000). Вторая строка содержит N целых чисел. Каждое i-е число соответствует цвету i-й клетки и равно 0 (для черного цвета) либо 1 (для белого цвета). Выходные данные Единственная строка выходного файла должна содержать одно целое число – минимальное количество ходов, необходимое для приведения полосы к одному цвету.
|
