Problem:


Problem A: Popularity Estimation

あなたはとあるアニメーション制作会社の企画部長である。昨今のアニメーション制作会社が制作するものは、アニメーションそのものにとどまらない。関連商品、例えば登場キャラクターのフィギュアやキャラクターソングCDなども、重要な収益源なのである。この収益をどれだけ伸ばせるかは、ひとえに企画部長のあなたにかかっているのであった。

当たり前のことだが、こういった関連商品は闇雲に発売すればいいというものではない。商品の開発には多くの時間と予算が必要なためだ。アニメの登場キャラクターのフィギュアを発売するにしても、多くの売上が見込まれる、人気があるキャラクターのものに限らなければならない。

キャラクターの人気度を測る手段の一つが、人気投票である。あなたも今までいくつかの人気投票を企画してきたが、どうやら視聴者はこの企画に不満を抱きつつあるようだ。人気度を測る他の手法の確立が急務である。

そこであなたは、ひとつの仮説を立てた。あるキャラクターの人気度は、そのアニメ本編中における登場時間の総和に比例する、というものだ。あなたはこの仮説を検証するため、それぞれのキャラクターの登場時間を集計するプログラムを書くことにした。

Input

入力は複数のケースからなる。
各ケースは以下のフォーマットで与えられる。

n 
name0 m0 d0,0 ... d0,m0-1
name1 m1 d1,0 ... d1,m1-1
.
.
.
namen-1 mn-1 dn-1,0 ... dn-1,mn-1-1

n はキャラクターの人数を表す。

namei はキャラクターの名前を表す。

mi はキャラクターが映っていた時刻の種類を表す。

mi の後にはmi 個の整数di,j が与えられる。

di,jはキャラクターが映っていた時刻を表す。

入力の終わりはn=0 からなる行によって与えられる

ある時刻に1人のキャラクターのみが画面に映っていた場合、そのキャラクターはnポイントを得ることが出来る。

同時刻に映るキャラクターが1人増える毎に、その時刻に映っていたキャラクターが得られるポイントは1減る。

n人のキャラクターが同時刻に映っていた場合、n人の人それぞれに1ポイントが加算される。

入力は以下の制約を満たす。

2 ≤ n ≤ 20

0 ≤ mi ≤ 30

0 ≤ di,j < 30

i 番目のキャラクターについてdi,j はすべて異なる。

namei はアルファベットの大文字または小文字のみを含み、長さは10以下である。

Output

最小のポイントを持つキャラクターのポイントとその名前を1つの空白で区切って出力せよ。

最小のポイントを持つキャラクターが複数いる場合は名前が辞書順で最小の人を選ぶこと。

Sample input

4
akzakr 2 1 8
fnmyi 5 2 3 4 6 9
tsnukk 5 2 3 4 7 9
yskwcnt 6 3 4 7 8 9 10
4
akzakr 1 2
fnmyi 3 10 11 12
tsnukk 2 1 8
yskwcnt 2 1 8
5
knmmdk 2 13 19
akmhmr 4 13 15 19 22
mksyk 6 3 7 12 13 15 19
skrkyk 3 1 4 8
tmemm 3 1 17 24
5
knmmdk 5 5 6 16 18 26
akmhmr 9 3 4 7 11 14 15 17 18 20
mksyk 5 6 13 25 27 28
skrkyk 4 3 16 23 24
tmemm 3 6 12 20
14
hrkamm 6 4 6 8 10 20 22
mkhsi 6 1 10 12 15 22 27
hbkgnh 2 4 9
chyksrg 8 3 4 12 15 16 20 25 28
mktkkc 6 0 1 8 15 17 20
tknsj 6 6 8 18 19 25 26
yyitktk 3 3 12 18
ykhhgwr 5 3 9 10 11 24
amftm 7 2 6 8 12 13 14 17
mmftm 4 6 12 16 18
rtkakzk 3 14 15 21
azsmur 7 1 2 4 12 15 18 20
iormns 2 4 20
ktrotns 6 7 12 14 17 20 25
14
hrkamm 2 4 21
mkhsi 6 2 3 8 11 18 20
hbkgnh 4 4 16 28 29
chyksrg 5 0 3 9 17 22
mktkkc 2 7 18
tknsj 3 3 9 23
yyitktk 3 10 13 25
ykhhgwr 2 18 26
amftm 3 13 18 22
mmftm 4 1 20 24 27
rtkakzk 2 1 10
azsmur 5 2 5 10 14 17
iormns 3 9 15 16
ktrotns 5 7 12 16 17 20
0

