214. Weird Dissimilarity
time limit per test: 0.5
sec.
memory limit per test: 65536
KB
input: standard
output: standard
The issue of this problem is to find out how far two strings over alphabet Σ are, with respect to one weird definition of dissimilarity. For any two characters c_{1} and c_{2} from Σ consider dissimilarity d(c_{1}, c_{2}) of c_{1} from c_{2} — nonnegative integer number. If we take two strings α and beta of equal length l, distance from α to β is dist(α, β) = sum(i=1..l, d(α[i], β[i])).
You are given two strings λ and μ. Consider all possible pairs of strings α and β of equal length over Σ, such that λ is a subsequence of α and μ is a subsequence of β (string ω of length n is a subsequence of a string ξ of length m if there exist 1 ≤ i_{1} < i_{2} < ... < i_n ≤ m such that ω[j] = ξ[i_{j}] for all 1 ≤ j ≤ n). Choose among them α' and β' such that dist(α', β') is minimal possible. Dissimilarity of λ from μ is defined as D(λ, μ) = dist(α', β').
Your task is to find the dissimilarity of λ from μ and to provide α' and β' such that D(λ, μ) = dist(α', β').
Input
The first line of the input file contains Σ — several different characters that form the alphabet for the strings we consider (1 ≤ Σ ≤ 200, all characters have ASCII code greater than space). Next two lines contain λ and μ respectively. Length of each of the given strings does not exceed 2000. Next Σ lines contain Σ nonnegative integer numbers each, jth number of ith line contains dissimilarity of ith character from jth.
Output
On the first line of the output file print D(λ, μ). On the second and third lines of the output file print α' and β', such that D(λ, μ) = dist(α', β'), λ is a subsequence of α' and μ is a subsequence of β'. Length of each of α' and β' must not exceed 4000.
Sample test(s)
Input
ab
ab
ba
2 1
4 1
Output
4
aba
bba
Author:  Andrew Stankevich

Resource:  Petrozavodsk Summer Trainings 2003

Date:  20030830

Server time: 20171123 19:45:04  Online Contester Team © 2002  2016. All rights reserved. 

