A. Short Program

Codeforces

IDCF878A

Time2000ms

Memory256MB

Difficulty—

bitmasksconstructive algorithms

English · Original

Chinese · Translation

Formal · Original

Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well. In the language, there are only three commands: apply a bitwise operation AND, OR or XOR with a given constant to the current integer. A program can contain an arbitrary sequence of these operations with arbitrary constants from 0 to 1023. When the program is run, all operations are applied (in the given order) to the argument and in the end the result integer is returned. Petya wrote a program in this language, but it turned out to be too long. Write a program in CALPAS that does the same thing as the Petya's program, and consists of no more than 5 lines. Your program should return the same integer as Petya's program for all arguments from 0 to 1023. ## Input The first line contains an integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of lines. Next _n_ lines contain commands. A command consists of a character that represents the operation ("_&_", "_|_" or "_^_" for AND, OR or XOR respectively), and the constant _x__i_ 0 ≤ _x__i_ ≤ 1023. ## Output Output an integer _k_ (0 ≤ _k_ ≤ 5) — the length of your program. Next _k_ lines must contain commands in the same format as in the input. [samples] ## Note You can read about bitwise operations in [https://en.wikipedia.org/wiki/Bitwise_operation](https://en.wikipedia.org/wiki/Bitwise_operation). Second sample: Let _x_ be an input of the Petya's program. It's output is ((_x_&1)&3)&5 = _x_&(1&3&5) = _x_&1. So these two programs always give the same outputs.

Petya 学习了一种新的编程语言 CALPAS。这种语言的程序总是接受一个非负整数，并返回一个非负整数。该语言中只有三种指令：将给定的常数与当前整数进行按位与（AND）、或（OR）或异或（XOR）操作。程序可以包含任意数量的这些操作，常数范围为 #cf_span[0] 到 #cf_span[1023]。当程序运行时，所有操作按给定顺序依次应用于输入整数，最终返回结果整数。 Petya 编写了一个该语言的程序，但程序过长。请编写一个 CALPAS 程序，其功能与 Petya 的程序完全相同，且指令行数不超过 #cf_span[5] 行。你的程序对所有从 #cf_span[0] 到 #cf_span[1023] 的输入，必须返回与 Petya 程序相同的整数。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 表示指令行数。接下来 #cf_span[n] 行为指令。每条指令由一个表示操作的字符（"_&_"、"_|_" 或 "_^_" 分别代表 AND、OR 或 XOR）和一个常数 #cf_span[xi] (#cf_span[0 ≤ xi ≤ 1023]) 组成。请输出一个整数 #cf_span[k] (#cf_span[0 ≤ k ≤ 5]) —— 你的程序的长度。接下来 #cf_span[k] 行必须以与输入相同的格式输出指令。你可以阅读关于按位操作的更多信息：https://en.wikipedia.org/wiki/Bitwise_operation。第二个样例：设 #cf_span[x] 为 Petya 程序的输入，其输出为 #cf_span[((x&1)&3)&5 = x&(1&3&5) = x&1]。因此这两个程序对所有输入均产生相同结果。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 表示指令行数。接下来 #cf_span[n] 行为指令。每条指令由一个表示操作的字符（"_&_"、"_|_" 或 "_^_" 分别代表 AND、OR 或 XOR）和一个常数 #cf_span[xi] (#cf_span[0 ≤ xi ≤ 1023]) 组成。 ## Output 请输出一个整数 #cf_span[k] (#cf_span[0 ≤ k ≤ 5]) —— 你的程序的长度。接下来 #cf_span[k] 行必须以与输入相同的格式输出指令。 [samples] ## Note 你可以阅读关于按位操作的更多信息：https://en.wikipedia.org/wiki/Bitwise_operation。第二个样例：设 #cf_span[x] 为 Petya 程序的输入，其输出为 #cf_span[((x&1)&3)&5 = x&(1&3&5) = x&1]。因此这两个程序对所有输入均产生相同结果。

**Definitions** Let $\mathcal{D} = \{ z \in \mathbb{Z} \mid 0 \le z \le 1023 \}$ be the domain of 10-bit non-negative integers. Let $\Omega = \{ \&, |, \oplus \}$ be the set of bitwise operations (AND, OR, XOR). A command is a tuple $(\diamond, c)$ where $\diamond \in \Omega$ and $c \in \mathcal{D}$. **Given** 1. An integer $n$ where $1 \le n \le 5 \cdot 10^5$. 2. A sequence of commands $S = \langle (\diamond_1, c_1), (\diamond_2, c_2), \dots, (\diamond_n, c_n) \rangle$. **Function Definition** Let $f_S: \mathcal{D} \to \mathcal{D}$ be the function defined by the sequential application of $S$ on an input $x \in \mathcal{D}$. Let $y_0 = x$. For $i = 1, \dots, n$, let $y_i = y_{i-1} \diamond_i c_i$. Then $f_S(x) = y_n$. **Objective** Find a sequence of commands $S' = \langle (\diamond'_1, c'_1), \dots, (\diamond'_k, c'_k) \rangle$ satisfying the following conditions: 1. $0 \le k \le 5$. 2. $\forall x \in \mathcal{D}, f_{S'}(x) = f_S(x)$. **Output** 1. The integer $k$. 2. The sequence $S'$ formatted as $k$ lines, each containing the character representation of $\diamond'_j$ and the integer $c'_j$.

Samples

Input #1

3
| 3
^ 2
| 1

Output #1

2
| 3
^ 2

Input #2

3
& 1
& 3
& 5

Output #2

1
& 1

Input #3

3
^ 1
^ 2
^ 3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Short Program",
    "description": {
      "content": "Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well. In the language, there are only three c",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF878A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya learned a new programming language CALPAS. A program in this language always takes one non-negative integer and returns one non-negative integer as well.\n\nIn the language, there are only three c...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 学习了一种新的编程语言 CALPAS。这种语言的程序总是接受一个非负整数，并返回一个非负整数。\n\n该语言中只有三种指令：将给定的常数与当前整数进行按位与（AND）、或（OR）或异或（XOR）操作。程序可以包含任意数量的这些操作，常数范围为 #cf_span[0] 到 #cf_span[1023]。当程序运行时，所有操作按给定顺序依次应用于输入整数，最终返回结果整数。\n\nPetya 编写...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**\nLet $\\mathcal{D} = \\{ z \\in \\mathbb{Z} \\mid 0 \\le z \\le 1023 \\}$ be the domain of 10-bit non-negative integers.\nLet $\\Omega = \\{ \\&, |, \\oplus \\}$ be the set of bitwise operations (AND...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments