Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

You are given a score log of a football match between two teams. Every time when one of the teams scored a goal, the name of that team was written in the score log on a separate line.
At the end of the match, the team that scored strictly more goals than the other team wins the match. If both teams scored an equal number of goals, the match ends in a tie. Determine the name of the winning team or that the match ended in a tie.

------ Input ------ 

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer n denoting the number of records in the score log (the total number of goals scored during the match).
Each of the following n lines contains a string s denoting the name of the team that scored a goal.

------ Output ------ 

For each test case, print a single line containing one string — the name of the winning team or "Draw" (without quotes) in case of a tie.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$0 ≤ n ≤ 10^{5}$
$1 ≤ |s| ≤ 20$
$s consists only of lowercase English letters$
$sum of n over all test cases ≤ 10^{5}$
$for each test case, there are at most two different team names$

----- Sample Input 1 ------ 
2
4
ab
bc
bc
ab
3
xxx
yyy
yyy
----- Sample Output 1 ------ 
Draw
yyy

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Implementation

Complete search


Solutions:
for p in range(int(input())):
	a = []
	(m, n) = (0, 0)
	for i in range(int(input())):
		c = input()
		a.append(c)
	for i in a:
		if i == a[0]:
			m += 1
		else:
			n += 1
			d = i
	if m == n:
		print('Draw')
	elif m < n:
		print(d)
	else:
		print(a[0])


for _ in range(int(input())):
	a = int(input())
	b = {}
	e = 1
	for i in range(a):
		c = input()
		if c not in b:
			b[c] = 1
		else:
			b[c] = b[c] + 1
	if len(b) < 1:
		print('Draw')
		continue
	elif len(b) == 1:
		print(*b)
		continue
	o = b[list(b.keys())[0]]
	o1 = b[list(b.keys())[1]]
	if o == o1:
		print('Draw')
	elif o > o1:
		print(list(b.keys())[0])
	else:
		print(list(b.keys())[1])


for _ in range(int(input())):
	n = int(input())
	p = 0
	e = 0
	r = 0
	for i in range(n):
		s = input()
		if p == 0:
			x = s
			e = e + 1
			p = 1
		elif s == x:
			e = e + 1
		else:
			y = s
			r = r + 1
	if r > e:
		print(y)
	elif r == e:
		print('Draw')
	else:
		print(x)


for _ in range(int(input())):
	a = int(input())
	lst = []
	for i in range(a):
		lst.append(input())
	count1 = 0
	count2 = 0
	for j in range(0, len(lst)):
		t1 = lst[0]
		if t1 == lst[j]:
			count1 = count1 + 1
		else:
			t2 = lst[j]
			count2 = count2 + 1
	if count1 > count2:
		print(t1)
	elif count2 > count1:
		print(t2)
	else:
		print('Draw')


test = int(input())
for i in range(test):
	n = int(input())
	d = {}
	for j in range(n):
		s = input()
		if s in d:
			d[s] += 1
		else:
			d[s] = 1
	a = 0
	team1 = ''
	team2 = ''
	ans1 = 0
	ans2 = 0
	for (key, value) in d.items():
		if a == 0:
			team1 = key
			ans1 = value
			a = 1
		else:
			team2 = key
			ans2 = value
	if ans1 == ans2:
		print('Draw')
	elif ans1 > ans2:
		print(team1)
	else:
		print(team2)


for _ in range(int(input())):
	n = int(input())
	lo = []
	for _ in range(n):
		lo.append(input())
	s = list(set(lo))
	if n == 0:
		print('Draw')
	elif len(s) == 1:
		print(s[0])
	else:
		t1 = lo.count(s[0])
		t2 = lo.count(s[1])
		if t1 > t2:
			print(s[0])
		elif t2 > t1:
			print(s[1])
		else:
			print('Draw')


for _ in range(int(input())):
	n = int(input())
	d = dict()
	for i in range(n):
		t = input()
		d[t] = d.get(t, 0) + 1
	(m, ans) = (0, 'Draw')
	for (x, y) in d.items():
		if y > m:
			(m, ans) = (y, x)
		elif y == m:
			ans = 'Draw'
	print(ans)


