The task is the same as the Merge Sort. The differences is that now the strings are in files.
We have $k$ files as input and each of them contains a string. Every three characters in a string form a word, and all words are in dictionary order as they appear in the file. For example, a file may have "abcbacbae" since “abc” is less than “bac”, which is less than “bae”.
The goal of the task is to merge these $k$ strings from $k$ files into a single sorted file. Note that you cannot read all $k$ strings into memory, since you will get MLE error if you do that. Instead you must read only necessary parts from the files.
The input has only one test case. The first line is the number of input files $k$. The following $k$ lines are the names of the $k$ input files. The length of every input file is a multiple of 3. The last line has the name of the output file.
- $k\lt 20$
- The length of the name of every file is less than 20.
Write the merged string into the output file.
- 10 points: There are only two input files, and each file has exactly three characters.
- 20 points: There are $k$ input files, and each file has exactly three characters.
- 70 points: There are $k$ input files, and each file has at least three characters.
Sample Input 1 (stdin)
Sample output 1
Sample Input 2 (stdin)
Sample output 2
Sample Input 3 (stdin)