Sistemes d'equacions simbòliques P92039


Statement
 

pdf   zip

thehtml

Un sistema d’equacions simbòliques és un conjunt d’equacions x = f(y1, …, yk), on x, y1, …, yk són variables i f és un símbol que representa a una funció arbitrària de k arguments (direm que faritat k). Una solució d’un sistema amb n variables x1, …, xn és qualsevol assignació α d’expressions a variables de manera que per tota equació x = f(y1, …, yk), es compleix α(x) = f(α(y1), …, α(yk)).

Feu un programa que, donat un sistema d’equacions simbòliques, en calculi la solució més general, o digui si no en té.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n, seguida de les n variables en ordre lexicogràfic, seguides del nombre d’equacions m, seguida de m equacions en el format dels exemples. Les variables i les funcions són paraules amb lletres minúscules, totes diferents. Cada variable apareix com a molt un cop a la banda esquerra d’una equació. Cada funció pot aparèixer diversos cops, però sempre amb la mateixa aritat, entre 1 i n. Tots els arguments de la mateixa funció són variables diferents. Podeu suposar 1 ≤ n ≤ 40.

Sortida

Escriviu, en ordre lexicogràfic de les variables, la solució més general del sistema, seguint el format dels exemples. Escriviu una línia buida al final de cada cas.

Pista

Inspireu-vos en l’ordenació topològica.

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
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++