
ZOJ Problem Set  2685
A union is an instance of playing the same pitch or of playing in octave. We want to arrange new polyphonic music with three different monophonic music scores of arbitrary length. Each monophonic music score has only 7 tones, C(do), D(re), E(mi), F(fa), G(sol), A(la), B(si) with the same interval. You can see polyphonic music X with three monophonic music scores (Music1, Music2, Music3) in Figure 1. Note that the lengths of Music1, Music2, and Music3 are 12, 12, 11, respectively. '&' is the symbol of a pause and means that no tone is played in that position. Music X is the same as playing 3 different monophonic music scores (Music1, 2, 3) simultaneously. The tones in each column of Figure1 denote a set of tones to be played simultaneously in polyphonic music. Let us define "unison" in this problem. A unison is an instance where the same tones are played simultaneously in a score. Thus, column1 = {A, F,A} and column2 = {C,C, F} are not unisons, so the music score X has only three unisons: column6 = {B,B,B}, column10 = {D,D,D}, and column12 = {A, A,&} . Formally, a column M = {x, y, z} is a unison, if M has three of the same tones or two of the same tones plus &. If x = y = z 6= '&', then the weight of the unison is 3. If M has two of the same tones and a single '&', then the weight of the column is 1. The sum of all unisons in a score is called the total unison weight. The following table shows the unison weight for each tone set.
The unison weight of score X in Figure1 is 3 + 3 + 1 = 7. However, if we arrange X to get another music by inserting pause symbols smartly, then we can increase the total unison weight significantly. Figure 2 shows another arrangement Y with unison weight 25. You are asked to compute the maximal unison weight from three different music scores by optimally inserting '&' symbols in each score. One important constraint on inserting '&' is that you should not insert more than one consecutive & in a music score. See Figure 3 for this constraint. Also, you are not allowed to modify the tones (melody) or to change the sequence of tones. Keep in mind that your arrangement can only insert &'s separately to get a maximal unison. Write a program that finds the maximal unison weight by using an optimal arrangement. Input The input consists of T test cases. The number of test cases (T) is given on the first line of the input file. Each test case starts with three lines containing a string of monophonic music scores consisting of a symbol set = {C, D, E, F, G, A, B}. There is a blank line between test cases. The maximal length of each monophonic music score string is 100. Output For each test case, your program reports only one number, the maximal total unison weight of each testing case in a line. If there is no arrangement satisfying the constraint, then print 1 as the output. The following shows sample input and output for four test cases. Sample Input 4 ABCDEF BCDEFG DEFGAB GABBCDEACF GAFGFCBBDEDD AFAFGCEECDEDF BCDEFGGADEF BCDE CDEFGABBA GAGABDEDCGAFFAB DAFFAGAEECCBA GCBDAAEGEAGAFF Sample Output 5 15 1 14 Source: Asia 2003, Seoul (South Korea) 