Sample output

7 akzakr
4 akzakr
6 knmmdk
12 tmemm
19 iormns
24 mktkkc

The University of Aizu Programming Contest 2011 Summer

原案: Tomoya Sakai

問題文: Takashi Tayama



Sample input:
4
akzakr 2 1 8
fnmyi 5 2 3 4 6 9
tsnukk 5 2 3 4 7 9
yskwcnt 6 3 4 7 8 9 10
4
akzakr 1 2
fnmyi 3 10 11 12
tsnukk 2 1 8
yskwcnt 2 1 8
5
knmmdk 2 13 19
akmhmr 4 13 15 19 22
mksyk 6 3 7 12 13 15 19
skrkyk 3 1 4 8
tmemm 3 1 17 24
5
knmmdk 5 5 6 16 18 26
akmhmr 9 3 4 7 11 14 15 17 18 20
mksyk 5 6 13 25 27 28
skrkyk 4 3 16 23 24
tmemm 3 6 12 20
14
hrkamm 6 4 6 8 10 20 22
mkhsi 6 1 10 12 15 22 27
hbkgnh 2 4 9
chyksrg 8 3 4 12 15 16 20 25 28
mktkkc 6 0 1 8 15 17 20
tknsj 6 6 8 18 19 25 26
yyitktk 3 3 12 18
ykhhgwr 5 3 9 10 11 24
amftm 7 2 6 8 12 13 14 17
mmftm 4 6 12 16 18
rtkakzk 3 14 15 21
azsmur 7 1 2 4 12 15 18 20
iormns 2 4 20
ktrotns 6 7 12 14 17 20 25
14
hrkamm 2 4 21
mkhsi 6 2 3 8 11 18 20
hbkgnh 4 4 16 28 29
chyksrg 5 0 3 9 17 22
mktkkc 2 7 18
tknsj 3 3 9 23
yyitktk 3 10 13 25
ykhhgwr 2 18 26
amftm 3 13 18 22
mmftm 4 1 20 24 27
rtkakzk 2 1 10
azsmur 5 2 5 10 14 17
iormns 3 9 15 16
ktrotns 5 7 12 16 17 20
0


Sample output:
7 akzakr
4 akzakr
6 knmmdk
12 tmemm
19 iormns
24 mktkkc

Submission status: Wrong Answer

Solution code:
while True:
	player_nun = int(input())
	if player_nun == 0:
		break
	
	#?????????????????????
	whole_data = []
	for i in range(0, player_nun):
		dat = input().split()
		p_data = []
		p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
		whole_data.append(p_data)
	
	print(whole_data)
	#???????????????????????????????????????
	xel = {}
	for i in whole_data:
		for x in i[2:]:
			if x in xel:
				xel[x] += 1
			else:
				xel[x] = 1
	
	#??????????????????????????¢?????????
	score = {}
	for y in xel.keys():
		score[y] = 5 - xel[y]	
	#????????¢??¨????????????????????????????????????
	result = []
	for i in whole_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
	
	#?????????????????????????¬?????????????????±???????	
	min_score = min(x[1] for x in result)
	winners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + sorted(winners)[0])

Submission status: Wrong Answer