t = int(input())
for yuafg in range(t):
	n = int(input())
	if n == 0:
		print('Draw')
		continue
	if n == 1:
		log = str(input())
		print(log)
		continue
	log = [str(input()) for fref in range(n)]
	t1 = 0
	t2 = 0
	x = log[0]
	y = ''
	for i in log:
		if i == x:
			t1 += 1
		else:
			y = i
			t2 += 1
	if t1 == t2:
		print('Draw')
	elif t1 > t2:
		print(x)
	else:
		print(y)


for _ in range(int(input())):
	N = int(input())
	D = {}
	for n in range(N):
		x = input()
		if x in D:
			D[x] += 1
		else:
			D[x] = 1
	teams = list(D.keys())
	scores = list(D.values())
	if len(teams) == 1:
		print(teams[0])
	elif len(teams) == 2:
		if scores[0] == scores[1]:
			print('Draw')
		elif scores[0] > scores[1]:
			print(teams[0])
		else:
			print(teams[1])
	else:
		print('Draw')


for i in range(int(input())):
	m = int(input())
	l = []
	for i in range(m):
		s = input()
		l.append(s)
	l1 = []
	l2 = []
	for ele in l:
		if len(l1) < 1:
			l1.append(ele)
		elif ele in l1:
			l1.append(ele)
		else:
			l2.append(ele)
	if len(l1) == len(l2):
		print('Draw')
	elif len(l1) > len(l2):
		print(l1[0])
	else:
		print(l2[0])


t = int(input())
for i in range(t):
	l = []
	n = int(input())
	for i in range(n):
		l.append(input())
	l1 = []
	l2 = []
	for team in l:
		if len(l1) < 1:
			l1.append(team)
		elif team in l1:
			l1.append(team)
		else:
			l2.append(team)
	if len(l1) == len(l2):
		print('Draw')
	elif len(l1) > len(l2):
		print(l1[0])
	else:
		print(l2[0])


t = int(input())
for i in range(t):
	n = int(input())
	lst = []
	for j in range(n):
		lst.append(input())
	un = []
	d = {}
	for _ in lst:
		if _ not in un:
			un.append(_)
			d[_] = lst.count(_)
	if len(un) > 1:
		if d[un[0]] > d[un[1]]:
			print(un[0])
		elif d[un[1]] > d[un[0]]:
			print(un[1])
		else:
			print('Draw')
	elif len(un) == 1:
		print(un[0])
	else:
		print('Draw')


n = int(input())
for i in range(n):
	goals = int(input())
	l = []
	for i in range(goals):
		l.append(input())
	teams = set(l)
	if len(teams) == 2:
		teams = list(teams)
		if l.count(teams[0]) > l.count(teams[1]):
			print(teams[0])
		elif l.count(teams[0]) < l.count(teams[1]):
			print(teams[1])
		else:
			print('Draw')
	elif len(teams) == 1:
		print(l[0])
	else:
		print('Draw')


t = int(input())
for i in range(t):
	n = int(input())
	team_dict = dict()
	TeamA = 0
	TeamB = 0
	for j in range(n):
		team = input()
		if j == 0:
			FirstTeam = team
		if FirstTeam != team:
			SecondTeam = team
			TeamB += 1
		else:
			TeamA += 1
	if TeamA == TeamB:
		print('Draw')
	elif TeamA > TeamB:
		print(FirstTeam)
	else:
		print(SecondTeam)


for _ in range(int(input())):
	t1 = []
	t2 = []
	for i in range(int(input())):
		s = input()
		if s in t1 or i == 0:
			t1.append(s)
		else:
			t2.append(s)
	if len(t1) > len(t2):
		print(t1[0])
	elif len(t1) < len(t2):
		print(t2[0])
	else:
		print('Draw')


