Editing 1971 - Plus

Locuitorii planetei Aritmo au hotărât ca în celebrul an 2012 să le explice pământenilor metoda plus de adunare a numerelor naturale pe planeta lor. La fel ca și planetele, înainte de adunare, numerele se aliniază astfel încât să se obțină cât mai multe cifre egale pe aceleași poziții. Cifrele egale, astfel obținute, se elimină din cele două numere. Pentru a obține rezultatul final, se adună cele două numerele deplasate, obținute după eliminare, ca în exemplu.

Exemplu: Numerele 18935 și 85352 se aliniază ca în figura de mai jos. După eliminare se obțin numerele 19 și 52 care se adună deplasate, pentru a obține rezultatul final. Așadar 18935 plus 85352=242.

: 18935 plus    19 +
:  85352         52
:               ---
:               242
Dacă există mai multe posibilități de a alinia numerele astfel încât să se elimine același număr maxim de cifre, atunci numerele sunt aliniate astfel încât, după eliminare şi adunarea numerelor după metoda descrisă, să se obțină o valoare cât mai mare.

Exemplu: '''22331 plus 3322 = 33331''' (există două moduri în care cele două numere pot fi aliniate astfel încât să se elimine un număr maxim de cifre, valoarea maximă obținându-se atunci când se elimină cele două cifre 2)

: 22331      221 +       22331      331+
:   3322       22      3322       33
:            ----                 -----
:            2232                 33331
Dacă două numere a și b sunt identice sau nu au cifre comune atunci a plus b=0. Dacă se elimină toate cifrele unui număr atunci rezultatul este dat de cifrele rămase în celălalt număr. Exemple: '''23 plus 523=5, 562 plus 56=2'''.

Adunarea mai multor numere se face de la stânga la dreapta: se adună primele două numere conform metodei descrise mai sus, apoi rezultatul se adună cu al treilea, și așa mai departe.

Într-o expresie în care se adună mai multe numere pot să apară paranteze rotunde. În evaluarea unei asemenea expresii, numită expresie parantezată, se efectuează mai întâi adunările din paranteze conform metodei descrise mai sus, parantezele fiind apoi înlocuite cu rezultatul adunărilor din paranteze.

Se definește adâncimea Ad(E) corespunzătoare unei expresii parantezate E astfel:

* dacă expresia '''E''' nu conține paranteze, atunci adâncimea acesteia este '''0''';
* dacă expresia '''E''' este de forma '''(F)''', atunci '''Ad(E)=1+Ad(F)''';
* dacă expresia '''E''' este de forma '''E1 plus E2…plus Ek''', atunci '''Ad(E)=max(Ad(E1)''', '''Ad(E2),…, Ad(Ek))'''.
== Cerința ==
Pentru a-i ajuta pe pământenii care doresc să învețe acest nou mod de adunare, scrieți un program care citește o expresie parantezată și determină:
a) adâncimea expresiei date;
b) valoarea acestei expresii.
== Date de intrare ==
Fișierul de intrare '''plusin.txt''' conține pe prima linie un număr natural '''n'''. Pe următoarele '''n''' linii se află descrierea expresiei parantezate. Pe fiecare dintre aceste linii se află un număr natural sau una dintre valorile '''-1''' sau '''-2'''. Valoarea '''-1''' reprezintă o paranteză rotundă deschisă iar valoarea '''-2''' reprezintă o paranteză rotundă închisă.
== Date de ieșire ==
Fișierul de ieșire '''plusout.txt''' va conține:
a) pe prima linie numărul natural ce reprezintă adâncimea expresiei date;
b) pe a doua linie se va scrie numărul natural ce reprezintă rezultatul evaluării expresiei date, adunarea numerelor făcându-se conform metodei descrise.
== Restricții și precizări ==
* '''1<n≤2000''';
* fiecare dintre celelalte numere naturale din fișier are cel mult 9 cifre;
* în fiecare paranteză se află cel puțin un număr natural;
* dacă într-o paranteză se află un singur număr natural, atunci valoarea expresiei este egală cu valoarea numărului din paranteză;
* pentru rezolvarea corectă a cerinței a) se acordă 20% din punctaj, iar pentru rezolvarea corectă a ambelor cerinţe se acordă punctajul integral.
== Exemplul 1 ==
; plusin.txt
: 12
: -1
: 1343 
: -1
: 234 
: 4532 
: -2
: -2
: 14091
: -1
: 21
: 2
: -2
; plusout.txt
: Datele introduse corespund restricțiilor impuse.
: 2
: 4639
== Explicație ==
Expresia parantezată care trebuie evaluată este:
'''(1343 plus (234 plus 4532)) plus 14091 plus (21 plus 2)='''
'''(1343 plus 45334)plus 14091 plus (21 plus 2) ='''
'''4543 plus 14091 plus (21 plus 2)='''
'''4543 plus 14091 plus 1='''
'''46391 plus 1=4639'''
Valoarea expresei este '''4639'''. Adâncimea expresiei este '''2'''.
== Exemplul 2 ==
; plusin.txt
: 13
: -1
: 1343
: -1
: 234
: 4532
: -2
: -2
: 14091
: -1
: 21
: 2
: -2
: 1000000000
; plusout.txt
: Datele introduse nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 1971 - Plus
def validare(op):           # functia de validare a datelor de intrare
    if len(op) > 2000:
        raise ValueError
    for operatie in op:
        if operatie != -1 and operatie != -2 and (operatie < 1 or operatie > 999999999):
            raise ValueError
    fisier_iesire.write("Datele de intrare corespund restrictiilor impuse\n")


def plus(op):                     # functia de rezolvare
    if len(op) == 0:
        fisier_iesire.write("0\n")
        return
    stiva = []
    adancime = 0
    for operatie in op:
        if operatie == -1:
            stiva.append([])
            adancime = max(adancime, len(stiva))
        elif operatie == -2:
            if len(stiva[-1]) == 1:
                if len(stiva) > 1:
                    stiva[-2].append(stiva[-1][0])
                stiva.pop()
            else:
                numere = stiva.pop()
                while len(numere) > 1:
                    a = numere.pop()
                    b = numere.pop()
                    numere.append(a + b - int(str(a) + str(b)))
                if len(stiva) > 0:
                    stiva[-1].append(numere[0])
        else:
            stiva[-1].append(operatie)
    fisier_iesire.write(str(adancime) + "\n")
    fisier_iesire.write(str(stiva[0][0]) + "\n")


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

    try:
        N = int(fisier_intrare.readline())
        operatii = [int(linie) for linie in fisier_intrare.readlines()]

        validare(operatii)                 # apelul functiei de validare
        plus(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>