Solution code:
while True:
	player_nun = int(input())
	if player_nun == 0:
		break
	
	#?????????????????????
	whole_data = []
	for i in range(0, player_nun):
		dat = input().split()
		p_data = []
		p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
		whole_data.append(p_data)
	
	#???????????????????????????????????????
	xel = {}
	for i in whole_data:
		for x in i[2:]:
			if x in xel:
				xel[x] += 1
			else:
				xel[x] = 1
	
	#??????????????????????????¢?????????
	score = {}
	for y in xel.keys():
		score[y] = 5 - xel[y]	
	#????????¢??¨????????????????????????????????????
	result = []
	for i in whole_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
	
	#?????????????????????????¬?????????????????±???????	
	min_score = min(x[1] for x in result)
	winners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + sorted(winners)[0])

Submission status: Wrong Answer

Solution code:
while 1:
	n=input()
	if n==0:break
	p=[0 for i in range(n)]
	a=sorted([raw_input().split() for i in range(n)])
	for t in range(1,30):
		c=0
		for j in range(n):
			c+=a[j][2:].count(str(t))
		for j in range(n):
			if str(t) in a[j][2:]:
				p[j]+=n-c+1
	print min(p),a[p.index(min(p))][0]

Submission status: Wrong Answer

Solution code:
while 1:
	n=input()
	if n==0:break
	p=[0]*n
	a=sorted([raw_input().split() for i in range(n)])
	for t in range(1,30):
		c=0
		for j in range(n):
			c+=a[j][2:].count(str(t))
		for j in range(n):
			if str(t) in a[j][2:]:
				p[j]+=n-c+1
	print min(p),a[p.index(min(p))][0]

Submission status: Wrong Answer

Solution code:
while 1:
	n=input()
	if n==0:break
	p=[0]*n
	l=[[0]*31 for i in range(n)]
	a=sorted([raw_input().split() for i in range(n)])
	for j in range(n):
		for t in a[j][2:]:
			l[j][int(t)]=1
	for t in range(1,30):
		c=0
		for j in range(n):
			if l[j][t]:c+=1
		for j in range(n):
			if l[j][t]:
				p[j]+=n-c+1
	print min(p),a[p.index(min(p))][0]

Submission status: Wrong Answer

Solution code:
while 1:
	n=input()
	if n==0:break
	p=[0]*n
	l=[[0]*31 for i in range(n)]
	a=sorted([raw_input().split() for i in range(n)])
	for j in range(n):
		for t in a[j][2:]:
			l[j][int(t)]=1
	for t in range(1,30):
		c=0
		for j in range(n):
			if l[j][t]:c+=1
		for j in range(n):
			if l[j][t]:
				if c==n:p[j]+=1
				elif c==1:p[j]+=n
				else:p[j]+=n-c+1
	print min(p),a[p.index(min(p))][0]

Submission status: Accepted

Solution code:
# AOJ 1074: Popularity Estimation
# Python3 2018.7.10 bal4u

while True:
	n = int(input())
	if n == 0: break
	f, tbl = [0]*31, []
	for i in range(n):
		a = input().split()
		nm = a.pop(0)
		m = int(a.pop(0))
		d = list(map(int, a))
		tbl.append([0, nm, d])
		for i in d: f[i] += 1
	for i in range(n):
		for j in tbl[i][2]: tbl[i][0] += n-f[j]+1
	tbl.sort(key=lambda x:(x[0],x[1]))
	print(tbl[0][0], tbl[0][1])

Submission status: Accepted

Solution code:
while True:
    try:
        n = int(input())
    except:
        break

    if n == 0: break

    char = []
    name = []
    times = []

    scores = {i: n + 1 for i in range(30)}

    for i in range(n):
        char = input().split()

        name.append(char[0])
        times.append(list(map(int, char[2:])))

        for t in times[i]:
            scores[t] = scores[t] - 1

    res = {}
    for i in range(n):
        res[i] = sum([scores[t] for t in times[i]])

    score = min(res.values())

    names = [name[i] for i in range(n) if score == res[i]]
    names.sort()
    print(score, names[0])