t = int(input())
for t in range(t):
	n = int(input())
	t1 = []
	t2 = []
	for i in range(n):
		s1 = input()
		if s1 in t1 or i == 0:
			t1.append(s1)
		else:
			t2.append(s1)
	if len(t1) > len(t2):
		print(t1[0])
	elif len(t2) > len(t1):
		print(t2[0])
	else:
		print('Draw')


t = int(input())
for t in range(t):
	n = int(input())
	(team1, team2) = ([], [])
	for i in range(n):
		s = input()
		if s in team1 or i == 0:
			team1.append(s)
		else:
			team2.append(s)
	if len(team1) > len(team2):
		print(team1[0])
	elif len(team2) > len(team1):
		print(team2[0])
	else:
		print('Draw')


for i in range(int(input())):
	n = int(input())
	(l1, l2) = ([], [])
	for i in range(1, n + 1):
		s = input()
		if s in l1 or i == 1:
			l1.append(s)
		else:
			l2.append(s)
	if len(l1) > len(l2):
		print(l1[0])
	elif len(l1) == len(l2):
		print('Draw')
	else:
		print(l2[0])


t = int(input())
for i in range(t):
	n = int(input())
	d = {}
	for i in range(n):
		s = input()
		if s in d:
			d[s] += 1
		else:
			d[s] = 1
	if n == 0:
		print('Draw')
	else:
		teams = list(d.keys())
		goals = list(d.values())
		if len(teams) == 1:
			print(teams[0])
		elif goals[0] == goals[-1]:
			print('Draw')
		elif goals[0] > goals[-1]:
			print(teams[0])
		else:
			print(teams[-1])


t = int(input())
for _ in range(t):
	N = int(input())
	a = ''
	a1 = ''
	b1 = 0
	b2 = 0
	for _ in range(N):
		s = input()
		if a == '':
			a = s
		if a == s:
			b1 += 1
		else:
			a1 = s
			b2 += 1
	if b2 > b1:
		print(a1)
	elif b2 < b1:
		print(a)
	else:
		print('Draw')


for _ in range(int(input())):
	n = int(input())
	d = 'a'
	c1 = 0
	c2 = 0
	for _ in range(n):
		s = input()
		if d == 'a':
			d = s
		if d == s:
			c1 += 1
		else:
			d1 = s
			c2 += 1
	if c2 > c1:
		print(d1)
	elif c2 < c1:
		print(d)
	else:
		print('Draw')


for t in range(int(input())):
	n = int(input())
	array = []
	for i in range(n):
		ele = input()
		array.append(ele)
	for i in range(n):
		if array[0] != array[i]:
			team1 = array[0]
			team2 = array[i]
	t1score = array.count(team1)
	t2score = array.count(team2)
	if t1score > t2score:
		print(team1)
	elif t2score > t1score:
		print(team2)
	else:
		print('Draw')


for _ in range(int(input())):
	a = int(input())
	l = []
	if a == 0:
		print('Draw')
	else:
		for i in range(a):
			s = input()
			l.append(s)
		m = l[0]
		(a1, a2) = (0, 0)
		for i in l:
			if i != m:
				p = i
				pass
			if i == l[0]:
				a1 += 1
			else:
				a2 += 1
		if a1 == a2:
			print('Draw')
		elif a1 > a2:
			print(l[0])
		else:
			print(p)


T = int(input())
for i in range(T):
	n = int(input())
	lst = []
	for i in range(n):
		lst.append(input().strip())
	(c, c1, ind) = (0, 0, 0)
	for i in lst:
		if i == lst[0]:
			c += 1
		else:
			ind = lst.index(i)
			c1 += 1
	if c == c1:
		print('Draw')
	elif c > c1:
		print(lst[0])
	else:
		print(lst[ind])


for _ in range(int(input())):
	n = int(input())
	d = [input() for i in range(n)]
	x = list(set(d))
	a = 0
	b = 0
	for i in d:
		if i == x[0]:
			a += 1
		else:
			b += 1
	if a > b:
		print(x[0])
	elif b > a:
		print(x[1])
	else:
		print('Draw')


