Cost mínim de fer dues paraules iguals P24879


Statement
 

pdf   zip

Donades dues paraules ss i tt compostes només per lletres minúscules, cal aconseguir fer-les iguals. Només es poden fer dues operacions, tantes vegades com calgui: Esborrar una lletra, amb cost 3, i duplicar una lletra, amb cost 2. Quin és el mínim cost possible?

Per exemple, per a s=s= “aaba” i t=t= “abb” el cost mínim és 7, corresponent a duplicar la ‘b’ i esborrar l’última ‘a’ de ss, i duplicar la ‘a’ de tt.

Entrada

L’entrada consisteix en diversos casos amb ss i tt, cadascuna amb entre 1 i 1000 lletres.

Sortida

Per a cada cas, escriviu el cost mínim de fer les dues paraules iguals.

Public test cases

  • Input

    a a
a b
a aa
aaba abb
xxxxzz zxxxx
g ggggggg

    Output

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