Problem:


入力候補

携帯電話には、メールなどの文章を効率良く入力するために入力候補を表示する機能が搭載されています。これは、使われる頻度が高い単語を記録しておき、入力された文字を頭文字に持つ単語を入力候補として提示するものです。例えば、普段”computer”という単語を多く入力しているなら、”c”と入力するだけで候補として”computer”が提示されます。このような機能の基本部分を作成してみましょう。

文章、文字を入力とし、その文字を頭文字に持つ単語を出現数の順に出力するプログラムを作成してください。ただし、出現数が同じ単語が複数ある場合は、辞書式順序で出力します。出力する単語は最大5つまでとします。該当する単語が存在しない場合は”NA”と出力してください。

入力

複数のデータセットが与えられます。入力の終わりはゼロひとつで表されます。各データセットは以下の形式で与えられます。

n
line1
line2
:
linen
k

1行目に文章の行数 n (1 ≤ n ≤ 10) が与えられます。続く n 行に文章が与えられます。文章は半角英小文字と半角空白からなり、１行の文字数は1文字以上1024文字以下とします。空白によって区切られる単語は1文字以上20文字以下です。

続く行に頭文字 k が半角英字で与えられます。

データセットの数は 100 を超えません。

出力

データセットごとに、指定された文字を頭文字にもつ単語または”NA” を出力します。

入力例

1
ben likes bananas the best among many fruits because bananas are sweet and cheap
b
1
winners get to visit aizu and the university of aizu and make many friends as well
a
3
ask alex about
the answer for the
assignment on android apps
a
2
programming is both
a sport and an intellectual puzzle
c
0

出力例

bananas because ben best
aizu and as
about alex android answer apps
NA



Sample input:
1
ben likes bananas the best among many fruits because bananas are sweet and cheap
b
1
winners get to visit aizu and the university of aizu and make many friends as well
a
3
ask alex about
the answer for the
assignment on android apps
a
2
programming is both
a sport and an intellectual puzzle
c
0


Sample output:
bananas because ben best
aizu and as
about alex android answer apps
NA

Submission status: Wrong Answer

Solution code:
import collections as C
while True:
    n = int(input())
    if n == 0:
        break
    d = {}
    for _ in range(n):
        tmp = input().split()
        for t in tmp:
            k = t[0]
            d[k] = [t] if k not in d else d[k]+[t]
    k = input()
    words = d.get(k, 0)
    if words:
        res = sorted(C.Counter(words).most_common(), key=lambda x: (x[0], x[1]))
        print(*[k for k, v in res])
    else:
        print("NA")

Submission status: Wrong Answer

Solution code:
import collections as C
while True:
    n = int(input())
    if n == 0:
        break
    d = {}
    for _ in range(n):
        tmp = input().split()
        for t in tmp:
            k = t[0]
            d[k] = [t] if k not in d else d[k]+[t]
    k = input()
    words = d.get(k, 0)
    if words:
        res = sorted(C.Counter(words).most_common(5), key=lambda x: (x[0], x[1]))
        print(*[k for k, v in res])
    else:
        print("NA")

Submission status: Wrong Answer

Solution code:
from collections import Counter

while True:
    n = int(input())
    if n == 0:
        break
    dataset = [input().split() for _ in range(n)]
    counter = Counter()
    k = input()
    for line in dataset:
        for word in line:
            if word[0] == k:
                counter[word] += 1
    candidates = sorted(counter.items(), key=lambda x: (x[0]))[:5]
    print(" ".join(candidate[0] for candidate in candidates) if candidates else "NA")

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    c = {}
    for _ in range(n):
        s = input().split()
        for e in s:
            if e in c:c[e] += 1
            else:c[e] = 1
    c = [(e, c[e]) for e in c.keys()]
    c.sort(key = lambda x:x[1], reverse = True)
    c.sort(key = lambda x:x[0])
    s = input()
    a = []
    for i in range(len(c)):
        if c[i][0][0] == s:a.append(c[i][0])
    if a == []:print("NA")
    else:print(*a)

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    c = {}
    for _ in range(n):
        s = input().split()
        for e in s:
            if e in c:c[e] += 1
            else:c[e] = 1
    c = [(e, c[e]) for e in c.keys()]
    c.sort(key = lambda x:x[1], reverse = True)
    c.sort(key = lambda x:x[0])
    s = input()
    a = []
    for i in range(len(c)):
        if c[i][0][0] == s:a.append(c[i][0])
    if a == []:print("NA")
    else:print(*a[:5])

