Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
gold

Задача Gold
Знаходячись  на вершины гори потрібно спуститься вниз. Від  вершини до основи збудовано  оригинальні сходи: з кожної сходинки можна зробити крок вниз
 на наступний рівень тільки по діагоналі вправо чи по діагоналі вліво. Число рівній на горі >1 и <=100. На кожній сходинці знаходится  ціле  число  золотих  монет (від 0 до 99). Напишіть програму, яка обчислить  найбільшу  суму  монет,  яку  можна зібрати на шляху від вершини до основи. Ось приклад такой гори:
    5         
   5 4       
  2 1 8     
 1 7 3 4     
4 5 6 1 1   
Технічні умови. Програма читає з клавіатури кількість рівнів, а далі - кількість монет на кожній сходинці кожного рівня. Всі числа записано в один рядок через пропуск. Програма виводить на екран єдине число - максимально можливу кількість монет на маршруті

Приклад
Введення
5 5 4 2 1 8 1 7 3 4 4 5 6 1 1

Виведення
25


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"