0162. Weird Dissimilarity

Имя входного файла:	dissim.in
Имя выходного файла:	dissim.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

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₁ and c₂ from Σ consider dissimilarity d(c₁, c₂) of c₁ from c₂ – non-negative integer number. If we take two strings α and β of equal length l, distance from α to β is dist(α, β) = Σ_i=1^ld(α[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₁ < i₂ < …< 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 file

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.

Output file

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.

Examples:

dissim.in	dissim.out
ab ab ba 2 1 4 1	4 aba bba

Источник: Petrozavodsk Summer 2003. Final Contest, Saturday, August 30
Автор: Andrew Stankevich

Обсудить       Отправить решение



Версия для печати