Submission status: Wrong Answer

Solution code:
while 1:
	n=input()
	if n==0:break
	dic={}
	for i in range(n):
		msg=raw_input().split()
		for word in msg:
			if word in dic:
				dic[word]+=1
			else:
				dic[word]=1
	alpha=raw_input()
	flag=0
	for k,v in sorted(dic.items(),key=lambda x:x[1]):
		if k[0]==alpha:
			print k,
			flag=1
	print "" if flag else "NA"

Submission status: Accepted

Solution code:
class T:
    def __init__(self):
        self.min_count = 0
        self.words = {}

while True:
    data = {chr(c): T() for c in range(ord('a'), ord('z') + 1)}
    n = int(input())
    if not n:
        break
    for i in range(n):
        for s in input().split():
            d = data[s[0]]
            if s in d.words:
                d.words[s] -= 1
            else:
                d.words[s] = -1
            if d.words[s] < d.min_count:
                d.min_count = d.words[s]
    
    res = ' '.join(map(lambda v: v[1], sorted(list(map(lambda a: a[::-1], data[input()].words.items())), reverse=True)[:-6:-1]))
    print(res if res else 'NA')

Submission status: Accepted

Solution code:
from collections import Counter
dic = {}


def add(x):
    if x[0] not in dic:
        dic[x[0]] = Counter()

    dic[x[0]][x] += 1

while 1:
    dic = {}
    n = int(input())
    if n == 0:break
    for l in [input() for i in range(n)]:
        for w in l.split():
            add(w)
    k = input()
    if k not in dic:
        print('NA')
    else:
        print(' '.join(map(lambda x:x[0],sorted(dic[k].items(), key=lambda x: (-x[1],x[0]))[:5])))

Submission status: Accepted

Solution code:
import sys
import string
import operator
from collections import Counter

f = sys.stdin

while True:    
    n = int(f.readline())
    if n == 0:
        break
    counters = {c:Counter() for c in string.ascii_lowercase}
    for i in range(n):
        for word in f.readline().strip().split():
            counters[word[0]].update([word])
    c = f.readline().strip()

    candidate = counters[c].most_common()
    candidate.sort(key=operator.itemgetter(0))
    candidate.sort(key=operator.itemgetter(1), reverse=True)
    candidate = [word for word, count in candidate[:5]]
    if len(candidate) == 0:
        print('NA')
    else:
        print(*candidate)

Submission status: Accepted

Solution code:
def f():
    c = None
    s = None
    ans = []
    for i, t in enumerate(sorted(data.items(), key=lambda x: x[1], reverse=True)):
        ans.append(t[0])
        if c is None:
            c = t[1]
            s = i
        else:
            if c != t[1] and 4 <= i:
                ans = ans[:s]+sorted(ans[s:i])+ans[i:]
                break
            elif c != t[1]:
                ans = ans[:s]+sorted(ans[s:i])+ans[i:]
                c = t[1]
                s = i
    else:
        ans = ans[:s]+sorted(ans[s:i+1])+ans[i+1:]
    return ' '.join(ans[:5])

while True:
    n = int(raw_input())
    if n == 0: break
    lis = [raw_input() for i in range(n)]
    key = raw_input()
    data = {}
    for line in lis:
        for string in line.split():
            if string[0] == key:
                if not string in data:
                    data[string] = 1
                else:
                    data[string] += 1
    if data:
        print f()
    else:
        print 'NA'

Submission status: Accepted

Solution code:
while True:
    n = input()
    if n == 0:
        break
    candidate = {}
    for i in range(n):
        words = raw_input().split(" ")
        for word in words:
            for key in candidate.iterkeys():
                if key == word:
                    candidate[key] += 1
                    break
            else:
                candidate[word] = 1
    head = raw_input()
    find_words = {}
    for key in candidate.iterkeys():
        if key[0] == head:
            find_words[key] = candidate[key]
    size_of_words = len(find_words)
    if size_of_words == 0:
        print "NA"
    else:
        for_print = []
        i = 1
        while len(find_words) != 0:
            eq_num_list = []
            for key in sorted(find_words.items()):
                s = key[0]
                if find_words[key[0]] == i:
                    eq_num_list.append(s)
                    find_words.pop(key[0])

            i += 1
            eq_num_list.reverse()
            for_print += eq_num_list

        for_print.reverse()
        print " ".join(for_print[0:5])

