693. Minimum in the Stack
The input to a program is a set of
operations with a stack. Each operation is either an addition or removal of an
item to or from the stack. After each operation find the smallest number in a
stack. Summarize all the resulting numbers and get the answer. If after any
operation the stack is empty, then add nothing to the answer. If it is
impossible to remove an item because the stack is empty, then do nothing.
Input. The input data will be generated in
your program. You will be given some parameters to get the input sequence.
The
first input number n (1 ≤ n ≤ 106) is the number
of operations with the stack. Then four nonnegative integers a, b,
c, x0 are given. Their values are not greater than 10000.
Let's
generate the input sequence x.
The
first number of input sequence is x1.
The first and each next number can be evaluated from the previous one using the
formula:
xi = (a·
+ b·xi-1 + c) / 100 mod 106,
where
'/' is an integer division, 'mod' is the remainder from division.
If xi mod 5 < 2, you must
delete the number from the stack. Otherwise add number xi to the stack.
Output. Print the resulting sum.
|
Sample input 1 |
Sample output 1 |
|
2 0 0
1 81 |
0 |
|
|
|
|
Sample input 2 |
Sample output 2 |
|
3 1 1
1 13 |
0 |
SOLUTION
data structures - stack
Algorithm
analysis
In the problem its enough to simulate
the stack. If xi mod 5
≥ 2, we shall put to the stack not the value of xi, but the minimum of the top of the stack and xi. If the stack is empty, we
push xi into it. If xi mod 5 < 2, delete the
element from the top of the stack. With this approach of processing the input
data the top of the stack will always contain the minimum value of xi which are currently in the
stack.
After processing the current value of
xi, add to the resulting
sum res the value from the top of the
stack.
Algorithm realization
Define a stack data structure.
stack<long long> s;
Read input data.
scanf("%lld
%lld %lld %lld %lld",&n,&a,&b,&c,&x);
for(res = i = 0; i < n; i++)
{
Keep in the variable x
the current element xi of the
sequence. Depending on the value of x mod 5, either put to the
stack the minimum of its top and x, or delete the element from
the top of the stack.
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5 < 2)
{
if (!s.empty()) s.pop();
} else
{
if (s.empty()) s.push(x);
else s.push(min(s.top(),x));
}
If the stack is not empty, then add to the resulting sum res the value stored at its top.
if (!s.empty()) res += s.top();
}
Print the answer.
printf("%lld\n",res);
Stack realization with static array
As the number of operations n with stack is no more than 106,
its enough to use a
stack with this size.
#include <stdio.h>
long long i, n, a, b, c, x, res;
class
Stack
{
private:
long long *m;
int topPtr,
size;
void
allocate()
{
m = new long long[size];
topPtr = EmptyStack;
}
public:
enum
{DefaultStack = 1000010, EmptyStack = -1};
Stack()
{
size = DefaultStack;
allocate();
}
Stack(int n)
{
if (!n) n =
DefaultStack;
size
= n;
allocate();
}
~Stack()
{
delete[] m;
}
int full(void)
{
return
topPtr + 1 >= size;
}
int empty(void)
{
return
topPtr <= EmptyStack;
}
void push(const long long &Value)
{
if
(!full()) m[++topPtr] = Value;
}
long long pop(void)
{
if
(!empty()) return m[topPtr--];
return 0;
}
long long top(void)
{
if
(!empty()) return m[topPtr];
return 0;
}
};
long long min(long long a, long long b)
{
return (a
< b) ? a : b;
}
Stack
s;
int
main(void)
{
scanf("%lld
%lld %lld %lld %lld",&n,&a,&b,&c,&x);
for(res = i =
0; i < n; i++)
{
x = ((a*x*x + b*x + c) / 100) % 1000000;
if (x % 5
< 2)
{
if
(!s.empty()) s.pop();
} else
{
if
(s.empty()) s.push(x);
else
s.push(min(s.top(),x));
}
if
(!s.empty()) res += s.top();
}
printf("%lld\n",res);
return 0;
}
Java realization
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Stack<Long> s = new
Stack<Long>();
Scanner con = new Scanner(System.in);
long n = con.nextLong();
long a = con.nextLong();
long b = con.nextLong();
long c = con.nextLong();
long x = con.nextLong();
long res = 0;
for(int i = 0; i < n; i++)
{
x = ((a*x*x + b*x + c) / 100) %
1000000;
if (x % 5 < 2)
{
if (!s.empty())
s.pop();
} else
{
if (s.empty())
s.push(x);
else
s.push(Math.min(s.peek(),x));
}
if (!s.empty())
res += s.peek();
}
System.out.println(res);
con.close();
}
}