Cost mínim de parentitzar correctament (2) P10387


Statement
 

pdf   zip

html

Donada una paraula composta només per parèntesis i claudàtors que obren i tanquen, s’hi poden fer dos tipus d’operacions:

  • Girar l’orientació d’un parèntesi o d’un claudàtor. És a dir, es pot convertir ‘(’ en ‘)’, ‘)’ en ‘(’, ‘[’ en ‘]’, o ‘]’ en ‘[’. Això costa 1.
  • Transformar un parèntesi en un claudàtor o a l’inrevés, sense canviar-ne l’orientació. És a dir, es pot convertir ‘(’ en ‘[’, ‘)’ en ‘]’, ‘[’ en ‘(’, o ‘]’ en ‘)’. Això costa 2.

Quin és el cost mínim de convertir una paraula donada en una parentització correcta? Per exemple, si la paraula és “](”, llavors es pot aconseguir la parentització correcta “[]” fent dos girs i una transformació, amb cost total 4.

Entrada

L’entrada consisteix en diversos casos. Cada cas consisteix en una paraula amb parèntesis i claudàtors que obren o tanquen. Totes les paraules tenen mides parells entre 2 i 100.

Sortida

Per a cada cas, escriviu el cost mínim de parentitzar correctament.

Pista

La solució esperada té cost temporal Θ(n3 ) i cost espacial Θ(n2 ).

Public test cases
  • Input

    ()
    ()[]
    ([](
    )]])
    ])[(
    ](
    )((]([(]
    

    Output

    0
    0
    1
    2
    6
    4
    9
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++