Problem B
Flag Quiz

However, sometimes (actually, most of the time) you can figure out the answer to a quiz question just by looking at the alternatives. Being a low budget show, the underpaid quiz question authors strive to minimize their effort in coming up with the alternatives for each question. They construct each alternative by making a small number of changes to the correct answer, where a change consists of replacing one part of the correct answer with something else. For example, transforming “green, blue, stripes” into “green, yellow, stripes” has one single change, while changing the same answer into “life, universe, stripes” has two changes. The question authors never permute the parts, so order matters. In other words, transforming “green, blue, stripes” into “stripes, blue, green” has two changes even though they are both technically the same answer. Note that the answers are case sensitive, so “green, blue, stripes” and “Green, Blue, Stripes” need 3 changes.
Your task is to write a program that automatically finds the most likely answers to questions constructed in this way. Define the incongruousity of an alternative as the maximum number of changes needed to transform that alternative into any of the other alternatives. We then seek the alternative(s) with the smallest incongruousity.
Task
Given a question and a set of potential answers to it, find the answer that is easiest to change into any other answer.
Input
The first line is the question to be answered. The next line
contains one positive integer
Output
Output the alternative that requires the smallest maximum amount of changes to be turned into any other answer. If there are several least incongruous alternatives, output them all in the same order as in the input.
Sample Input 1 | Sample Output 1 |
---|---|
The flag of the empire Angola? 4 Green stripe, black stripe, yellow Red stripe, black stripe, yellow Red stripe, black stripe, white Red stripe, green stripe, yellow |
Red stripe, black stripe, yellow |
Sample Input 2 | Sample Output 2 |
---|---|
The flag of the Knights who say Ni? 4 Black, white, pink, shrubbery Black, white, red, shrubbery Pink, white, red, shrubbery Black, pink, red, shrubbery |
Black, white, red, shrubbery |