Cost mínim de fer dues paraules iguals P24879


Statement
 

pdf   zip

thehtml

Donades dues paraules s i t 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= “aaba” i t= “abb” el cost mínim és 7, corresponent a duplicar la ‘b’ i esborrar l’última ‘a’ de s, i duplicar la ‘a’ de t.

Entrada

L’entrada consisteix en diversos casos amb s i t, 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++