Submission status: Accepted

Solution code:
# Aizu Problem 0242: Input Candidates

import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


while True:
    n = int(input())
    if n == 0:
        break
    text = []
    count = {}
    for _ in range(n):
        for word in input().split():
            count[word] = count.get(word, 0) + 1
    char = input().strip()
    out = []
    for key, value in sorted(sorted(count.items()), key=lambda x: -x[1]):
        if key[0] == char:
            out.append(key)
        if len(out) == 5:
            break
    if len(out) == 0:
        print("NA")
    else:
        print(' '.join(out))

Submission status: Accepted

Solution code:
# AOJ 0242: Input Candidates
# Python3 2018.6.25 bal4u

while 1:
	n = int(input())
	if n == 0: break
	idx = {}
	dict = {}
	for i in range(n):
		for j in list(input().split()):
			if j in dict: dict[j] += 1
			else:
				dict[j] = 1
				if j[0] not in idx:
					idx[j[0]] = []
				idx[j[0]].append(j)
	k = input()
	if k not in idx: print("NA")
	else:
		a = []
		for j in idx[k]: a.append((j, dict[j]))
		a = sorted(a, key=lambda x:(-x[1],x[0]))
		w = len(a)
		if w > 5: w = 5
		ans = []
		for j in range(w): ans.append(a[j][0])
		print(*ans)

Submission status: Accepted

Solution code:
# AOJ 0242: Input Candidates
# Python3 2018.6.25 bal4u

while 1:
	n = int(input())
	if n == 0: break
	idx, dict = {}, {}
	for i in range(n):
		for j in list(input().split()):
			if j in dict: dict[j] += 1
			else:
				dict[j] = 1
				if j[0] not in idx:	idx[j[0]] = []
				idx[j[0]].append(j)
	k = input()
	if k not in idx: print("NA")
	else:
		a, ans = [], []
		for j in idx[k]: a.append((j, dict[j]))
		a.sort(key=lambda x:(-x[1],x[0]))
		w = min(len(a), 5)
		for j in range(w): ans.append(a[j][0])
		print(*ans)

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    c = {}
    for _ in range(n):
        s = input().split()
        for e in s:
            if e in c:c[e] += 1
            else:c[e] = 1
    c = [(e, c[e]) for e in c.keys()]
    c.sort(key = lambda x:x[0])
    c.sort(key = lambda x:x[1], reverse = True)
    s = input()
    a = []
    for i in range(len(c)):
        if c[i][0][0] == s:a.append(c[i][0])
    if a == []:print("NA")
    else:print(*a[:5])

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  dic = {}
  for _ in range(n):
    ss = input().split()
    for s in ss:
      if s[0] in dic:
        dic[s[0]].append(s)
      else:
        dic[s[0]] = [s]
  k = input()
  if k not  in dic:
    print("NA")
    continue
  lst = dic[k]
  k_dic = {}
  for s in lst:
    if s in k_dic:
      k_dic[s] += 1
    else:
      k_dic[s] = 1
  ans = list(k_dic.items())
  ans.sort()
  ans.sort(key=lambda t:-t[1])
  print(*[k for k, v, in ans][:5])

Submission status: Accepted

Solution code:
while True:
	n = input()
	if n == 0: break
	words = []
	for i in xrange(n):
		words += raw_input().split()
	candidates = {}
	for w in set(words):
		c = words.count(w)
		candidates.setdefault(w[0], [])
		candidates[w[0]] += [(-c, w)]
	try:
		print " ".join([w for c, w in sorted(candidates[raw_input()])][:5])
	except KeyError:
		print "NA"

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
while True:
    n=input()
    if n==0:break
    dic,L=dd(dict),[]
    for i in range(n):
        L+=raw_input().split()
    k=raw_input()
    for i in L:
        if i not in dic[i[0]]:
            dic[i[0]][i]=-1
        else:
            dic[i[0]][i]-=1
    if k not in dic:
        print "NA"
    else:
        print " ".join(i[1] for i in sorted([(j,i) for i,j in dic[k].items()])[\
:5])

Submission status: Accepted

