Bit Operation

Time Limit : 1 sec, Memory Limit : 262144 KB

問題 I : ビット演算

いよいよ G○○gle Code Jam の世界大会が始まろうとしている. 前では P○tr, t○mek, SnapDrag○n をはじめとする, G○○gle の誇る最強のコーダー達が睨みを利かせている. 妙な動きを見せれば,命はないだろう. 目をつむり,コンテスト開始をじっと待つ.

…妙だ,コンテストが始まらない. 目を開けてみると…なんということだ.部屋の全ての人間が,倒れている. いや違う,全てではない.一人の男,wata を除いてだ.

wata
「やっと話せるぞ. 久しぶりだな,(iwi)」
(iwi)
「…お前は何者だ? 俺の知る wata は幼なじみ系美少女のはずが…」
wata
「まだそんな妄想に取り憑かれているのか!! 思い出せ!! 受け止めろ!! 彼はもうこの世界には居ないんだ!!」

はっ…!! 僕は全てを思い出していた. 僕は世界で最初にプログラミングコンテストで人を殺めたのだ. そして,僕が殺したのは他でもなく,最も仲の良かった友人の一人,kita_masa であった.

kita_masa は自らをビット演算の達人と言い, あらゆる関数はビット演算で記述できると言う,少し変わった奴だった. そういえば今,ビット演算を用いて作成したい関数があるが, kita_masa にそれをお願いすることはできない. そこで,kita_masa の代わりになるプログラムを作成することにした.

問題

N 個の整数の組 (xiyi) が与えられる. 全ての組に対して 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 ビット符号無し整数で表現できる非負の整数を 10 進数で自然に (leading-zero 等を持たず) 表現したものとする.

このような関数の式を出力するプログラムを作成せよ.

入力

入力の最初の行は 1 つの整数 N を含む.

続く N 行の i 行目は 2 つの整数 xiyi を含む.

出力

条件を満たす式を出力せよ.

制約

  • 1 ≤ N ≤ 8
  • 0 ≤ xiyi < 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))

良く知られる最右の 1 ビットをオフにする操作である.


Source: University of Tokyo Programming Contest 2011 , Tokyo, Japan, 2011-05-14
Problem Setter:  Takuya Akiba
http://www.utpc.jp/2011/