Another problem of the edit distance P80964


Statement
 

pdf   zip

thehtml

Given two words made up with lowercase letters, compute the minimum cost of making them equal. The allowed operations are erasing a letter, increasing a letter (not ‘z’), and decreasing a letter (not ‘a’). Removing costs 10. Increasing and decreasing costs 1.

For example, if the words are “hello” and “hi”, the minimum cost is 33. One possible way is to delete the ‘e’, one ‘l’ and the ‘o’ of the first word, and increase 3 times the ‘i’ of the second word to make it an ‘l’.

Input

Input consists of several cases. Every case has two nonempty words, each with between 1 and 1000 lowercase letters.

Output

For every case, print the minimum cost of making the words equal.

Public test cases
  • Input

    hello hi
    a b
    zz a
    aza yyydd
    

    Output

    33
    1
    30
    44
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++