AIOC Banner

Problem: Chimera

Want to try solving this problem? You can submit your code online if you log in or register.


Chimera

Input File: chimin.txt
Output File: chimout.txt
Time Limit: 1 second

Next week is your school's Mad Science Fair, and everyone is hard at work on their mad science projects. For example, Gru is building a rocket big enough to steal the moon, whilst Elsa is tinkering with her freeze ray. For your project, you are breeding a chimera.

A chimera is a monster that is part lion, part snake, and part goat. Your plan is to take the DNA sequences of each of the three creatures and combine them into a new DNA sequence for the chimera. A DNA sequence is a string of N letters, each one of A, T, C or G.


The list above shows an example of three DNA sequences of length 7 representing lion, snake and goat DNA. The bottom DNA sequence is one possible sequence of chimera's DNA. Letters in bold in the top three lines are the same as the letter in the chimera's DNA at the same position.

The lionishness of your chimera is defined as the number of positions in which the lion DNA and the chimera DNA have the same letter. In the example above, the lionishness of your chimera is 6, as they match in all but the first position. The snakiness and goatism of your chimera are defined similarly. In the example above, the snakiness and goatism of your chimera are both 5.

The task before you is to construct the chimera's DNA sequence. You will be given the DNA sequences for lions, snakes and goats. The mark for your project will be whichever is lowest: the lionishness, snakiness or goatism of your chimera. You must determine the highest mark you can possibly achieve.

Input

Your program should read from the file chimin.txt.

Output

Your program should write to the file chimout.txt. Your output file should contain one line with one integer: the highest possible mark you can achieve. (Remember, your mark will be whichever is lowest: the lionishness, snakiness or goatism of your chimera.)

Sample Input 1

7
GATTATA
CAGGATA
TATTACA

Sample Output 1

5

Explanation

The sample data reflects the case described earlier in the problem description. There is no chimera DNA sequence that will receive a mark higher than 5.

Constraints

To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

Furthermore,

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  5:42am AEDT