読者です 読者をやめる 読者になる 読者になる

AtCoder ARC#15 C

ん〜フルで出てれば通せたんだけどな〜(吐血
確かにdoubleで精度足りる感は有ったけどN=200だし多倍長分数
python強い(小並感
基本的には適当な一つを1として幅優先探索でその他を決めて、最大/最小
多倍長分数だから精度とかは全部大丈夫

# -*- coding: utf-8 -*-

from collections import deque

N = int(input())
t = [input().split() for i in range(N)]

s = set()
for d in t:
	s.add(d[0])
	s.add(d[2])
l = list(s)

h = [[] for i in range(len(l))]
for i in range(N):
	t[i][0] = l.index(t[i][0])
	t[i][1] = int(t[i][1])
	t[i][2] = l.index(t[i][2])
	h[t[i][0]].append(i)
	h[t[i][2]].append(i)

p = [[-1, 1] for i in range(len(l))]
used = [False for i in range(N)]
p[0][0] = 1
q = deque(h[0])
while len(q):
	u = q.pop()
	if used[u]:
		continue
	used[u] = True
	nt = t[u]
	q.extend(h[nt[0]])
	q.extend(h[nt[2]])
	if p[nt[0]][0] == -1:
		p[nt[0]][0] = p[nt[2]][0] * nt[1]
		p[nt[0]][1] = p[nt[2]][1]
	else:
		p[nt[2]][0] = p[nt[0]][0]
		p[nt[2]][1] = p[nt[0]][1] * nt[1]
b = 1
for d in p:
	b *= d[1]
res = []
for i in range(len(l)):
	res.append(p[i][0] * b // p[i][1])
ma = res.index(max(res))
mi = res.index(min(res))
print('1{0}={1}{2}'.format(l[ma], res[ma]//res[mi], l[mi]))