1999 Canadian Computing Competition, Stage 2

Day 1, Problem 2: Common Words

Given a sequence of m words from a newspaper article and an integer k, find the kth most common word.

Input

Input will consist of an integer n followed by n data sets. Each data set begins with a line containing m and k, followed by m lines, each containing a word of up to 20 lower case letters. There will be no more than 1000 words per data set.

Output

For each input data set, determine the kth most common word(s). To be precise, a word w is the kth most common if exactly k-1 distinct words occur more frequently than w in the data set. Note that w might be multiply defined (i.e. there is a tie for the kth most common word) or w might not exist (i.e. there is no kth most common word). For each data set, print a title line indicating k using normal ordinal notation (1st, 2nd, 3rd, 4th, 5th, ...) followed by a number of lines giving all the possible values for the kth most common word in any order. A blank line should follow the last word for each data set.

Sample Input

3
7 2
the
brown
the
fox
red
the
red
1 3
the
2 1
the
wash

Sample Output

2nd most common word(s):
red

3rd most common word(s):

1st most common word(s):
the
wash

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

The problem should say that the numbers ending in 1,2,3 should be printed with st, nd and rd(except for numbers ending in 11,12,13).

For each data set, print a title line indicating k using normal ordinal notation (1st, 2nd, 3rd, 4th, 5th, ...)

Pls give me a hint about what's wrong with my output, but better than the one Bob got^

You aren't outputting the words you should be.


Well, you're simply outputting the wrong words...