← 返回题目列表

AtCoder · utpc2011_9

I. 位运算

中文机器翻译题面 查看原题
我们收到报告称此问题评分不正确。

G○○gle Code Jam 世界锦标赛终于要开始了。 前面包括P○tr、t○mek、SnapDrag○n、 G○○gle最强的程序员们正在注视着我们。 如果它表现出奇怪的动作,它很可能就会死掉。 闭上眼睛,耐心等待比赛开始。

...奇怪,比赛无法开始。 当我睁开眼睛时……天啊。房间里的人全部崩溃了。 不,不是一切。除了一个人,渡。

瓦塔
“我们终于可以谈谈了。已经有一段时间了,(毛利人)。”
(毛利部落)
“……你是谁?我认识的wata应该是我儿时的朋友,一个美丽的女孩……”
瓦塔
“你还被这样的妄想所附身吗!!记住!!接受吧!!他已经不在这个世界上了!!”

哈...!!我记住了一切。 我是世界上第一个在编程竞赛中杀人的人。 而我杀死的人正是我最亲密的朋友之一,kita_masa。

kita_masa 自称为位运算大师。 他是一个有点不寻常的人,他说所有函数都可以使用按位运算来编写。 现在我想了一下,我有一个想要使用按位运算创建的函数。 你不能要求 kita_masa 这样做。 因此,我决定创建一个程序来替换 kita_masa。

問題

N 整数集 给出了 (xi, yi) 。 对于所有对 yi = f(xi) 功能 考虑在约束下创建 f 。

関数 f 可以表示为C语言源代码如下:

uint32_t f(uint32_t x) {
  return 式;
}

这里,uint32_t 表示 32 位无符号整数。 另外,假设该表达式可以使用以下 BNF 来表达:

<expr> ::= "x"
         | <num>
         | "(~" <expr> ")"
         | "(" <expr> <op2> <expr> ")"
<op2> ::= "&" | "|" | "^" | "+" | "-" | "*"

<num> 是一个非负整数,可以表示为 32 位无符号整数。 假设它自然地表示为十进制数(没有前导零等)。

创建一个输出此类函数公式的程序。

入力

第一行输入是单个整数 包含 N 。

继续 来自行 N 线 i 行是两个整数 xi, yi 。

出力

输出满足条件的表达式。

制約

  • 1 ≤ N ≤ 8
  • 0 ≤ xi, yi < 256
  • 请务必以遵循上述 BNF 的格式输出表达式。即使它作为 C 语言中的表达式有效,也不要插入空格、换行符或删除括号。
  • 输出不得超过 100000 个字符。
  • 满足条件的函数 给出的输入使得 f 始终存在。

部分点

针对该问题的判断设置了一组20分的测试用例。 该组中包含的测试用例的输入满足以下条件。

  • 有一个不使用“+”、“-”或“*”的正确输出

入出力例

入力例1:

8
1 1
2 2
3 3
4 0
5 1
6 2
7 3
8 0

输入示例 1 的输出示例:

(x&3)

入力例2:

8
1 0
2 0
3 2
4 0
5 4
6 4
7 6
8 0

输入示例 2 的输出示例:

(x&(x-1))

这是一个众所周知的操作,它会关闭最右边的位。