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 c1 and c2 from Σ consider dissimilarity d(c1, c2) of c1 from c2 — non-negative 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 ≤ i1 < i2 < ... < i_n ≤ m such that ω[j] = ξ[ij] 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(α', β').
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 |Σ| non-negative integer numbers each, j-th number of i-th line contains dissimilarity of i-th character from j-th.
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.
ab ab ba 2 1 4 1
4 aba bba
Petrozavodsk Summer Trainings 2003
Codeforces (c) Copyright 2010-2019 Mike Mirzayanov