[autumn_fest_07]Bit Map

ID: 2896

传统题

2000ms

64MiB

尝试: 0

已通过: 0

难度:

上传者:

admin

配点

満点

110

部分点

問題文

1変数関数が与えられる。与えられた関数を等価な50文字以下の表現で書きなおせ。

ただしこの問題で関数 $f$ と $g$ が等価であるとは、任意の $x \\in \\{0,1,..,2147483647(=2^{31}-1)\\}$ に対して $f(x) = g(x)$ が成り立つことをいう。

入力形式

入力は以下の形式で与えられる。

$N$ definition1 definition2 ... definition $N$

$N$ は定義する関数の個数である。

definition $i$ は全て以下のBNFに従う。


<definition> ::= <function-name> + "(x)=" + <expr>
<expr> ::= "x" | <number> | <function> + "(" + <expr> + ")"
                  | "(" + <expr> + "|" + <expr> + ")"
                  | "(" + <expr> + "^" + <expr> + ")"
                  | "(" + <expr> + "&" + <expr> + ")"
<function> ::= <function-name> | <function-name> + "^" + <number>
<function-name> ::= "a" | "b" | ... | "j"
<number> ::= "0" | "1" | ... | "2147483647"

で使われる"&"、"|"、"^"はそれぞれビット演算のand、or、xorを表す。

で使われる"^"は関数の合成 $f^n(x)$ を表す。

非負整数 $n$ に対して $f^n(x)$ は次のように定義される。

$f^0(x) = x$ $f^{n+1}(x) = f(f^n(x))$

関数の定義は上から行われる。定義式の右辺にその時点で未定義な他の関数や、定義しているその関数自身が現れることはない。また、既に定義された関数を新たに定義しなおすこともない。

定義される全ての関数は50文字以下の等価な表現を持つことが保証されている。

出力形式

関数を与えられた順に等価な表現で1行ごとに出力せよ。

各行毎に出力される文字列は50文字を越えてはならない。

出力は以下のBNFにしたがう必要がある。


<output> ::= <function-name> + "(x)=" + <expr>
<expr> ::= "x" | <number>
                  | "(" + <expr> + "|" + <expr> + ")"
                  | "(" + <expr> + "^" + <expr> + ")"
                  | "(" + <expr> + "&" + <expr> + ")"
<function-name> ::= "a" | "b" | ... | "j"
<number> ::= "0" | "1" | ... | "2147483647"

入力が従うBNFと異なり、ある関数の表現に他の関数を用いてはならないことに注意せよ。

制約

$1 ≤ N ≤ 10$
|definitioni| $≤ 1000$

この問題の判定には、 $30$ 点分のテストケースのグループが設定されている。このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

$N = 1$

入力例 1


4
f(x)=(x^1)
g(x)=(f(x)&7)
h(x)=f(g^3((2147483647^x)))
c(x)=(3|10)

出力例 1


f(x)=(x^1)
g(x)=((x^1)&7)
h(x)=((x&7)^7)
c(x)=11

もちろんこれ以外にも様々な表現がある。例えば


f(x)=((x^3)^2)  c(x)=(((x^x)|1)^10)
```などと表現しても構わない。一方、```plain

f(x)=x^1  c(x)=(1|2|8)  c(x)=(11)
```などと表現するのは指定されたBNFに従わないのでWrong Answerとなる。

* * *

### 入力例 2

```plain

5
a(x)=(x^1)
b(x)=a^1000000000(x)
c(x)=a^1000000001(x)
d(x)=a^0((x|2))
e(x)=a^1((x|2))

出力例 2


a(x)=(x^1)
b(x)=x
c(x)=(x^1)
d(x)=(x|2)
e(x)=((x|2)^1)

Writer: komiya

Source Name

Autumn Fest

#autumnfest07. [autumn_fest_07]Bit Map

配点

問題文