Zmicala Narcis: Pagină nouă: == Cerința == XORin este nemulțumit de problemele primite în prima zi de concurs de la Olimpiada Națională de Informatică și decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din șiruri de numere. Din când în când el trebuie să adauge sau să șteargă elemente din șir. Câteodată el decide să readauge dintre elemente șterse anterior. Fie șirul de numere '''a=(a[1], a[2], … ,a[N])''' și '''...

2024-01-03T14:02:32Z

Pagină nouă: == Cerința == XORin este nemulțumit de problemele primite în prima zi de concurs de la Olimpiada Națională de Informatică și decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din șiruri de numere. Din când în când el trebuie să adauge sau să șteargă elemente din șir. Câteodată el decide să readauge dintre elemente șterse anterior. Fie șirul de numere '''a=(a[1], a[2], … ,a[N])''' și '''...

New page

== Cerința ==
XORin este nemulțumit de problemele primite în prima zi de concurs de la Olimpiada Națională de Informatică și decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din șiruri de numere. Din când în când el trebuie să adauge sau să șteargă elemente din șir. Câteodată el decide să readauge dintre elemente șterse anterior. Fie șirul de numere '''a=(a[1], a[2], … ,a[N])''' și '''N''' numărul de elemente din șir după fiecare operație.
Astfel el are de realizat următoarele operații pornind de la un șir vid:
* Inserează la sfârșitul șirului o valoare '''x''';
* Șterge ultimele '''x''' elemente din șir;
* Readaugă la sfârșitul șirului primele '''x''' elemente șterse. Dacă, de exemplu, în operația anterioară de ștergere a unui număr '''y''' de elemente, am șters elementele '''a[N-y+1], a[N-y+2],…, a[N]''', iar acum urmează o operație de readăugare a '''x''' elemente, vor fi adăugate în ordine elementele '''a[N-y+1], a[N-y+2],…, a[N-y+x]''' la sfârșitul șirului.
Din când în când XORin își pune următoarea întrebare: de câte ori există valoarea '''x''' în șir?
== Date de intrare ==
Fișierul de intrare '''undoin.txt''' conține pe prima linie numărul '''M''' ce reprezintă numărul de operații.
Pe următoarele '''M''' linii se vor afla operațiile codificate astfel:
* '''1 x''' – se inserează elementul '''x''' la sfârșitul șirului
* '''2 y''' – se șterg ultimele '''y''' elemente adăugate în șir
* '''3 z''' – se adaugă înapoi la sfârșitul șirului primele '''z''' elemente șterse
* '''4 t''' – se afișează numărul de elemente cu valoarea '''t''' din șir
== Date de ieșire ==
Pe fiecare linie a fișierului '''undoout.txt''' se scriu răspunsurile la întrebările lui XORin, fiecare răspuns pe câte o linie.
== Restricții și precizări ==
* Toate numerele din fișierul de intrare sunt cuprinse între '''1''' și '''200000''';
* Pentru 20% din teste se garantează '''M ≤ 1000''', pentru alte 40% din teste, se garantează că numerele inserate vor fi distincte;
* Între o operație de ștergere și una de readăugare sau între două de readăugare nu se vor afla alte operații de inserare
* Numărul de elemente readăugate nu va fi mai mare decât numărul de elemente șterse la ultima operație.
* Între două operații de readăugare va exista cel puțin o operație de ștergere.
== Exemplul 1 ==
; undoin.txt
: 16
: 1 1
: 1 2
: 1 3
: 1 4
: 4 4
: 2 2
: 4 3
: 3 1
: 4 4
: 4 3
: 1 7
: 1 7
: 1 7
: 4 7
: 2 2
: 4 7
; undoout.txt
: Datele introduse corespund restricțiilor impuse.
: 1
: 0
: 0
: 1
: 3
: 1
== Explicație ==
Inițial șirul este vid.
După primele '''4''' operații de inserare șirul este '''1, 2, 3, 4'''.
Operația '''4 4''' va afișa '''1'''.
Operația '''2 2''' va șterge ultimele două elemente șirul devenind '''1, 2'''.
Din cauză că elementul '''3''' a fost șters, a șaptea operație va afișa '''0'''.
Operația '''3 1''' va readăuga la sfârșitul șirului elementul '''3'''.
În urma acestei operații șirul devine '''1, 2, 3'''.
Operația '''4 4''' va afișa '''0''', iar operația '''4 3''' va afișa '''1'''.
ș.a.m.d.
== Exemplul 2 ==
; undoin.txt
: 17
: 1 1
: 1 2
: 1 3
: 1 4
: 4 4
: 2 2
: 4 3
: 3 1
: 4 4
: 4 3
: 1 7
: 1 7
: 1 7
: 4 7
: 2 2
: 4 7
: 1 200001
; undoout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 1690 - Undo
def validare(op): # functia de validare a datelor de intrare
if len(op) > 200000:
raise ValueError
for operatie in op:
if operatie[0] < 1 or operatie[0] > 4 or operatie[1] < 1 or operatie[1] > 200000:
raise ValueError
fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")

def undo(op): # functia de rezolvare
sir = []
sters = []
for operatie in op:
if operatie[0] == 1:
sir.append(operatie[1])
elif operatie[0] == 2:
for _ in range(operatie[1]):
sters.insert(0, sir.pop())
elif operatie[0] == 3:
for _ in range(operatie[1]):
sir.append(sters.pop(0))
elif operatie[0] == 4:
fisier_iesire.write(str(sir.count(operatie[1])) + "\n")

if __name__ == '__main__':
fisier_intrare = open("undoin.txt", "r") # declararea fisierelor
fisier_iesire = open("undoout.txt", "w") # fisierul out trebuie declarat cu optiunea "w" (write)

try:
M = int(fisier_intrare.readline())
operatii = [list(map(int, linie.split())) for linie in fisier_intrare.readlines()]

validare(operatii) # apelul functiei de validare
undo(operatii) # apelul functiei de rezolvare

except ValueError:
fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
fisier_iesire.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>

1690 - Undo - Revision history