Symbolic systems of equations P92039


Statement
 

pdf   zip

thehtml

A symbolic system of equations is a set of equations x = f(y1, …, yk), where x, y1, …, yk are variables and f is a symbol representing an arbitrary function with k arguments (we say that f has arity k). A solution of a system with n variables x1, …, xn is any assignment α of expressions to variables in such a way that for every equation x = f(y1, …, yk) it holds that α(x) = f(α(y1), …, α(yk)).

Write a program that, given a system of symbolic equations, computes its most general solution, or tells that it does not exist.

Input

Input consists of several cases, each with n, followed by n variables in lexicographical order, followed by the number of equations m, followed by m equations in the exact format of the examples. Variables and functions are words made up of lowercase letters, all different. Every variable appears at most once in the left side of an equation. Every function can occur several times, but always with the same arity, between 1 and n. All arguments of the same function are different variables. You can assume 1 ≤ n ≤ 40.

Output

Print, in lexicographical order of the variables, the most general solution of the system, following the format of the examples. Print an empty line at the end of each case.

Hint

Take inspiration from a topological sort.

Public test cases
  • Input

    3
    x y z
    2
    z = f ( x y )
    y = h ( x )
    
    1
    x
    1
    x = f ( x )
    
    2
    xx yy
    2
    xx = ff ( yy )
    yy = ff ( xx )
    
    2
    abc z
    0
    
    6
    uu uv w x y z
    4
    x = f ( uv )
    y = gg ( x z )
    w = gg ( uv y )
    uu = gh ( uv )
    

    Output

    x -> x
    y -> h ( x )
    z -> f ( x h ( x ) )
    
    No solution!
    
    No solution!
    
    abc -> abc
    z -> z
    
    uu -> gh ( uv )
    uv -> uv
    w -> gg ( uv gg ( f ( uv ) z ) )
    x -> f ( uv )
    y -> gg ( f ( uv ) z )
    z -> z
    
    
  • Information
    Author
    Enric Rodríguez
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++