Submission status: Accepted

Solution code:
from itertools import combinations as C
while True:
    n = int(input())
    if n == 0: break
    d, dd, ddd = {}, {}, {}
    names = []
    for i in range(n):
        nmd = input().split()
        d[nmd[0]] = nmd[2:]
        names.append(nmd[0])
    for cc in list(C(d.items(), n-1)):
        t, tt = [], []
        for c in cc:
            t.append(c[0])
            tt += c[1]
        for name in names:
            if name not in t:
                dd[name] = tt
                break
    for k in d.keys():
        tmp = 0
        for v in d[k]:
            tmp += n-dd[k].count(v)
        ddd[k] = tmp
    ans = sorted(ddd.items(), key=lambda x: (x[1], x[0]))[0]
    print(ans[1], ans[0])

Submission status: Accepted

Solution code:
while True:
	player_nun = int(input())
	if player_nun == 0:
		break
	
	#?????????????????????
	whole_data = []
	for i in range(0, player_nun):
		dat = input().split()
		p_data = []
		p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
		whole_data.append(p_data)
	
	#???????????????????????????????????????
	xel = {}
	for i in whole_data:
		for x in i[2:]:
			if x in xel:
				xel[x] += 1
			else:
				xel[x] = 1
	
	#??????????????????????????¢?????????
	score = {}
	for y in xel.keys():
		score[y] = player_nun + 1 - xel[y]	
	#????????¢??¨????????????????????????????????????
	result = []
	for i in whole_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
	
	#?????????????????????????¬?????????????????±???????	
	min_score = min(x[1] for x in result)
	winners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + sorted(winners)[0])
	
	#??£??????????????????????????????

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:break
    D=[raw_input().split() for i in range(n)]
    D.sort()
    L=[[False]*30 for i in range(n)]
    P=[0]*n
    for i in range(n):
        for j in D[i][2:]:
            L[i][int(j)]=True
    for i in range(30):
        cnt=0
        for j in range(n):
            if L[j][i]:
                cnt+=1
        for j in range(n):
            if cnt==n:
                P[j]+=1
            elif cnt==1 and L[j][i]:
                P[j]+=n
            elif L[j][i]:
                P[j]+=n-cnt+1
    minInt=min(P)
    print minInt,D[P.index(minInt)][0]

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	p=[0]*n
	l=[[0]*31 for i in range(n)]
	a=sorted([raw_input().split() for i in range(n)])
	for j in range(n):
		for t in a[j][2:]:
			l[j][int(t)]=1
	for t in range(30):
		c=0
		for j in range(n):
			if l[j][t]:
				c+=1
		for j in range(n):
			if l[j][t]:
				p[j]+=n-c+1
	print min(p),a[p.index(min(p))][0]

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0:break
	p=[0]*n
	l=[[0]*31 for i in range(n)]
	a=sorted([raw_input().split() for i in range(n)])
	for j in range(n):
		for t in a[j][2:]:
			l[j][int(t)]=1
	for t in range(30):
		c=0
		for j in range(n):
			if l[j][t]:c+=1
		for j in range(n):
			if l[j][t]:p[j]+=n-c+1
	print min(p),a[p.index(min(p))][0]

Submission status: Accepted

Solution code:
from collections import defaultdict
while 1:
    N = int(input())
    if N == 0:
        break
    D = defaultdict(list)
    S = [None]*N
    for i in range(N):
        name, _, *ts = input().split()
        S[i] = name
        for t in map(int, ts):
            D[t].append(i)
    P = [0]*N
    for vs in D.values():
        p = N+1 - len(vs)
        for v in vs:
            P[v] += p
    m = min(P)
    U = [S[i] for i in range(N) if P[i] == m]
    print(m, min(U))

Submission status: Accepted

