Алгоритмы и программы на С++. Решение задачи 7 Главы 2

Алгоритмы на С++

матрицы

Решение задачи 7 главы 2

Вам нужно разбить бронированные плиты на оборонной башне противника, которая в плане имеет вид N-угольника. Для каждой стороны известно количество прикрывающих ее плит. Стрельба ведется из специальной двуствольной пушки - она ездит по рельсам вокруг башни и за один выстрел разбивает (по вашему желанию) или две плиты на одной стороне башни, или по одной плите на двух соседних сторонах. Найдите наименьшее число выстрелов, необходимых для разрушения всех плит.
Вход. В первой строке текста - количество тестов M, в каждой из следующих M строк - тест. Тест задает число сторон N (3\le N\le 10^7) и N целых неотрицательных чисел - количества плит на сторонах.

к списку задач