t = int(input())
for _ in range(t):
	n = int(input())
	lis = []
	for i in range(n):
		s = input()
		lis.append(s)
	x = list(set(lis))
	c1 = 0
	c2 = 0
	for i in range(len(lis)):
		if lis[i] == x[0]:
			c1 += 1
		elif lis[i] == x[1]:
			c2 += 1
	if c1 > c2:
		print(x[0])
	elif c2 > c1:
		print(x[1])
	else:
		print('Draw')


t = int(input())
for _ in range(t):
	H = {}
	n = int(input())
	for _ in range(n):
		goalTeam = input()
		H[goalTeam] = H.get(goalTeam, 0) + 1
	(x, y, t1, t2) = (0, 0, '', '')
	for team in H:
		if x == 0:
			x = H[team]
			t1 = team
		else:
			y = H[team]
			t2 = team
	if x == y:
		print('Draw')
	elif x > y:
		print(t1)
	else:
		print(t2)


for test_ in range(int(input())):
	n = int(input())
	temp = [input() for i in range(n)]
	count = 0
	oppo = ''
	for i in temp:
		if i == temp[0]:
			count += 1
		else:
			count -= 1
		if i != temp[0] and oppo == '':
			oppo = i
	if count == 0:
		print('Draw')
	elif count > 0:
		print(temp[0])
	else:
		print(oppo)


for tc in range(int(input())):
	n = int(input())
	if n == 0:
		print('Draw')
		continue
	l = []
	for i in range(n):
		s = input()
		l.append(s)
	t = list(set(l))
	if len(t) == 1:
		print(*t)
	elif l.count(t[0]) > l.count(t[1]):
		print(t[0])
	elif len(t) == 0 or l.count(t[0]) == l.count(t[1]):
		print('Draw')
	else:
		print(t[1])


for i in range(int(input())):
	n = int(input())
	t = []
	for i in range(n):
		t.append(input())
	s = set(t)
	if len(s) == 1:
		print(''.join(s))
	elif len(s) == 0 or t.count(t[0]) == len(t) / 2:
		print('Draw')
	elif t.count(t[0]) > len(t) / 2:
		print(t[0])
	else:
		s.remove(t[0])
		print(''.join(s))


for x in range(int(input())):
	n = int(input())
	T1 = 0
	T2 = 0
	scores = []
	for x in range(n):
		scores.append(str(input()))
		if x == 0:
			T1 += 1
		elif x > 0:
			if scores[0] == scores[x]:
				T1 += 1
			else:
				y = x
				T2 += 1
	if T1 > T2:
		print(scores[0])
	elif T1 < T2:
		print(scores[y])
	else:
		print('Draw')


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
		s = set(l)
		p = list(s)
	first = 0
	sec = 0
	for i in l:
		if i == p[0]:
			first += 1
		else:
			sec += 1
	if first > sec:
		print(p[0])
	elif first < sec:
		print(p[1])
	else:
		print('Draw')


def Solve(d, n):
	if n == 0:
		return 'Draw'
	elif n == 1:
		return str(list(d.keys()))
	l = list(d.items())
	if l[0][1] == l[1][1]:
		return 'Draw'
	elif l[0][1] >= l[1][1]:
		return l[0][0]
	elif l[0][1] < l[1][1]:
		return l[1][0]
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		team = input()
		if i == 0:
			a.append(team)
		elif team in a:
			a.append(team)
		else:
			b.append(team)
	if len(a) == len(b):
		print('Draw')
	elif len(a) > len(b):
		print(a[0])
	else:
		print(b[0])


u = int(input())
for _ in range(u):
	n = int(input())
	li = []
	ls = []
	for i in range(n):
		v = input()
		if i == 0:
			li.append(v)
		elif v in li:
			li.append(v)
		else:
			ls.append(v)
	if len(li) == len(ls):
		print('Draw')
	elif len(li) > len(ls):
		print(li[0])
	else:
		print(ls[0])


t = int(input())
for _ in range(t):
	n = int(input())
	li = []
	ls = []
	for i in range(n):
		a = input()
		if i == 0:
			li.append(a)
		elif a in li:
			li.append(a)
		else:
			ls.append(a)
	if len(li) == len(ls):
		print('Draw')
	elif len(li) > len(ls):
		print(li[0])
	else:
		print(ls[0])


