Задача 150
Поиск под-треугольника с наименьшей суммой в треугольном массиве

В треугольном массиве положительных и отрицательных целых чисел мы хотим найти такой под-треугольник, чтобы сумма всех чисел, из которых он состоит, была по возможности меньшей.

В примере ниже отчетливо видно, что выделенный треугольник удовлетворяет условию, т.к. его сумма равна −42.

Мы собираемся сделать такой треугольный массив с одной тысячей строк, поэтому нам необходимо сгенерировать 500500 псевдослучайных числа s_(k) в диапазоне ±2^(19), воспользовавшись определенным типом генератора случайных чисел (известен как "линейный конгруэнтный генератор") следующим образом:

t := 0
при k = 1 до k = 500500:
    t := (615949*t + 797807) modulo 2^(20)
    s_(k) := t−2^(19)

Таким образом: s_(1) = 273519, s_(2) = −153582, s_(3) = 450905 и т.д.

После этого наш треугольный массив формируется из полученных псевдо-случайных чисел следующим образом:

s_(1)
s_(2)  s_(3)
s_(4)  s_(5)  s_(6) 
s_(7)  s_(8)  s_(9)  s_(10)
...

Под-треугольники можно начинать с любого элемента массива и продолжать их вниз настолько, насколько это необходимо (выбирая два элемента на следующей строке, три элемента на идущей через одну строке и т.д.).
"Сумма под-треугольника" определяется как сумма всех его элементов.
Найдите наименьшую возможную сумму под-треугольника.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net