/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 7 点
注意
この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
ある文を構成する N 個の単語の列 S が与えられます。
この列には同じ単語が複数回出てくるかもしれません。
この列に一回以上出現する単語を、その出現回数の多い順に並べたとき K 番目の単語を出力してください。
但し、出現回数が同じ単語をどう並べるかによって K 番目の単語が一つに決まらないときは代わりに AMBIGUOUS を出力してください。
制約
- 1 \le N \le 10^5
- S_i は長さ 1 以上 10 以下の英小文字からなる文字列 (1 \le i \le N)
- 1 \le K \le (S に含まれる異なる文字列の個数 )
- N, K は整数
入力
入力は以下の形式で標準入力から与えられる。
N K
S_1
S_2
S_3
\hspace{3pt} \vdots
S_N
出力
S に 1 回以上出現する単語を出現回数の多い順に並べたときに K 番目の単語が一つに決まる場合その単語を、そうでない場合 AMBIGUOUS を出力せよ。
入力例 1
6 2 abcde caac abcde caac abc caac
出力例 1
abcde
caac が 3 回、abcde が 2 回、abc が 1 回出現します。出現回数の多い順で 2 番目は abcde です。
入力例 2
9 3 a a bb bb a ccc bb ccc dddd
出力例 2
ccc
a と bb が 3 回、ccc が 2 回、dddd が 1 回出現します。
出現回数が同じ a と bb をどの順に並べたとしても、それらが 1 番目と 2 番目を占め 3 番目が ccc となるので、 ccc を出力してください。
入力例 3
7 2 caac abcde caac abc abcde caac abc
出力例 3
AMBIGUOUS
caac が 3 回、abcde と abc が共に 2 回出現します。2 番目に多く出現するのは abcde か abc か決まらないので AMBIGUOUS を出力してください。
Score : 7 points
Warning
Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
Given is a sequence S of N words that form a certain sentence.
The same word may appear multiple times in this sequence.
Consider sorting the words that appear at least once in S in descending order of frequency, and print the word that comes in K-th.
However, if the K-th frequent word varies depending on the order of words with the same frequency, print AMBIGUOUS instead.
Constraints
- 1 \le N \le 10^5
- S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters. (1 \le i \le N)
- 1 \le K \le ( the number of different words contained in S)
- N and K are integers.
Input
Input is given from Standard Input in the following format:
N K
S_1
S_2
S_3
\hspace{3pt} \vdots
S_N
Output
If, among the words appearing in S at least once, the K-th frequent word does not vary depending on the order of words with the same frequency, print that word; otherwise, print AMBIGUOUS.
Sample Input 1
6 2 abcde caac abcde caac abc caac
Sample Output 1
abcde
caac appears three times, abcde appears twice, and abc appears once. The second most frequent word is abcde.
Sample Input 2
9 3 a a bb bb a ccc bb ccc dddd
Sample Output 2
ccc
a and bb appear three times each, c appears twice, and dddd appears once.
Regardless of the order of a and bb, that have the same frequency, these two come first and second, and ccc comes third, so we should print ccc.
Sample Input 3
7 2 caac abcde caac abc abcde caac abc
Sample Output 3
AMBIGUOUS
caac appears three times, and abcde and abc appear twice each. The second frequent word is not uniquely determined - it can be abcde or abc, so we should print AMBIGUOUS.