e-olimp 693. Минимум в стеке

Задача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из стека. После выполнения каждой операции найдите наименьшее число, которое находится в стеке. Сложите все полученные числа и получите ответ. Если после некоторой операции стек оказался пуст, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как стек пуст, то не выполняйте его.

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

Входные данные генерируются в самой программе. На вход подаются параметры для генерации входной последовательности.

Первое число содержит количество операций [latex]n (1\leq n\leq10^{6})[/latex] со стеком. Затем следуют четыре неотрицательных целых числа [latex]a, b, c, x_{0}[/latex] не превосходящие [latex]10000[/latex].

Для получения входных данных генерируем последовательность [latex]x[/latex].

Первое число в генерируемой последовательности [latex]x_{1}[/latex]. Первое, а также каждое следующее число вычисляется из предыдущего по формуле:

[latex]x_{i}=\left(a\cdot x_{i-1}^{2} + b\cdot x_{i-1} + c\right)/100 \bmod{10^{6}}[/latex],

где ‘/‘ — операция целочисленного деления, а ‘[latex] \mod{}[/latex]’ — остаток от деления.

Если [latex]x_{i} \mod{5}<2[/latex], то необходимо удалить число из стека. В противном случае необходимо добавить в стек число [latex]x_{i}[/latex].

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

Выведите результирующую сумму.

Ссылка на задачу. Ссылка на засчитанное решение.

Код программы

 Пояснение решения

На мой взгляд сложность задачи состояла только в том, чтобы реализовать взятие минимального элемента из стека за [latex]O\left(1 \right)[/latex].

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

Ілларіонова Марія Валеріївна
Ілларіонова Марія Валеріївна

Latest posts by Ілларіонова Марія Валеріївна (see all)

5 thoughts on “e-olimp 693. Минимум в стеке

Добавить комментарий