
ZOJ Problem Set  2366
The issue of this problem is to find out how far two strings over alphabet Z are, with respect to one weird definition of dissimilarity. For any two characters c_{1} and c_{2} from Z consider dissimilarity d(c_{1}, c_{2}) of c_{1} from c_{2}  nonnegative integer number. If we take two strings a and b of equal length l, distance from a to b is You are given two strings s and t. Consider all possible pairs of strings a and b of equal length over Z, such that s is a subsequence of a and t is a subsequence of b (string w of length n is a subsequence of a string v of length m if there exist 1 <= i_{1} < i_{2} < ... < i_{n} <= m such that w[j] = v[i_{j}] for all 1 <= j <= n). Choose among them a' and b' such that dist(a', b') is minimal possible. Dissimilarity of s from t is defined as D(s, t) = dist(a', b'). Your task is to find the dissimilarity of s from t and to provide a' and b' such that D(s, t) = dist(a', b'). This problem contains multiple test cases! The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks. The output format consists of N output blocks. There is a blank line between output blocks. Input The first line of the input file contains Z  several different characters that form the alphabet for the strings we consider (1 <= Z <= 200, all characters have ASCII code greater than space). Next two lines contain s and t respectively. Length of each of the given strings does not exceed 2000. Next Z lines contain Z 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(s, t). On the second and third lines of the output file print a' and b', such that D(s, t) = dist(a', b'), s is a subsequence of a' and t is a subsequence of b'. Length of each of a' and b' must not exceed 4000. Sample Input
1 Sample Output
4 Author: Andrew Stankevich Source: Andrew Stankevich's Contest #3 