E. Logical Expression

Codeforces

IDCF913E

Time3000ms

Memory256MB

Difficulty—

bitmasksdpshortest paths

English · Original

Chinese · Translation

Formal · Original

You are given a boolean function of three variables which is defined by its truth table. You need to find an expression of minimum length that equals to this function. The expression may consist of: * Operation _AND_ ('_&_', ASCII code 38) * Operation _OR_ ('_|_', ASCII code 124) * Operation _NOT_ ('_!_', ASCII code 33) * Variables _x_, _y_ and _z_ (ASCII codes 120-122) * Parentheses ('_(_', ASCII code 40, and '_)_', ASCII code 41) If more than one expression of minimum length exists, you should find the lexicographically smallest one. Operations have standard priority. _NOT_ has the highest priority, then _AND_ goes, and _OR_ has the lowest priority. The expression should satisfy the following grammar: E ::= E '_|_' T | T T ::= T '_&_' F | F F ::= '_!_' F | '_(_' E '_)_' | '_x_' | '_y_' | '_z_' ## Input The first line contains one integer _n_ — the number of functions in the input (1 ≤ _n_ ≤ 10 000). The following _n_ lines contain descriptions of functions, the _i_\-th of them contains a string of length 8 that consists of digits _0_ and _1_ — the truth table of the _i_\-th function. The digit on position _j_ (0 ≤ _j_ < 8) equals to the value of the function in case of , and . ## Output You should output _n_ lines, the _i_\-th line should contain the expression of minimum length which equals to the _i_\-th function. If there is more than one such expression, output the lexicographically smallest of them. Expressions should satisfy the given grammar and shouldn't contain white spaces. [samples] ## Note The truth table for the second function: ![image](https://espresso.codeforces.com/77f8cbfcaf676f6885c34af765c173adb6d42278.png)

你被给定一个由真值表定义的三个变量的布尔函数。你需要找到一个长度最小的表达式，使其等于该函数。表达式可以包含：如果存在多个长度最小的表达式，你应该找到字典序最小的那个。运算符具有标准优先级：_NOT_ 优先级最高，其次是 _AND_，_OR_ 优先级最低。表达式应满足以下文法： E ::= E '_|_' T | T T ::= T '_&_' F | F F ::= '_!_' F | '_(_' E '_)_' | '_x_' | '_y_' | '_z_' 第一行包含一个整数 #cf_span[n] — 输入中函数的个数（#cf_span[1 ≤ n ≤ 10 000]）。接下来的 #cf_span[n] 行包含函数的描述，第 #cf_span[i] 行包含一个长度为 #cf_span[8] 的由数字 _0_ 和 _1_ 组成的字符串 —— 第 #cf_span[i] 个函数的真值表。位置 #cf_span[j]（#cf_span[0 ≤ j < 8]）上的数字等于当 , 和时该函数的取值。你应该输出 #cf_span[n] 行，第 #cf_span[i] 行应包含一个长度最小且等于第 #cf_span[i] 个函数的表达式。如果存在多个这样的表达式，输出其中字典序最小的那个。表达式必须满足给定文法，且不应包含任何空格。第二个函数的真值表： ## Input 第一行包含一个整数 #cf_span[n] — 输入中函数的个数（#cf_span[1 ≤ n ≤ 10 000]）。接下来的 #cf_span[n] 行包含函数的描述，第 #cf_span[i] 行包含一个长度为 #cf_span[8] 的由数字 _0_ 和 _1_ 组成的字符串 —— 第 #cf_span[i] 个函数的真值表。位置 #cf_span[j]（#cf_span[0 ≤ j < 8]）上的数字等于当 , 和时该函数的取值。 ## Output 你应该输出 #cf_span[n] 行，第 #cf_span[i] 行应包含一个长度最小且等于第 #cf_span[i] 个函数的表达式。如果存在多个这样的表达式，输出其中字典序最小的那个。表达式必须满足给定文法，且不应包含任何空格。 [samples] ## Note 第二个函数的真值表：

Definitions: - Let $ f: \{0,1\}^3 \to \{0,1\} $ be a Boolean function of three variables $ x, y, z $. - The truth table of $ f $ is given as a binary string $ s \in \{0,1\}^8 $, where $ s[j] = f(x,y,z) $ for $ j = 4a + 2b + c $, with $ a,b,c \in \{0,1\} $ corresponding to $ x,y,z $ respectively in lexicographic order: $$ (x,y,z) = (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) $$ Grammar: $$ \begin{align*} E &::= E \mid T \mid T \\ T &::= T \land F \mid F \\ F &::= \neg F \mid (E) \mid x \mid y \mid z \end{align*} $$ (Note: `_||_` → $ \mid $, `_&_` → $ \land $, `_!_` → $ \neg $, no whitespace.) Constraints: - Expression must be syntactically valid under the above grammar. - Operator precedence: $ \neg $ (highest), $ \land $, $ \mid $ (lowest). - Parentheses may be used only where necessary to override precedence. Objective: For each given truth table $ s $, find an expression $ \mathcal{E} $ such that: 1. $ \mathcal{E} $ computes $ f $ (i.e., matches truth table $ s $). 2. The length of $ \mathcal{E} $ (number of characters) is minimized. 3. Among all minimal-length expressions, choose the lexicographically smallest one under the ordering: $ \neg < ( < ) < x < y < z < \land < \mid $ (i.e., character order: `!` < `(` < `)` < `x` < `y` < `z` < `&` < `|`) Input: - Integer $ n $ ($ 1 \leq n \leq 10{,}000 $) - $ n $ binary strings of length 8, each representing a truth table. Output: - $ n $ lines, each containing the minimal-length, lexicographically smallest expression for the corresponding function.

Samples

Input #1

Output #1

y
(y|z)&x
!x
x|y&z

API Response (JSON)

{
  "problem": {
    "name": "E. Logical Expression",
    "description": {
      "content": "You are given a boolean function of three variables which is defined by its truth table. You need to find an expression of minimum length that equals to this function. The expression may consist of: ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF913E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a boolean function of three variables which is defined by its truth table. You need to find an expression of minimum length that equals to this function. The expression may consist of:\n\n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定一个由真值表定义的三个变量的布尔函数。你需要找到一个长度最小的表达式，使其等于该函数。表达式可以包含：\n\n如果存在多个长度最小的表达式，你应该找到字典序最小的那个。\n\n运算符具有标准优先级：_NOT_ 优先级最高，其次是 _AND_，_OR_ 优先级最低。表达式应满足以下文法：\n\nE ::= E '_|_' T | T\n\nT ::= T '_&_' F | F\n\nF ::= '_!_' F...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Definitions:\n- Let $ f: \\{0,1\\}^3 \\to \\{0,1\\} $ be a Boolean function of three variables $ x, y, z $.\n- The truth table of $ f $ is given as a binary string $ s \\in \\{0,1\\}^8 $, where $ s[j] = f(x,y,z...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments