e-olymp 5741. Стек шаров

Задание

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

Участник должен выбрать набор шаров, и его призом будет сумма чисел на них. Участник может взять шар, только если он берет все шары, находящиеся непосредственно над ним. Это может потребовать снятия дополнительных шаров по описанному правилу. Участник может не взять ни одного шара, в таком случае его приз будет равным нулю.

Директор телешоу заинтересован в том, чтобы участник получил максимальный приз для заданного стека. Так как он является Вашим босом, то попросил Вас решить эту задачу.

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

Каждый тест задается в нескольких строках. Первая строка содержит количество рядов [latex]N (1 ≤ N ≤ 1000)[/latex] в стеке. [latex]i[/latex]-ая из следующих [latex]N [/latex] строксодержит [latex]i[/latex] целых чисел [latex]B_{ij} (-10^{5}≤ B_{ij}≤ 10^{5}[/latex] для [latex]1 ≤ j ≤ i ≤ N)[/latex]; значение [latex]B_{ij}[/latex] равно числу, записанному на [latex]j[/latex]-ом шаре в [latex]i[/latex]-ом ряду стека (первый ряд — самый верхний, в каждом ряду первым шаром является самый левый).

За последним тестом следует строка, содержащая один ноль.

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

Для каждого теста вывести в отдельной строке целое число — максимальный приз, который может получить участник игры для заданного стека шаров.

Тесты

Ввод Вывод
4
3
-5 3
-8 2 -8
3 9 -2 7
2
-2
1 -10
3
1
-5 3
6 -4 1
0
7
0
6
3
7
2 1
3 4 6
2
5
9 2
1
2
0
23
16
2

Код

Решение

Иницианилизируем  двумерный массив [latex]s[/latex], который будет играть роль нашего стека. При считывании массива будем сразу суммировать предыдущие шары. Далее будем хранить в нижних шарах стека сумму всех верхних и при обходе с помощью максимума находить оптимальный путь. Остаётся только найти максимум среди получившихся сумм. Это и будет нашим ответом.

Ссылки

  1. Условие на e-olymp
  2. Код на Ideone

Ю 4.17

Постановка задачи

В массиве [latex]A(n)[/latex] найти и напечатать номера (индексы) локальных максимумов, то есть таких [latex]a_{i}[/latex], что [latex]a_{i-1}<x_{i}>a_{i+1}[/latex].

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

Количество значений и сами значения

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

Индексы локальных максимумов

Тесты

Количество значений Значения Результат
1 6 2 4 6 1 3 7 5 2
2 7 3 1 6 2 8 5 7 2, 4
3 10 2 5 8 3 5 6 9 7 1 4 2, 6

Решение

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную n для хранения размера массива. Далее создаем массив типа double. Для нахождения локальных максимумов x[i] создаем цикл for, в котором при каждой итерации будем проверять, являются ли значения локальными максимумами. Если значение удовлетворяет условие, выводим на экран индекс этого значения. Например, в первом тесте мы вводим количество значений 6, сами значения 2 4 6 1 3 7 5 и нашим результатом оказывается число с индексом 2, т.е. число 6. Так как числа 4 и 1 меньше 6, наше значение будет удовлетворять условие.