Задача 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].
Выходные данные
Выведите результирующую сумму.
Ссылка на задачу. Ссылка на засчитанное решение.
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <stack> #include <utility> #include <algorithm> using namespace std; const long long mod=1000000; stack <pair <long long, long long> > st; int main() { long long n, a, b, c, x, ans=0; cin >> n >> a >> b >> c >> x; while (n--) { x=(a*x*x+b*x+c)/100%mod; if (x%5<2) { if (!st.empty()) st.pop(); } else { long long mini= st.empty() ? x : min(x, st.top().second); st.push(make_pair(x, mini)); } if (!st.empty()) ans+=st.top().second; } cout << ans << endl; return 0; } |
На мой взгляд сложность задачи состояла только в том, чтобы реализовать взятие минимального элемента из стека за [latex]O\left(1 \right)[/latex].
Для этого предполагается хранить в стеке не просто наши элементы, но и минимум в стеке на текущем шаге. Что для этого требовалось, так это не забывать кидать в стек обновлённые минимумы на каждом шаге. Так же помня о том, что стек может быть уже пуст, я изменяла результирующую сумму только в том случае, если в стеке был хотя бы один элемент.
Пожалуйста, оформите все формулы в laTeX, включая «n» и «O(1)».
Всё исправлено.
Не знаю точно, как правильно было обозначить O(1) в латексе, поэтому если не подойдёт, то я исправлю, только скажите, как нужно.
Вы же уже кодировали скобки выше. Но можно и так оставить. А вот с остатком от деления нужно переделать.
Исправила и скобки, и модули.
Зачтено