t = int(input())
for z in range(t):
	score = [0, 0]
	team = []
	n = int(input())
	for i in range(n):
		s = input()
		if s not in team:
			team.append(s)
			score[team.index(s)] = 1
		else:
			score[team.index(s)] += 1
	if score[0] < score[1]:
		print(team[1])
	elif score[0] > score[1]:
		print(team[0])
	else:
		print('Draw')


t = input()
for c in range(0, int(t)):
	n = int(input())
	f = {}
	for i in range(n):
		x = input()
		if x in f:
			f[x] += 1
		else:
			f[x] = 1
	a = []
	ind = []
	for i in f:
		a.append(f[i])
		ind.append(i)
	if n == 0:
		print('Draw')
	elif len(a) == 1:
		print(ind[0])
	elif a[0] == a[1]:
		print('Draw')
	elif a[0] > a[1]:
		print(ind[0])
	else:
		print(ind[1])


for _ in range(int(input())):
	n = int(input())
	(a, b) = ([], [])
	for i in range(n):
		s = input()
		if i == 0:
			a.append(s)
		elif s in a:
			a.append(s)
		else:
			b.append(s)
	l1 = len(a)
	l2 = len(b)
	if l1 > l2:
		print(a[0])
	elif l2 > l1:
		print(b[0])
	else:
		print('Draw')


for _ in range(int(input())):
	n = int(input())
	y1 = []
	y2 = []
	for i in range(n):
		inp = input()
		if i == 0:
			y1.append(inp)
		elif inp in y1:
			y1.append(inp)
		else:
			y2.append(inp)
	if len(y1) == len(y2):
		print('Draw')
	elif len(y1) > len(y2):
		print(y1[0])
	else:
		print(y2[0])


for _ in range(int(input())):
	n = int(input())
	l1 = []
	l2 = []
	for i in range(n):
		inp = input()
		if i == 0:
			l1.append(inp)
		elif inp in l1:
			l1.append(inp)
		else:
			l2.append(inp)
	if len(l1) == len(l2):
		print('Draw')
	elif len(l1) > len(l2):
		print(l1[0])
	else:
		print(l2[0])


for _ in range(int(input())):
	n = int(input())
	dt = {}
	l = []
	for _ in range(n):
		s = input()
		if s not in l:
			l.append(s)
		dt[s] = dt.get(s, 0) + 1
	if len(l) == 0:
		print('Draw')
	elif len(l) == 1:
		print(l[0])
	elif dt[l[0]] > dt[l[1]]:
		print(l[0])
	elif dt[l[0]] < dt[l[1]]:
		print(l[1])
	else:
		print('Draw')


def func(d):
	l = list(d.keys())
	if len(l) == 1 or d[l[0]] > d[l[1]]:
		return l[0]
	if d[l[0]] == d[l[1]]:
		return 'Draw'
	else:
		return l[1]
from sys import stdin, stdout
t = int(stdin.readline())
for j in range(t):
	n = int(stdin.readline())
	if n == 0:
		stdout.write('Draw\n')
		continue
	d = {}
	for i in range(n):
		f = stdin.readline().rstrip()
		try:
			d[f] += 1
		except KeyError:
			d[f] = 1
	stdout.write(f'{func(d)}\n')


for _ in range(int(input())):
	n = int(input())
	li = []
	fi = []
	se = []
	if n == 0:
		print('Draw')
		continue
	for _ in range(n):
		x = input()
		li.append(x)
	for i in range(n):
		if li[i] == li[0]:
			fi.append(li[i])
		else:
			se.append(li[i])
	if len(fi) > len(se):
		print(fi[0])
	elif len(fi) < len(se):
		print(se[0])
	else:
		print('Draw')


for x in range(int(input())):
	n = int(input())
	a = []
	b = []
	for i in range(n):
		data = input()
		if i == 0:
			a.append(data)
		elif data in a:
			a.append(data)
		else:
			b.append(data)
	val = len(a) - len(b)
	if val == 0:
		print('Draw')
	elif val > 0:
		print(a[0])
	else:
		print(b[0])


