Editing 1924 - QStiva (section)

==Explicație==
Funcția validate_input verifică dacă input-ul este valid, adică dacă este în conformitate cu restricțiile problemei. Funcția read_input citește input-ul din fișierul "qstiva.in" și îl validează folosind funcția validate_input. Funcția solve_queries primește input-ul validat și rezolvă problema "Q-Stack" utilizând tehnica de programare dinamică. Funcția write_output scrie rezultatul în fișierul "qstiva.out". Funcția main este funcția principală care apelează celelalte funcții în ordine pentru a citi input-ul, a rezolva problema și a scrie rezultatul.

Algoritmul utilizează o matrice dp de dimensiuni nmax x Smax+2, unde dp[i][j] este True dacă există un subsir de lungime i cu o sumă de elemente egală cu j. Matricea este inițializată cu dp[0][0] = True, pentru că există un subsir de lungime zero cu suma elementelor zero. Algoritmul primește trei tipuri de interogări:

Adaugă elementul x la stack.
Elimină ultimul element adăugat la stack.
Verifică dacă există un subsir de elemente care au o sumă egală cu x.
Pentru fiecare interogare de tipul 1, se creează un nou rând în matricea dp, inițializat cu False. Pentru fiecare element i din matricea anterioară care are valoarea True, se actualizează valorile dp[n][i+x] și dp[n][i] pe baza valorii anterioare dp[n-1][i].

Pentru fiecare interogare de tipul 2, se elimină ultimul rând din matricea dp.

Pentru fiecare interogare de tipul 3, se verifică dacă există un subsir de elemente din stack care au o sumă egală cu x. Dacă da, se adaugă 1 în lista de rezultate ans, altfel se adaugă 0.

În final, lista de rezultate este scrisă în fișierul "qstiva.out".