Solution code:
# Input Candidates

def compare(x, y):
    if x[1] == y[1]:
        return cmp(x[0], y[0])
    else:
        return cmp(x[1], y[1]) * -1


while True:
    n = int(raw_input())
    if n == 0:
        break

    dic = {}
    for i in range(n):
        words = raw_input().strip().split()
        for word in words:
            dic[word] = dic.setdefault(word, 0) + 1

    candidate = []
    key = raw_input().strip()
    for k, v in dic.items():
        if k.startswith(key):
            candidate.append((k, v))

    candidate.sort(compare)

    if candidate:
        print ' '.join([word[0] for word in candidate[:5]])
    else:
        print 'NA'

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	dic={}
	for i in range(n):
		msg=raw_input().split()
		for word in msg:
			if word in dic:
				dic[word]+=1
			else:
				dic[word]=1
	alpha=raw_input()
	ans=[]
	for k,v in sorted(sorted(dic.items()),key=lambda x:x[1],reverse=True):
		if k[0]==alpha:ans.append(k)
	print " ".join(map(str,ans)) if len(ans)>0 else "NA"

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	dic={}
	for i in range(n):
		msg=raw_input().split()
		for word in msg:
			try:dic[word]+=1
			except:dic[word]=1
	alpha=raw_input()
	ans=[]
	for k,v in sorted(sorted(dic.items()),key=lambda x:x[1],reverse=True):
		if k[0]==alpha:ans.append(k)
	print " ".join(map(str,ans)) if len(ans)>0 else "NA"

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0: break
    line = [list(input().split()) for _ in range(n)]
    k = input()
    words = {}
    for i in line:
        for word in i:
            if word in words:
                words[word] += 1
            else:
                words[word] = 1
    cand = {key: v for key, v in words.items() if key[0] == k}
    items = cand.items()
    sitems = sorted(items, key=lambda x: x[1], reverse=True)
    prev = 0
    tmp = []
    ans = []
    for i in sitems:
        if prev != i[1]:
            tmp.sort()
            ans.extend(tmp)
            tmp = []
        tmp.append(i[0])
        prev = i[1]
    tmp.sort()
    ans.extend(tmp)
    if len(ans) > 5: ans = ans[0:5]
    if len(ans) == 0:
        print("NA")
    else:
        print(' '.join(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Input Candidates
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0242

"""
import sys


from string import ascii_lowercase
from collections import defaultdict

def solve(n):
    d = {ch: defaultdict(int) for ch in ascii_lowercase}
    for _ in range(n):
        for word in input().split():
            d[word[0]][word] += 1
    k = input()
    return [a for _, a in sorted([(-v, k) for k, v in d[k].items()])[:5]] \
        if d[k] else ['NA']


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        ans = solve(n)
        print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# 参考:http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3286382#1

while 1:
    n = int(input())
    if n == 0:
        break

    words,dic = [],[]
    for i in range(n):
        data = list(input().split())
        for d in data:
            words.append(d)

    k = input()
    setWords = list(set(words))

    for w in setWords:
        if w[0] == k:
            dic.append([w, words.count(w)])

    dic = sorted(dic, key=lambda x: (-x[1], x[0]))
    if dic == []:
        print("NA")
    else:
        print(' '.join(d[0] for d in dic[:5]))

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
while 1:
    N = int(input())
    if N == 0:
        break
    mp = defaultdict(list)
    for i in range(N):
        for word in input().split():
            mp[word[0]].append(word)
    k = input()
    c = Counter(mp[k])
    if len(c) == 0:
        print("NA")
    else:
        print(*sorted(c, key=lambda x: (-c[x], x))[:5])

Submission status: Accepted

Solution code:
from collections import defaultdict

while True:
    n = int(input())
    
    if n==0:
        break
    
    initial = defaultdict(set)
    cnt = defaultdict(int)
    
    for _ in range(n):
        l = list(input().split())
        
        for li in l:
            initial[li[0]].add(li)
            cnt[li] += 1
    
    k = input()
    ans = list(initial[k])
    
    if len(ans)==0:
        print('NA')
        continue
    
    ans.sort()
    ans.sort(key=lambda w: cnt[w], reverse=True)
    
    if len(ans)<5:
        print(*ans)
    else:
        print(*ans[:5])

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


class Info:
    def __init__(self,arg_word,arg_count):
        self.word= arg_word
        self.count = arg_count

    def __lt__(self,another):
        if self.count != another.count:
            return self.count > another.count
        else:
            return self.word < another.word


while True:

    num_row = int(input())
    if num_row == 0:
        break

    DICT = {} #単語→ID
    rev_DICT = {} #ID→単語
    COUNT = {} #IDをキーとして、出現数を計上
    num_words = 0

    for _ in range(num_row):
        words = input().split()
        for i in range(len(words)):
            if words[i] in DICT:
                COUNT[DICT[words[i]]] += 1
            else:
                DICT[words[i]] = num_words
                rev_DICT[num_words] = words[i]
                num_words += 1
                COUNT[DICT[words[i]]] = 1

    head_word = str(input())
    table = []
    for i in range(num_words):
        word = rev_DICT[i]
        if word[0] != head_word:
            continue
        table.append(Info(word,COUNT[DICT[word]]))

    if len(table) == 0:
        print("NA")
        continue

    table.sort()
    print("%s"%(table[0].word),end = "")
    for i in range(1,min(5,len(table))):
        print(" %s"%(table[i].word),end="")
    print()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class Word:
    def __init__(self, word, cnt):
        self.word = word
        self.cnt = cnt

    def __lt__(self, other):
        if self.cnt == other.cnt:
            return self.word < other.word
        else:
            return self.cnt > other.cnt
            

while True:
    N = int(input())
    if N == 0:
        break
    
    str = []
    for l in range(N):
        str.extend(input().split())

    str.sort()
    k = input()
    words = []

    for i in range(len(str)):
        if str[i][0] == k:
            if len(words) > 0 and words[-1].word == str[i]:
                words[-1].cnt = words[-1].cnt + 1
            else:
                t = Word(str[i],1)
                words.append(t)

    if len(words) == 0:
        print("NA")
    elif len(words) < 5:
        words.sort()
        for i in range(len(words)-1):
            print(words[i].word, end = " ")
        print(words[-1].word)
    else:
        words.sort()
        for i in range(4):
            print(words[i].word, end = " ")
        print(words[4].word)

Submission status: Accepted

Solution code:
import collections
while 1:
    n=int(input())
    if n==0:break
    words=[]
    words_match=[]
    count=0
    ans=[]
    for i in range(n):
        words+=list(map(str,input().split()))
    keyword=input()
    words.sort()
    for i in words:
        if keyword==i[0]:words_match.append(i)
    count_dict = collections.Counter(words_match)
    ans=count_dict.most_common(5)
    if ans==[]:
        print("NA")
    else:
        for i in range(len(ans)):
            if i>0:print(" ",end="")
            print(ans[i][0],end="")
        print()

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break

    word = []
    for _ in range(n):
        data = list(input().split())
        for d in data:
            word.append(d)

    k = input()
    word_u = list(set(word))
    dic = []
    for w in word_u:
        if w[0] == k:
            dic.append([w, word.count(w)])

    dic = sorted(dic, key=lambda x: (-x[1], x[0]))
    if dic == []:
        print("NA")
    else:
        print(' '.join(d[0] for d in dic[:5]))

Submission status: Runtime Error

Solution code:
import sys
import string
from collections import Counter

f = sys.stdin

while True:    
    n = int(f.readline())
    if n == 0:
        break
    counters = {c:Counter() for c in string.ascii_lowercase}
    for i in range(n):
        for word in f.readline().strip().split():
            counters[word[0]].update([word])
    c = f.readline().strip()

    candidate = counters[c].most_common()
    candidate.sort(key=operator.itemgetter(0))
    candidate.sort(key=operator.itemgetter(1), reverse=True)
    candidate = [word for word, count in candidate[:5]]
    if len(candidate) == 0:
        print('NA')
    else:
        print(*candidate)

Submission status: WA: Presentation Error

Solution code:
while 1:
	n=input()
	if n==0:break
	dic={}
	for i in range(n):
		msg=raw_input().split()
		for word in msg:
			if word in dic:
				dic[word]+=1
			else:
				dic[word]=1
	alpha=raw_input()
	flag=0
	for k,v in sorted(sorted(dic.items()),key=lambda x:x[1],reverse=True):
		if k[0]==alpha:
			print k,
			flag=1
	print "" if flag else "NA"