P9927 [NFLSPC #6] Altar of Truth

It was getting late, and the crowd of onlookers had mostly dispersed. People probably did not notice that there was still a thin figure running toward the Altar of Truth. “Which field are you a scientist in? Why are you alone?” The risk remover tilted his head and asked little Y in front of him. “I’m not a scientist. I’m just a high school student.” “A student?” The risk remover was confused. “Then what do you want to ask?” “I want to know the ultimate law of the universe.” “Since you’re just a student, how do you think I should help you understand the laws of the universe?” “Huh?” Little Y seemed surprised. After a moment, a bit of disappointment appeared on his face. “Shouldn’t the truth of the universe be so simple that everyone can understand it... Shouldn’t it?” “Truth is not that simple. Leaving the universe aside, I’ll casually give you some ‘principles’ here. Can you describe them in concise language?” Little Y raised his head, looked at the dense strings of zeros and ones displayed in the sky by holographic projection, and fell into deep thought.

There are $n$ **propositional variables**, denoted as $P_0, P_1, \cdots, P_{n - 1}$. Their **truth values** are Boolean values: either $0$ or $1$. We call a **principle** a function that takes $n$ Boolean values as input and outputs one Boolean value, i.e., a mapping $\{0, 1\}^n \to \{0, 1\}$. Strings that satisfy certain conditions are called **Well-Formed Formulas** (WFF). Each WFF corresponds to exactly one principle, called the formula’s **truth table**. Specifically: - A propositional variable $P_i$ is a WFF. Its truth table always outputs the $i$-th input value it receives (the indices of the $n$ input values are $0, 1, \cdots, n - 1$). - If $k$ strings $A_1, A_2, \cdots, A_k$ ($k \geq 1$) are all WFFs, then $(A_1 \land A_2 \land \cdots \land A_k)$ is also a WFF. When its truth table receives an input $I$, its output is the minimum of the outputs of the truth tables of $A_1, A_2, \cdots, A_k$ on input $I$. - If $k$ strings $A_1, A_2, \cdots, A_k$ ($k \geq 1$) are all WFFs, then $(A_1 \lor A_2 \lor \cdots \lor A_k)$ is also a WFF. When its truth table receives an input $I$, its output is the maximum of the outputs of the truth tables of $A_1, A_2, \cdots, A_k$ on input $I$. - If $A$ is a WFF, then $\lnot A$ is also a WFF. Suppose the truth table of $A$ outputs $x$ on input $I$, then the truth table of $\lnot A$ outputs $1 - x$ on input $I$. Define the **size** of a WFF as the number of $\land$ and $\lor$ it contains. Now, given a principle, find a WFF whose truth table equals that principle, and under this condition make the formula’s size as small as possible.

**This is an output-only problem.** All testdata `formula1.in` to `formula10.in` are provided in the attached files. The first line of the input contains an integer $n$. The second line contains a string $a_{0 \sim 2^n - 1}$ of length $2^n$, describing the given principle: if for any $0 \leq i < n$, the $i$-th input value is $\left\lfloor\frac{x}{2^i}\right\rfloor \bmod 2$, then the output of the principle is $a_x$. The third line contains $10$ scoring parameters; their specific use is described in “Hint”.

For the given $10$ input files, you need to submit your output files `formula1.out` to `formula10.out` respectively. Each output file contains one line, representing the WFF you provide. Parentheses are written as `()`. Propositional variable $P_i$ is written as the digit `i` (since $n \leq 10$, this is guaranteed to be a single character). $\land$ is written as `&`, $\lor$ is written as `|`, and $\lnot$ is written as `!`. **Do not omit parentheses on your own.**

For all testdata, $1 \leq n \leq 10$. For each test case, we score as follows: - If your output length is greater than $10^5$, you get $0$ points. - If your output is not a WFF, you get $0$ points. - If the truth table of your WFF is different from the input principle, you get $0$ points. - If none of the above happens, let $s_{1 \sim 10}$ be the scoring parameters, and let $S$ be the size of your formula. Your score is $\sum_{i = 1}^{10}[S \leq s_i]$. Each test case has a full score of $10$ points. There are $10$ test cases, so the total is $100$ points (before multiplying by the score coefficient). **It is guaranteed that a full-score solution exists.** --- We provide a tool to test your output. Download the attached file `checker.cpp` and compile it to get an executable `checker.exe` (Windows) or `checker` (Linux). Its usage is as follows: - Enter `checker.exe X` (Windows) or `./checker X` (Linux) in the terminal, or run it directly and then input `X` followed by a newline, to test the $X$-th test case `formulaX.in/out`. - Enter `checker.exe A B` (Windows) or `./checker A B` (Linux) in the terminal, or run it directly and then input `A B` followed by a newline, to test with input filename $A$ and output filename $B$. - If the input is invalid or the output has errors, there will be corresponding messages. - If there are no errors, it will output the size of your WFF. - The input file may match the input format description exactly, or omit the line of scoring parameters. If the checker detects that the line of scoring parameters exists, it will also output your score. Source: NFLSPC #6 C by chenxia25. Translated by ChatGPT 5