Problem:


Problem D: 無矛盾な単位系

京、垓、{禾予}、穣、溝、澗、正、載、極、恒河沙、阿僧祇、那由他、不可思議、無量大数
分、厘、毛、糸、忽、微、繊、沙、塵、埃、渺、漠、模糊、逡巡、須臾、瞬息、弾指、刹那、六徳、虚空、清浄、阿頼耶、阿摩羅、涅槃寂静

これらが何か分かるだろうか。これらは全て10の累乗につけられた数詞である。

京 = 1016, 垓 = 1020, {禾予} = 1024, 穣 = 1028, 溝 = 1032, ...
分 = 10-1、厘 = 10-2、毛 = 10-3、糸 = 10-4、忽 = 10-5, ...

ではこれらが実用的に使われているのを見たことはあるだろうか？無いのではなかろうか？ 過去の先人達が熟考の末にこれらの命名を行ったにもかかわらず、これらの数詞が日の目を見られないとはなんと勿体無いことだろう。

この問題は、コンテスト参加者の皆様にこれらの数詞を知ってもらうために作られたものである。以下に問題の概要を示す。

1 km = 103 m

上記のような単位間の関係が入力として与えられる。この問題では、左辺における単位が右辺における単位の10の累乗倍となっているような単位間の関係だけが与えられる。
単位間の関係が矛盾しているとは、与えられた関係から以下の関係が同時に成り立つことをいう。

1 A = 10x B
1 A = 10y B

ただし、 x&ne;yであり、 AとBは任意の単位。

入力として与えられた単位間の関係が矛盾しているかどうか判定せよ。 なお、入力は簡易のため指数表記で与えられる。 

Input

入力の一行目に、単位間の関係の個数を示す整数 N (1≤ N ≤ 100) が与えられる。

続くN行に、単位間の関係が含まれる。
単位間の関係は以下のフォーマットで与えられる。

"1 A = 10^x B"

A, B は単位を示す。AとBは相異なっており、それぞれ空白を含まないアルファベット小文字1〜16文字からなる。x は -100から100までの整数である。
"1 A = 10^x B" が定義されたとき、 "1 B = 10^-x A" も暗黙のうちに定義されているものとする。

任意の単位系のペアが2回以上定義されることはない。
すなわち、"1 kilobyte = 10^3 byte", "1 kilobyte = 10^1 byte" のような関係が、同時に入力に含まれることはない。
同様に、"1 kilobyte = 10^3 byte", "1 byte = 10^-3 kilobyte" のような関係が、同時に入力に含まれることはない。 

Output

与えられた単位系が矛盾していなければ Yes を、 矛盾していれば No を出力せよ。 

Notes on Test Cases

上記入力形式で複数のデータセットが与えられます。各データセットに対して上記出力形式で出力を行うプログラムを作成して下さい。

N が 0 のとき入力の終わりを示します。

Sample Input

3
1 km = 10^3 m
1 m = 10^2 cm
1 km = 10^5 cm
7
1 kilometre = 10^3 metre
1 megametre = 10^3 kilometre
1 metre = 10^-6 megametre
1 terametre = 10^3 gigametre
1 petametre = 10^3 terametre
1 gigametre = 10^-6 petametre
1 metre = 10^-15 petametre
4
1 a = 10^2 b
1 a = 10^3 c
1 b = 10^2 c
1 c = 10^1 d
4
1 acm = 10^2 icpc
1 icpc = 10^3 utpc
1 utpc = 10^4 topcoder
1 topcoder = 10^-1 acm
0

Output for Sample Input

Yes
Yes
No
No



Sample input:
3
1 km = 10^3 m
1 m = 10^2 cm
1 km = 10^5 cm
7
1 kilometre = 10^3 metre
1 megametre = 10^3 kilometre
1 metre = 10^-6 megametre
1 terametre = 10^3 gigametre
1 petametre = 10^3 terametre
1 gigametre = 10^-6 petametre
1 metre = 10^-15 petametre
4
1 a = 10^2 b
1 a = 10^3 c
1 b = 10^2 c
1 c = 10^1 d
4
1 acm = 10^2 icpc
1 icpc = 10^3 utpc
1 utpc = 10^4 topcoder
1 topcoder = 10^-1 acm
0


