| Автор: | И. Туфанов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
| Выходной файл: | output.txt |
Биллиардные шары сложены на столе в форме пирамиды. В первом ряду пирамиды находится один шар. В каждом последующем — на один больше, чем в предыдущем. В последнем ряду находится N шаров.
Назовем 1-внешними шары на последнем ряду пирамиды, а также самый левый и самый правый шары в каждом ряду. При удалении 1-внешних шаров размер пирамиды уменьшается. 1-внешние шары новой пирамиды мы будем называть 2-внешними. Продолжая процесс до тех пор, пока пирамида не исчезнет, можно определить k-внешние шары. Шары бывают двух видов: одноцветные и полосатые. Будем называть пирамиду хорошей, если при обходе 1-внешних шаров по периметру встретится не более одной пары соседних шаров одного вида. Будем называть пирамиду замечательной, если это свойство выполняется для t-внешних шаров для любого t.
В данной пирамиде за одно действие разрешается поменять местами два любых шара. Требуется найти минимальное количество действий, за которое можно превратить пирамиду в замечательную, либо установить, что это невозможно.
Если пирамиду можно сделать замечательной, то выведите одно число — минимальное количество необходимых для этого действий, в противном случае выведите − 1.
В приведенном примере средний шар меняется местами с нижним правым (1 действие).
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|