3695 - iziStack
De la Universitas MediaWiki
Enunt
Se dă o stivă vidă. Elementele stivei sunt numerotate incepand cu 1 de la bază înspre vârf. Avem de procesat T comenzi de tipurile:
- 0 x – elementul x se va adăuga în vârful stivei
- 1 x y add – tuturor elementelor din intervalul x y le va fi adăugată valoarea add
- 2 – eliminarea elementului din vârf
Cerinţa
Afisați dupa fiecare operație elementul din vârful stivei. Se garantează: 1. că nu se va efectua operația de tip 2 dacă nu există cel puțin două elemente în stivă; 2. că prima operatie va fi de tipul 0
Date de intrare
Fișierul de intrare izi.in conține pe prima linie un număr natural T, iar pe următoarele T linii operațiile efectuate asupra stivei.
Date de ieșire
Fișierul de ieșire izi.out va conține T linii, reprezentând elementele din vârful stivei dupa fiecare operație.
Restricţii şi precizări
- 1 ≤ T ≤ 1.000.000
- -1000 ≤ add ≤ 1000
- Pentru operațiile de tip 1, -1000 ≤ x ≤ 1000, iar pentru operatiile de tip 2 numărul elementelor aflate în stivă este mai mare ca y
- Pentru 36 puncte: 1 ≤ T ≤ 1000
- Pentru alte 33 puncte: Toate operatiile de tip 2 se vor afla la finalul fișierului de intrare
Exemplu
- izi.in
7 0 1 1 1 1 2 0 2 1 1 2 3 2 0 4 2
- izi.out
1 3 2 5 6 4 6
Rezolvare
class Stack:
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x)
def pop(self):
if self.is_empty():
return None
return self.stack.pop()
def top(self):
if self.is_empty():
return None
return self.stack[-1]
def is_empty(self):
return len(self.stack) == 0
def process_operations(T, operations):
stack = Stack()
for op in operations:
if op[0] == 0:
stack.push(op[1])
elif op[0] == 1:
x, y, add = op[1], op[2], op[3]
for i in range(x - 1, y):
stack.stack[i] += add
elif op[0] == 2:
stack.pop()
if not stack.is_empty():
print(stack.top())
def main():
T = int(input())
operations = []
for _ in range(T):
operation = list(map(int, input().split()))
operations.append(operation)
process_operations(T, operations)
if __name__ == "__main__":
main()