Задача D. Биллиардная пирамида

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Биллиардные шары сложены на столе в форме пирамиды. В первом ряду пирамиды находится один шар. В каждом последующем — на один больше, чем в предыдущем. В последнем ряду находится N шаров.

Назовем 1-внешними шары на последнем ряду пирамиды, а также самый левый и самый правый шары в каждом ряду. При удалении 1-внешних шаров размер пирамиды уменьшается. 1-внешние шары новой пирамиды мы будем называть 2-внешними. Продолжая процесс до тех пор, пока пирамида не исчезнет, можно определить k-внешние шары. Шары бывают двух видов: одноцветные и полосатые. Будем называть пирамиду хорошей, если при обходе 1-внешних шаров по периметру встретится не более одной пары соседних шаров одного вида. Будем называть пирамиду замечательной, если это свойство выполняется для t-внешних шаров для любого t.

В данной пирамиде за одно действие разрешается поменять местами два любых шара. Требуется найти минимальное количество действий, за которое можно превратить пирамиду в замечательную, либо установить, что это невозможно.

Формат входного файла

В первой строке входного файла находится чило N. Затем следуют N строк с описанем пирамиды. В i-ой строке находится i чисел 1 или 0, разделенных произвольным количеством пробелов. Они обозначают вид шара в i-м ряду (1 - одноцветный, 0 - полосатый).

Формат выходного файла

Если пирамиду можно сделать замечательной, то выведите одно число — минимальное количество необходимых для этого действий, в противном случае выведите  − 1.

В приведенном примере средний шар меняется местами с нижним правым (1 действие).

Ограничения

1 ≤ N ≤ 50

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
   1
  0 0 
 1 0 1  
1 0 1 1
1

0.064s 0.012s 13