Sample output:
Yes
Yes
No
No

Submission status: Wrong Answer

Solution code:
defnum=999999999

def parse_input(line):
    [one, lname, eq, scale, rname] = line.split()
    exp=int( scale.split("^")[-1] )
    return lname, exp, rname

while(1):
    N=int(raw_input())
    if N==0: break
    L=[]
    names=[]
    for i in range(N):
        [lname, exp, rname]=parse_input(raw_input())
        names += [lname, rname]
        L.append([lname, rname, exp])
    names=sorted(set(names))
    m=len(names)
    A=[[defnum if i!=j else 0 for i in range(m)] for j in range(m)]
    ans="Yes"
    for l in L:
        li,ri = [names.index(name) for name in l[:2]]
        exp=l[2]
        #add
        if A[li][ri] == defnum:
            A[li][ri] = exp
            A[ri][li] = -exp
            for ab in[ [li,ri], [ri,li] ]:
                a,b=ab
                for x in range(m):
                    if A[b][x]!=defnum:
                        A[a][x] = A[a][b]+A[b][x]
                        A[x][a] = -A[a][x]
        else:
            if A[li][ri]!=exp:
                ans="No"
                break
    print ans

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    m = []
    f = 1
    for _ in range(n):
        _, a, _, v, b = input().split()
        v = int(v[3:])
        x, y = -1, -1
        for i in range(len(m)):
            if a in m[i]:x = i
            if b in m[i]:y = i
        if x >= 0:
            if y >= 0:
                if x == y:
                    if m[x][a] - v != m[x][b]:f = 0
                else:
                    for i in m[y]:
                        m[x][i] = m[y][i] + m[x][a] - m[y][b] - v
                    m.pop(y)
            else:
                m[x][b] = m[x][a] - v
        elif y >= 0:
            m[y][a] = m[y][b] + v
        else:
            m.append({a:v, b:0})
    print("yes" if f else "no")

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:break
  dic = {}
  for _ in range(n):
    _, name1, _, val, name2 = input().split()
    val = int(val.split("^")[1])
    if name1 not in dic:
      dic[name1] = {}
    if name2 not in dic:
      dic[name2] = {}
    dic[name1][name2] = val
    dic[name2][name1] = -val
  
  keys = list(dic.keys())
  score = {key:None for key in keys}
  
  def search(key):
    now = score[key]
    for to in dic[key]:
      if score[to] == None:
        score[to] = now + dic[key][to]
        if not search(to):return False
      if score[to] != now + dic[key][to]:return False
    return True
  
  for key in keys:
    if score[key] != None:continue
    score[key] = 0
    if not search(key):
      print("No")
      break
  else:
    print("Yes")

Submission status: Accepted

Solution code:
defnum=999999999

def parse_input(line):
    [one, lname, eq, scale, rname] = line.split()
    exp=int( scale.split("^")[-1] )
    return lname, exp, rname

while(1):
    N=int(raw_input())
    if N==0: break
    L=[]
    names=[]
    for i in range(N):
        [lname, exp, rname]=parse_input(raw_input())
        names += [lname, rname]
        L.append([lname, rname, exp])
    names=sorted(set(names))
    m=len(names)
    A=[[defnum if i!=j else 0 for i in range(m)] for j in range(m)]
    ans="Yes"
    for l in L:
        li,ri = [names.index(name) for name in l[:2]]
        exp=l[2]
        #add
        if A[li][ri] == defnum:
            A[li][ri] = exp
            A[ri][li] = -exp
            for ab in[ [li,ri], [ri,li] ]:
                a,b=ab
                for y in range(m):
                    for x in range(m):
                        if A[y][a]!= defnum and A[b][x]!=defnum:
                            A[y][x] = A[y][a]+A[a][b]+A[b][x]
                            A[x][y] = -A[y][x]
        else:
            if A[li][ri]!=exp:
                ans="No"
                break
