Problem C

Žofka invented a new word puzzle. She gives you two strings $s_1$ and $s_2$ of the same length. You need to modify $s_1$ into $s_2$ as quickly as possible. The trick is that you are allowed to modify the strings only using the following types of moves: (1) shift forward where you choose a substring of one of the strings and shift each of its letters by 1 forward in the alphabet, or (2) shift backward where you shift each letter in a substring backward in the alphabet. The first move is not allowed if the substring contains the letter z while the second move is not allowed if the subtring contains a. What is the smallest number of moves you need to modify $s_1$ into $s_2$?


Each word puzzle is described on a single line that contains the strings $s_1$ and $s_2$ separated by space. The strings contain only lower case letters. You may also assume that the length of each string is at most $10\, 000\, 000$.


Output one line with the smallest number of moves needed to modify $s_1$ into $s_2$.


The first sample input can be modified in the following way. First shift lo forward, getting helmp. Then shift h forward 12 times, getting telmp. Then shift l 11 times backward to get teamp and then shift p forward three times to get teams. Total number of moves is $1+12+11+3=27$.

The second sample input can be modified as follows. First shift the entire string forward, getting bbdddbbbb. Then shift ddd backward twice to get bbbbbbbbb. This requires 1+2=3 moves.

Sample Input 1 Sample Output 1
hello teams
Sample Input 2 Sample Output 2
aacccaaaa bbbbbbbbb
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Ivona Bezakova
Source Northeast North America Regional 2013
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in