{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n\t\t\t\n\t\t\t\u003cfont color\u003d\"FF0000\"\u003eこの問題は正しく採点されていないという報告を受けています。\u003c/font\u003e\r\n\u003cp\u003eいよいよ G○○gle Code Jam の世界大会が始まろうとしている.\r\n前では P○tr, t○mek, SnapDrag○n をはじめとする,\r\nG○○gle の誇る最強のコーダー達が睨みを利かせている.\r\n妙な動きを見せれば,命はないだろう.\r\n目をつむり,コンテスト開始をじっと待つ.\u003c/p\u003e\r\n\u003cp\u003e…妙だ,コンテストが始まらない.\r\n目を開けてみると…なんということだ.部屋の全ての人間が,倒れている.\r\nいや違う,全てではない.一人の男,wata を除いてだ.\u003c/p\u003e\r\n\u003cdl class\u003d\"docutils\"\u003e\r\n\u003cdt\u003ewata\u003c/dt\u003e\r\n\u003cdd\u003e「やっと話せるぞ. 久しぶりだな,(iwi)」\u003c/dd\u003e\r\n\u003cdt\u003e(iwi)\u003c/dt\u003e\r\n\u003cdd\u003e「…お前は何者だ? 俺の知る wata は幼なじみ系美少女のはずが…」\u003c/dd\u003e\r\n\u003cdt\u003ewata\u003c/dt\u003e\r\n\u003cdd\u003e「まだそんな妄想に取り憑かれているのか!! 思い出せ!! 受け止めろ!! 彼はもうこの世界には居ないんだ!!」\u003c/dd\u003e\r\n\u003c/dl\u003e\r\n\u003cp\u003eはっ…!! 僕は全てを思い出していた.\r\n僕は世界で最初にプログラミングコンテストで人を殺めたのだ.\r\nそして,僕が殺したのは他でもなく,最も仲の良かった友人の一人,kita_masa であった.\u003c/p\u003e\r\n\u003cp\u003ekita_masa は自らをビット演算の達人と言い,\r\nあらゆる関数はビット演算で記述できると言う,少し変わった奴だった.\r\nそういえば今,ビット演算を用いて作成したい関数があるが,\r\nkita_masa にそれをお願いすることはできない.\r\nそこで,kita_masa の代わりになるプログラムを作成することにした.\u003c/p\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id1\"\u003e\r\n\u003ch2\u003e問題\u003c/h2\u003e\r\n\u003cp\u003e\u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e 個の整数の組 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e,\u0026nbsp;\u003ci\u003ey\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e が与えられる.\r\n全ての組に対して \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ey\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026nbsp;\u003d\u0026nbsp;\u003ci\u003ef\u003c/i\u003e(\u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e)\u003c/span\u003e なる関数 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e を制約の下で作ることを考える.\u003c/p\u003e\r\n\u003cp\u003e関数 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e は,C 言語のソースコードとして以下のように表現できるものとする:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\nuint32_t f(uint32_t x) {\r\n return 式;\r\n}\r\n\u003c/pre\u003e\r\n\u003cp\u003eここで,uint32_t は 32 ビット符号無し整数を表す.\r\nまた,式は以下の BNF で表現できるものとする:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n\u0026lt;expr\u0026gt; ::\u003d \"x\"\r\n | \u0026lt;num\u0026gt;\r\n | \"(~\" \u0026lt;expr\u0026gt; \")\"\r\n | \"(\" \u0026lt;expr\u0026gt; \u0026lt;op2\u0026gt; \u0026lt;expr\u0026gt; \")\"\r\n\u0026lt;op2\u0026gt; ::\u003d \"\u0026amp;\" | \"|\" | \"^\" | \"+\" | \"-\" | \"*\"\r\n\u003c/pre\u003e\r\n\u003cp\u003e\u0026lt;num\u0026gt; は 32 ビット符号無し整数で表現できる非負の整数を\r\n10 進数で自然に (leading-zero 等を持たず) 表現したものとする.\u003c/p\u003e\r\n\u003cp\u003eこのような関数の式を出力するプログラムを作成せよ.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id2\"\u003e\r\n\u003ch2\u003e入力\u003c/h2\u003e\r\n\u003cp\u003e入力の最初の行は 1 つの整数 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e を含む.\u003c/p\u003e\r\n\u003cp\u003e続く \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003eN\u003c/i\u003e\u003c/span\u003e 行の \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e 行目は 2 つの整数 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e,\u0026nbsp;\u003ci\u003ey\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e を含む.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id3\"\u003e\r\n\u003ch2\u003e出力\u003c/h2\u003e\r\n\u003cp\u003e条件を満たす式を出力せよ.\u003c/p\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id4\"\u003e\r\n\u003ch2\u003e制約\u003c/h2\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e\u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e1\u0026nbsp;≤\u0026nbsp;\u003ci\u003eN\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;8\u003c/span\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e0\u0026nbsp;≤\u0026nbsp;\u003ci\u003ex\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e,\u0026nbsp;\u003ci\u003ey\u003c/i\u003e\u003csub\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u0026nbsp;\u0026lt;\u0026nbsp;256\u003c/span\u003e\u003c/li\u003e\r\n\u003cli\u003e式は必ず,上記の BNF に従う書式で出力せよ.例え C 言語の表現として妥当であったとしても,空白や改行の挿入や括弧の削除などはしてはならない.\u003c/li\u003e\r\n\u003cli\u003e出力は 100000 文字を越えてはならない.\u003c/li\u003e\r\n\u003cli\u003e条件を満たす関数 \u003cspan style\u003d\"font-size:110%;font-family:times new roman;\"\u003e\u003ci\u003ef\u003c/i\u003e\u003c/span\u003e が常に存在するような入力が与えられる.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id5\"\u003e\r\n\u003ch2\u003e部分点\u003c/h2\u003e\r\n\u003cp\u003eこの問題の判定には,20 点分のテストケースのグループが設定されている.\r\nこのグループに含まれるテストケースの入力は以下を満たす.\u003c/p\u003e\r\n\u003cul class\u003d\"simple\"\u003e\r\n\u003cli\u003e\u0027+\u0027, \u0027-\u0027, \u0027*\u0027 を用いないような正しい出力が存在する\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/div\u003e\r\n\u003cdiv class\u003d\"section\" id\u003d\"id6\"\u003e\r\n\u003ch2\u003e入出力例\u003c/h2\u003e\r\n\u003cp\u003e入力例1:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n8\r\n1 1\r\n2 2\r\n3 3\r\n4 0\r\n5 1\r\n6 2\r\n7 3\r\n8 0\r\n\u003c/pre\u003e\r\n\u003cp\u003e入力例 1 に対する出力の例:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n(x\u0026amp;3)\r\n\u003c/pre\u003e\r\n\u003cp\u003e入力例2:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n8\r\n1 0\r\n2 0\r\n3 2\r\n4 0\r\n5 4\r\n6 4\r\n7 6\r\n8 0\r\n\u003c/pre\u003e\r\n\u003cp\u003e入力例 2 に対する出力の例:\u003c/p\u003e\r\n\u003cpre class\u003d\"literal-block\"\u003e\r\n(x\u0026amp;(x-1))\r\n\u003c/pre\u003e\r\n\u003cp\u003e良く知られる最右の 1 ビットをオフにする操作である.\u003c/p\u003e\r\n\u003c/div\u003e\r\n"}}]}