← 返回题目列表

AtCoder · autumn_fest_07

G. 位图

中文机器翻译题面 查看原题

配点

満点
110
部分点
30

問題文

给定一个一变量函数。将给定函数重写为等价的50字符以下的表示。

但是本题中函数 f 和 g 等价是指,对任意x \in \{0,1,..,2147483647(=2^{31}-1)\} 反对 f(x) = g(x)都成立。


入力形式

输入以以下格式给出。

N
definition1
definition2
...
definitionN

N 是定义的函数数量。

定义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"

在 <expr> 中使用的 "&"、"|"、"^" 分别表示位运算的与、或、异或。

在 <function> 中使用的 "^" 是函数的组合 f^n(x) 。

非負整数 n 反对 f^n(x) 的定义如下。

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

函数的定义按照顺序进行。定义式右边不会出现此时未定义的其他函数或函数本身。并且,已经定义的函数也不会被重新定义。

所有规定的函数保证有不超过50个字符的等价表示。

出力形式

请按给定顺序逐行输出函数的等价表示。

每行输出的字符串不得超过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
  • |定义i| ≤ 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,因此是错误答案。


入力例 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)

作者:小宫