MC - Minimum Cost


Problem Statement :

Given two string S and T. you can delete a character  from  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 = a5b and  T = 2ab . 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
Gaurav Dahima: 2016-09-21 19:24:03

top down tle
Bottom up AC

Junaid: 2015-12-15 14:37:37

Simple problem...AC in one go...
HINT:-LCS

gullu_mishra: 2015-11-04 19:24:12

easy LCS ;) AC in 1 go..

:.Mohib.:: 2015-06-27 11:54:57

Easy... :)

rahul nagurtha: 2015-06-11 08:09:14

Dp giving TLE?? Is it the same with everyone?

Aayush: 2015-01-13 12:43:40

Exactly as @AnantKumar puts it

breaking_code: 2015-01-13 10:15:54

problem with statement about input....
input doesn't end when a[0] = '#' . input ends when scan(a,b) != 2

Neel Jinwala: 2014-07-13 13:05:05

'#' can be a part of string. Well any possible character can be a part of string. Just for heads up!

Himanshu: 2014-06-07 21:23:19

DP for beginners..

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

nice one :)


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