MC - Minimum Cost


Problem Statement

Given two string S and T. You can delete a character from S with cost 15 and a Character T with cost 30. Your goal is to make the string equal (same). It is not mandatory to delete character.

For example: S = aXb and T = Yab. Now, if we delete X from S and Y from T, then total cost = 15 + 30 = 45. And S and T will become ab.

Another example: S = ab , T = cd, Now total cost = 15 + 15 + 30 + 30 = 90.

Another example: S = abcd, T = acdb, Now total cost = 15 + 30 = 45.

Input

Input consists of pairs of lines. The first line of a pair contains the first string S and the second line contains the second string T. Each string is on a separate line and consists of at most 1,000 characters . The end of input occurs when the first sequence starts with an "#" character (without the quotes).

Output

For each subsequent pair of input lines, output a line containing one integer number which the minimum cost to make the string equal (same).

Sample Input/Output

Sample Input

Sample Output

axb
yab
ab
cd
ko
p
abcd
acdb
#
45
90
60
45


___________________________________________________________________________________________________________
Problem Setter: Shipu Ahamed, Dept. of CSE

Bangladesh University of Business and Technology (BUBT)


hide comments
Prime virus: 2014-03-14 23:18:48

nice one :)

Anant Kumar: 2013-10-18 22:53:52

That moment when you get the idea and the hard question becomes piece of cake(in Ouditchya
Sir's word). :)

Shipu : r8

Last edit: 2013-11-27 11:46:28
Hasil Sharma: 2013-10-18 22:53:52

really easy with python :) Best solution in python \m/ and working on it to make it better .....

Last edit: 2013-07-02 18:57:34
SilentKiller: 2013-10-18 22:53:52

Input ends when first character of first string is '#' not with "#" Costed two WA
otherwise very easy

Ouditchya Sinha: 2013-10-18 22:53:52

Piece of Cake! :)

Hasil Sharma: 2013-10-18 22:53:52

S = abcd , T = acdb
total cost should be 0 right ?
ans -> No .
S = abcd
T = acdb

result acd.
so 15 + 30 = 45

Last edit: 2013-06-20 18:12:38
nitish rao: 2013-10-18 22:53:52

can the length of a string be zero??

ans -> no

Last edit: 2013-06-20 18:10:05

Added by:Shipu Ahamed
Date:2013-06-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:BAPS