Bio-HRQ-Comparator is a fully automatic computer based neurological scanning
system that scans brains of three persons simultaneously and ranks them 1, 2, 3 with respect
to their HRQ (Human Resource Quotient) for a given activity. Bio-HRQ-Comparator has three
specially designed chairs each fitted with brain scanning devise. Exactly three persons are to
sit on the chairs and just think independently and simultaneously on the best possible solution
of a given problem related to an activity for which HRQ is tested. The thinking process
continues for a specified duration of time that is dependent on the complexity of the given
problem. Bio-HRQ-Comparator captures the thinking process and ranks them with respect to
their HRQ without any further scrutiny. Through rigorous testing and analysis, ranking by Bio-
HRQ-comparator has been found to be so precise that no two ranked persons are identified
to have different rank order or found to have the same HRQ.
The system has the potential to replace the traditional method of selection of
candidates through interview, where the basic problem is to arrive at total ordering and
ranking of a given set of n (assume n≤ 20) candidates with respect to their HRQ for a specific
job. It is proposed to select arbitrarily k sets of three candidates each and rank candidates in
each set using Bio-HRQ-comparator hoping that total ordering and ranking of candidates can
be done successfully. However it is not always possible to arrive at total ordering and ranking
of all n candidates using arbitrarily selected k sets of candidates.
You are required to write a program that either ranks all n candidates, if possible,
using the k results obtained so far or determines the minimum number m of additional Bio-
HRQ-comparator testing required for determining the total ordering and ranking of all n
candidates. In case m additional testing are required, the program should identify m sets of
three candidates each, for additional Bio-HRQ-comparator testing. Assume for simplicity that
a candidate is not required to appear more than twice for additional testing.
Input may contain multiple test cases. Each test case contains two lines.
The 1st line gives n and a string of n letters. Each letter in the string identifies a candidate and letters appear in an arbitrary order.
The 2nd line gives k results of Bio-HRQ-comparator testing. The first field is the integer k and it is followed by k strings of three letters each representing k results. The three letters in a string appear in order of ranks 1, 2 and 3 of candidates represented by the letters.
Input terminates with a line that contains 0 (zero) as the first and the only character.
For each test case, print output in one line.
The first field in the line gives the integer m. If m is equal to 0 then a string of n letters follows it; the string represents the total rank order of all n candidates.
Otherwise just print nothing.
* Note this is different from the original problem statement.
5 axdpf 3 adf xdp axp 5 xapfd 3 afd xdp axf 7 adgbnem 4 aem egn dgm emb 0 0 0
1 0 axfdp 2 0
If you get AC for this problem (ID:4415) on ICPC-live archieve website, please tell TA, thank you:)
Migrated from old NTUJ.
ICPC Kanpur, 2008
| No. | Testdata Range | Score |
|---|