Solution code:
from collections import defaultdict
while True:
  n = int(input())
  if n == 0:
    break
  score = {}
  dic = defaultdict(list)
  for _ in range(n):
    line = input().split()
    name = line[0]
    score[name] = 0
    for d in line[2:]:
      dic[d].append(name)
  
  for v in dic.values():
    p = n - len(v) + 1
    for name in v:
      score[name] += p
  
  print(*min([(v, k) for k, v in score.items()]))

Submission status: Runtime Error

Solution code:
while True:
	player_nun = int(input())
	if player_nun == 0:
		break
	whole_data = []
	
	xel = {}
	for i in (0, player_nun):
		dat = input().split()
		p_data = []
		p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
			whole_data.append(p_data)
		for x in p_data[2:p_data[1]]:
			if xel.has_key(x) == False:
				0 = xel[x]
				xel[x] += 1
			else:
				xe;[x] += 1
		
	score = {}
	for y in xel.keys():
		5 - xel[y] = score[y]
		
	result = []
	for i in whoe_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
		
	min_score = min(x[1] for x in result)
	winnners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + winners.sorted[0])

Submission status: Runtime Error

Solution code:
while True:
	#player_nun = int(input())
	player_nun = 4
	if player_nun == 0:
		break
	
	#?????????????????????
	whole_data = []
	for i in (0, player_nun):
		#dat = input().split()
		#p_data = []
		#p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
			whole_data.append(p_data)
			
	#???????????????????????????????????????
	xel = {}
	for i in whole_data:
		for x in i[2:]:
			if x in xel:
				xel[x] += 1
			else:
				xel[x] = 1
	
	#??????????????????????????¢?????????
	score = {}
	for y in xel.keys():
		score[y] = 5 - xel[y]	
	#????????¢??¨????????????????????????????????????
	result = []
	for i in whole_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
	
	#?????????????????????????¬?????????????????±???????	
	min_score = min(x[1] for x in result)
	winners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + sorted(winners)[0])

Submission status: Runtime Error

Solution code:
while True:
	player_nun = int(input())
	player_nun = 4
	if player_nun == 0:
		break
	
	#?????????????????????
	whole_data = []
	for i in (0, player_nun):
		dat = input().split()
		p_data = []
		p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
			whole_data.append(p_data)
			
	#???????????????????????????????????????
	xel = {}
	for i in whole_data:
		for x in i[2:]:
			if x in xel:
				xel[x] += 1
			else:
				xel[x] = 1
	
	#??????????????????????????¢?????????
	score = {}
	for y in xel.keys():
		score[y] = 5 - xel[y]	
	#????????¢??¨????????????????????????????????????
	result = []
	for i in whole_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
	
	#?????????????????????????¬?????????????????±???????	
	min_score = min(x[1] for x in result)
	winners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + sorted(winners)[0])

Submission status: Runtime Error

Solution code:
while True:
	player_nun = int(input())
	player_nun = 4
	if player_nun == 0:
		break
	
	#?????????????????????
	whole_data = []
	for i in range(0, player_nun):
		dat = input().split()
		p_data = []
		p_data.append(dat[0])
		for x in dat[1:]:
			p_data.append(int(x))
		whole_data.append(p_data)
	
	print(whole_data)
	#???????????????????????????????????????
	xel = {}
	for i in whole_data:
		for x in i[2:]:
			if x in xel:
				xel[x] += 1
			else:
				xel[x] = 1
	
	#??????????????????????????¢?????????
	score = {}
	for y in xel.keys():
		score[y] = 5 - xel[y]	
	#????????¢??¨????????????????????????????????????
	result = []
	for i in whole_data:
		player_score = []
		player_score.append(i[0])
		player_score.append(0)
		for x in i[2:]:
			player_score[1] += score[x]
		result.append(player_score)
	
	#?????????????????????????¬?????????????????±???????	
	min_score = min(x[1] for x in result)
	winners = []
	for x in result:
		if x[1] == min_score:
			winners.append(x[0])
	print(str(min_score) + " " + sorted(winners)[0])