Codeforces Global Round 2 |
---|
Закончено |
У Павла есть набор палок, с длинами равными степеням двойки.
У него есть $$$a_0$$$ палок длины $$$2^0 = 1$$$, $$$a_1$$$ палок длины $$$2^1 = 2$$$, ..., $$$a_{n-1}$$$ палок длины $$$2^{n-1}$$$.
Павел хочет составить из этих палок наибольшее количество треугольников, с площадью строго больше нуля, каждая палка при этом может содержаться не более чем в одном треугольнике.
Запрещено ломать палки, а также каждый треугольник должен состоять из ровно трех палок.
Найдеите наибольшее количество треугольников, которое может составить Павел.
Первая строка содержит единственное целое число $$$n$$$ — количество различных длин палок, которые есть у Павла ($$$1 \leq n \leq 300\,000$$$).
Вторая строка содержит $$$n$$$ целых чисел, разделенных пробелами, $$$a_0$$$, $$$a_1$$$, ..., $$$a_{n-1}$$$ ($$$1 \leq a_i \leq 10^9$$$), $$$a_i$$$ обозначает количество палок длины $$$2^i$$$.
Выведите одно целое число — максимальное количество невырожденных треугольников, которые может составить Павел.
5 1 2 2 2 2
3
3 1 1 1
0
3 3 3 3
3
В первом примере Павел может, например, составить такой комплект треугольников (перечислены длины сторон треугольника):
$$$(2^0, 2^4, 2^4)$$$, $$$(2^1, 2^3, 2^3)$$$, $$$(2^1, 2^2, 2^2)$$$.
Во втором примере Павел не может составить ни одного треугольника.
В третьем примере Павел может, например, составить такой комплект треугольников (перечислены длины сторон треугольника):
$$$(2^0, 2^0, 2^0)$$$, $$$(2^1, 2^1, 2^1)$$$, $$$(2^2, 2^2, 2^2)$$$.
Название |
---|