#    print names
#    for al in A:
#        print al
    print ans

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n == 0:break
    m = []
    f = 1
    for _ in range(n):
        _, a, _, v, b = input().split()
        v = int(v[3:])
        x, y = -1, -1
        for i in range(len(m)):
            if a in m[i]:x = i
            if b in m[i]:y = i
        if x >= 0:
            if y >= 0:
                if x == y:
                    if m[x][a] - v != m[x][b]:f = 0
                else:
                    for i in m[y]:
                        m[x][i] = m[y][i] + m[x][a] - m[y][b] - v
                    m.pop(y)
            else:
                m[x][b] = m[x][a] - v
        elif y >= 0:
            m[y][a] = m[y][b] + v
        else:
            m.append({a:v, b:0})
    print("Yes" if f else "No")

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
class WeightedUnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            px = self.find(self.parents[x])
            self.weight[x] += self.weight[self.parents[x]]
            self.parents[x] = px
            return px

    def union(self, x, y, w):
        w += self.weight[x] - self.weight[y]
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y, w = y, x, -w
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        self.weight[y] = w
        return

    def weig(self, x):
        self.find(x)
        return self.weight[x]

    def diff(self, x, y):
        return self.weig(y) - self.weig(x)
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

while 1:
    n = int(input())
    if n == 0:
        exit()
    Q, d = [], set()
    while n:
        _, a, _, p, b = input().split()
        Q += (a, b, int(p[3:])),
        d |= {a, b}
        n -= 1
    D = {c : e for e, c in enumerate(d)}
    UF = WeightedUnionFind(len(d))
    for a, b, p in Q:
        a, b = D[a], D[b]
        if UF.same(a, b):
            if p != UF.diff(a, b):
                print("No"); break
        else:
            UF.union(a, b, p)
    else:
        print("Yes")

Submission status: Accepted

Solution code:
class WeightedUnionFind(object):
    __slots__ = ["nodes", "weight"]

    def __init__(self, n: int) -> None:
        self.nodes = [-1]*n
        self.weight = [0]*n

    def get_root(self, x: int) -> int:
        if x < 0:
            raise ValueError("Negative Index")

        if self.nodes[x] < 0:
            return x
        else:
            root = self.get_root(self.nodes[x])
            self.weight[x] += self.weight[self.nodes[x]]
            self.nodes[x] = root
            return root

    def relate(self, smaller: int, bigger: int, diff_weight: int) -> None:
        if smaller < 0 or bigger < 0:
            raise ValueError("Negative Index")

        root_a, root_b = self.get_root(smaller), self.get_root(bigger)
        new_weight = diff_weight + self.weight[smaller] - self.weight[bigger]

        if root_a == root_b:
            # 問題によっては必要かも（情報に矛盾があるなら-1を出力など）
            if self.weight[smaller] + diff_weight == self.weight[bigger]:
                return
            raise ValueError("relateに矛盾あり")

        if self.nodes[root_a] > self.nodes[root_b]:
            root_a, root_b, new_weight = root_b, root_a, -new_weight

        self.nodes[root_a] += self.nodes[root_b]
        self.nodes[root_b] = root_a
        self.weight[root_b] = new_weight

    def diff(self, x: int, y: int) -> int:
        root_x, root_y = self.get_root(x), self.get_root(y)
        if root_x != root_y:
            return None
        return self.weight[y] - self.weight[x]


while True:
    N = int(input())
    if not N:
        break
    uf, d = WeightedUnionFind(N*2), dict()
    queries = [input().split() for _ in [0]*N]
    try:
        for _, a, _, n, b in queries:
            n = int(n[3:])
            d[a] = d[a] if a in d else len(d)
            d[b] = d[b] if b in d else len(d)
            uf.relate(d[a], d[b], n)
        print("Yes")
    except ValueError as e:
        print("No")