ん〜フルで出てれば通せたんだけどな〜(吐血
確かに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]))