for _ in range(int(input())):
	n = int(input())
	t1 = []
	t2 = []
	for i in range(n):
		val = input()
		if i == 0:
			t1.append(val)
		elif val in t1:
			t1.append(val)
		else:
			t2.append(val)
	if len(t1) == len(t2):
		print('Draw')
	elif len(t1) > len(t2):
		print(t1[0])
	else:
		print(t2[0])


for c in range(int(input())):
	n = int(input())
	team1 = []
	team2 = []
	for i in range(n):
		team_name = input()
		if i == 0:
			team1.append(team_name)
		elif team_name in team1:
			team1.append(team_name)
		else:
			team2.append(team_name)
	if len(team1) - len(team2) > 0:
		print(team1[0])
	elif len(team1) - len(team2) == 0:
		print('Draw')
	else:
		print(team2[0])


for _ in range(int(input())):
	lst = []
	lst2 = []
	n = int(input())
	for i in range(n):
		team = input()
		if i == 0:
			lst.append(team)
		elif team in lst:
			lst.append(team)
		else:
			lst2.append(team)
	val = len(lst) - len(lst2)
	if val == 0:
		print('Draw')
	elif val > 0:
		print(lst[0])
	else:
		print(lst2[0])


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		l.append(input())
	maxi = 0
	dic = Counter(l)
	for (key, value) in dic.items():
		if value > maxi:
			maxi = value
			ans = key
	if len(list(dic.values())) == len(set(dic.values())) and n != 0:
		print(ans)
	else:
		print('Draw')


tests = int(input())
for i in range(tests):
	goals = int(input())
	if goals > 0:
		goals_dict = {}
		teams = []
		for j in range(goals):
			team = input()
			if team in goals_dict:
				goals_dict[team] += 1
			else:
				goals_dict[team] = 1
				teams.append(team)
		if len(teams) == 1 or goals_dict[teams[0]] > goals_dict[teams[1]]:
			print(teams[0])
		elif goals_dict[teams[0]] == goals_dict[teams[1]]:
			print('Draw')
		else:
			print(teams[1])
	else:
		print('Draw')


for _ in range(int(input())):
	n = int(input())
	d1 = {}
	for __ in range(n):
		s = input()
		if d1.get(s) is None:
			d1[s] = 1
		else:
			d1[s] += 1
	l1 = list(d1.keys())
	if len(l1) == 0:
		print('Draw')
	elif len(l1) == 1:
		print(l1[0])
	elif d1[l1[0]] > d1[l1[1]]:
		print(l1[0])
	elif d1[l1[0]] < d1[l1[1]]:
		print(l1[1])
	else:
		print('Draw')


for i in range(int(input())):
	n = int(input())
	if n == 0:
		print('Draw')
		continue
	lst = {}
	for i in range(n):
		t = input()
		if t in lst.keys():
			lst[t] += 1
		else:
			lst[t] = 1
	value = 0
	ans = ''
	for (i, j) in lst.items():
		if j > value:
			value = j
			ans = i
		elif j == value:
			ans = 'Draw'
	print(ans)


for _ in range(int(input())):
	n = int(input())
	if n == 0:
		print('Draw')
		continue
	d = [input()]
	c = ''
	for i in range(n - 1):
		a = input()
		if a != d[0]:
			c = a
		d.append(a)
	if d.count(d[0]) == n // 2 and n % 2 == 0:
		print('Draw')
	else:
		print(d[0] if d.count(d[0]) > n // 2 else c)


t = int(input())
for _ in range(t):
	n = int(input())
	p1 = p2 = 0
	arr = []
	if n > 0:
		arr.append(input())
		p1 = 1
		for _ in range(n - 1):
			i = input()
			if i not in arr:
				p2 += 1
				t = i
			else:
				p1 += 1
	if p1 > p2 or n == 1:
		print(arr[0])
	elif p2 > p1:
		print(t)
	else:
		print('Draw')