Vizualizare sursă pentru „3991 - Modifica Paranteze”

= Cerința =
Fie un șir de paranteze rotunde, deschise sau închise. Putem efectua de câte ori dorim operația de transformare a unei paranteze deschise într-una închisă sau invers. Să se determine numărul minim de operații necesare transformării secvenței inițiale într-una corect parantezată. Dacă acest lucru nu este posibil, se va afișa <code>-1</code>.

= Date de intrare =
Programul citește de la tastatură șirul de paranteze rotunde, fără spații.

= Date de ieșire =
Programul va afișa pe ecran numărul minim de operații necesar pentru a transforma șirul într-o secvență corect parantezată. Dacă nu este posibilă parantezarea corectă, se va afișa <code>-1</code>.

= Restricții și precizări =

* <code>1 ≤ numărul de paranteze ≤ 1000</code>

= Exemplul 1: =
Intrare
 ((((
Ieșire
 2

=== Explicație ===
O posibilitate este să modificăm ultimele două paranteze deschise în paranteze închise și să obținem <code>(())</code>.

== Exemplul 2: ==
Intrare
 (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
Ieșire
 Datele nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restriction(s):
    num_parentheses = s.count('(') + s.count(')')
    return 1 <= num_parentheses <= 1000

def nr_min_op(s):
    cnt = 0
    nr_op = 0
    n = len(s)

    if not check_restriction(s):
        print("Datele nu corespund restrictiilor impuse.")
        return -1

    if n % 2 == 1:
        return -1

    for i in range(n):
        if s[i] == '(':
            cnt += 1
        else:
            cnt -= 1

        if cnt < 0:
            nr_op += 1
            cnt = 1

    nr_op += cnt // 2
    return nr_op

if __name__ == "__main__":
    s = input("Introduceti un sir cu paranteze: ")

    if check_restriction(s):
        result = nr_min_op(s)
        if result != -1:
            print(result)
    else:
        print("Datele nu corespund restrictiilor impuse.")

</syntaxhighlight>