eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

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

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

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

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Z1_3.jpg

Nümunə

Giriş verilənləri #1
4
5 6 7 8
Çıxış verilənləri #1
65

Qeyd

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

Mənbə 2020 XXXIV областная олимиіада по информатике, Житомир