Time Limit: 2 sec / Memory Limit: 64 MB
配点
- 満点
- 110
- 部分点
- 30
問題文
1変数関数が与えられる。与えられた関数を等価な50文字以下の表現で書きなおせ。
ただしこの問題で関数 f と g が等価であるとは、任意のx \in \{0,1,..,2147483647(=2^{31}-1)\} に対して f(x) = g(x)が成り立つことをいう。
入力形式
入力は以下の形式で与えられる。
N definition1 definition2 ... definitionN
N は定義する関数の個数である。
definitioniは全て以下の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"
<expr>で使われる"&"、"|"、"^"はそれぞれビット演算のand、or、xorを表す。
<function>で使われる"^"は関数の合成 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)などと表現しても構わない。一方、
f(x)=x^1 c(x)=(1|2|8) c(x)=(11)などと表現するのは指定されたBNFに従わないのでWrong Answerとなる。
入力例 2
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