e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ІІІ етап Всеукраїнської олімпіади з інформатик в Житомирській обл. 2019-2020

Пирамида из чисел

Пирамида состоит из n строк. Первая строка расположена внизу и содержит n чисел, вторая строка содержит n - 1 чисел, третья n - 2 и так далее. Последняя (верхняя) строка представлена одним числом.

Известны n чисел первой строки. Вторая строка формируется на основе чисел первой строки, третья строка - на основе второй и так далее.

Каждый элемент четной строки определяется как последняя цифра числа - минимума двух чисел: суммы элементов предыдущей строки, расположенных левее текущего элемента и суммы элементов предыдущей строки, расположенных правее текущего элемента.

Каждый элемент нечетной строки (кроме первой, числа которого заданы) вычисляется так же за исключением того, что вместо минимума находится максимум.

Найдите сумму всех чисел пирамиды.

Входные данные

Первая строка содержит количество чисел n в первой строке пирамиды. Вторая строка содержит эти числа. Все числа целые в диапазоне от 0 до 50 000.

Выходные данные

Выведите сумму всех чисел пирамиды.

Z1_3.jpg

Пояснение

4 строка: min{9,8} = 8

3 строка: max{5, 1 + 8} = 9, max{5 + 1, 8} = 8

2 строка: min{5, 6 + 7 + 8} = 5, min{5 + 6, 7 + 8} = 11, min{5 + 6 + 7, 8} = 8

1 строка: числа заданы в условии задачи

Ответ: 8 + 9 + 8 + 5 + 1 + 8 + 5 + 6 + 7 + 8 = 65

Time limit 4 second
Memory limit 128 MiB
Input example #1
4
5 6 7 8
Output example #1
65
Source 2020 XXXIV областная олимиіада по информатике, Житомир