1690 - Undo

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">

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>