P17020 [ROI 2026 Day1] Brackets and Trees [Judging Not Configured Yet]

This is a communication problem.

This problem discusses **rooted trees with unordered children**. A rooted tree with unordered children consists of a root and zero or more children, and each child is itself a rooted tree with unordered children. Also, as the name suggests, the order of listing the children does not matter. That is, the two trees shown in the figure below are considered the same rooted tree with unordered children. In what follows, we will abbreviate rooted trees with unordered children as **trees**. :::align{center}  ::: Any tree can be encoded into a **correct bracket sequence** (hereinafter referred to as a bracket sequence) in the following way: - A tree consisting of only one vertex is encoded as `()`. - Suppose after removing the root, the tree splits into subtrees $t_1, t_2, \ldots, t_k$, where $k$ is the number of children of the original root. Let $s_1, \ldots, s_k$ be the strings encoding $t_1, \ldots, t_k$, respectively. Then for any permutation $a = [a_1, a_2, \ldots, a_k]$ of $1$ to $k$, the original tree can be encoded as the bracket sequence `(` $s_{a_1} s_{a_2} \ldots s_{a_k}$ `)`. Note that the same tree may be encoded by different bracket sequences. For example, the tree shown below can be encoded as `(()(()))` or as `((())())`. :::align{center}  ::: You need to learn how to encode an arbitrary tree sequence $u_1, \ldots, u_n$ into a rooted tree $w$. To check whether your encoding method is correct, your program will be run twice. **First run** In the first run, the program will receive $n$ correct bracket sequences, where each sequence is an encoding $s_i$ of some rooted tree. As a response, you need to output one correct bracket sequence representing some rooted tree $w$. Different subtasks impose different limits on the number of vertices of the tree $w$ (depending on the total number of vertices of the original trees). **Second run** In the second run, the program will receive a single correct bracket sequence that encodes the tree $w$ you output in the first run. Note that the input may be any valid encoding of the tree $w$, not necessarily the exact sequence your program output in the first run. As a response, you need to output several correct bracket sequences. They should correspond one-to-one to the trees given in the first run, and in the same order. For each tree, you may output any of its valid bracket-sequence encodings, but the order within the whole list must be consistent with the order of the input in the first run. ### Interaction Protocol At the beginning of each run, your program should read an integer $t$ ($t = 1$ or $2$), indicating which run it is. **First run** You need to handle multiple groups of input. Each group is provided via interaction through standard input. That is, before reading the next group, you must output the answer for the current group and flush the standard output buffer. The first line of each group contains an integer $n$, the number of trees to be encoded. If $n = 0$, it means all data has been processed and your program should terminate. Otherwise, the next $n$ lines each contain a string $s_i$ consisting of `(` and `)`, which is the correct bracket sequence encoding of the $i$-th tree as described above. It is guaranteed that $s_i$ describes a valid tree. For this group, your program should output a correct bracket sequence encoding some tree $w$. After outputting, print a newline and flush the output buffer. In the first run, the judge is **adaptive**. This means that when generating subsequent data groups for the current test point, the judge may make use of the tree $w$ you output in previous groups. **Second run** You need to handle multiple groups of input. Each group contains a string $s$. If $s$ is `0`, it means all data has been processed and your program should terminate. Otherwise, $s$ is a correct bracket sequence encoding some tree $w$ that you generated in the first run. For each group, you need to output two lines. The first line contains an integer $n$, the number of decoded trees. The second line consists of $n$ correct bracket sequences, which encode (in the corresponding order) the trees that were given in the first run, with sequences separated by `+`. For example, if you need to output `(())` and `(()())` in order, you should output: ``` 2 (())+(()()) ``` After each output, you must print a newline and flush the output buffer. Note that after each output, do not forget to print a newline and flush the output stream correctly. Please refer to the contestant instructions to learn how to flush the output stream in interactive problems. ## Constraints The total length of all bracket sequences in a single input group is denoted by $s$, and the length of the sequence you output for that group in the first run is denoted by $m$. Each subtask defines a function $f(x)$. If for every group we have $m \le f(s)$ and all trees are recovered correctly, then the subtask is considered passed. Let the number of vertices of the $i$-th tree be $t_i$. Then the length of the string $s_i$ is $2 t_i$. Let $S$ be the sum of $s$ over all data groups in the same test point. It is guaranteed that for each test point, $S \le 10^6$, and the number of data groups does not exceed $100$. | Subtask | Score | $f(x)$ | $S$ | Additional constraints | Depends on | |:---:|:---:|:---:|:---:|:---|:---:| | 1 | 13 | $f(x) = x + 2000$ | $S \le 200\,000$ | In the second run, the bracket sequence given is **exactly the same** as the sequence your program output in the first run. | | | 2 | 7 | $f(x) = x + 2000$ | $S \le 200\,000$ | $t_1 < t_2 < \ldots < t_n$ | | | 3 | 6 | $f(x) = x + 2000$ | $S \le 200\,000$ | $n = 2$ | | | 4 | Up to 34 | $f(x) = 4x + 2000$ | $S \le 200\,000$ | | | | 5 | Up to 11 | $f(x) = x + 2000$ | | $t_1 = t_2 = \ldots = t_n > 1$ | | | 6 | Up to 9 | $f(x) = x + 2000$ | | $t_i > 1$ | 5 | | 7 | Up to 20 | $f(x) = x + 2000$ | | | 1 – 6 | The scoring method for subtask 4 is as follows. For each data group, define $k = \max\left(0, \dfrac{m - 2000}{s}\right)$. The function $\operatorname{score}(k)$ is given by the table below: | $k$ | $\operatorname{score}(k)$ | |:---:|:---:| | $\le 1.5$ | $34$ | | $2$ | $20$ | | $3$ | $10$ | | $4$ | $5$ | | $> 4$ | $0$ | For intermediate values of $k$, the function value is obtained by linear interpolation between adjacent rows of the table and rounded to the nearest integer. The score of a test point is the minimum $\operatorname{score}(k)$ over all data groups in that test point, and the score of a subtask is the minimum score over its test points. Subtasks 5, 6, and 7 are scored in the same way as follows. For each data group, define $c = \max(0, m - s)$. The function $\operatorname{score}(c)$ is given by the table below: | $c$ | $\operatorname{score}(c)$, Subtask 5 | $\operatorname{score}(c)$, Subtask 6 | $\operatorname{score}(c)$, Subtask 7 | |:---:|:---:|:---:|:---:| | $\le 30$ | $11$ | $9$ | $20$ | | $100$ | $7$ | $7$ | $14$ | | $200$ | $4$ | $4$ | $8$ | | $2000$ | $2$ | $2$ | $4$ | | $> 2000$ | $0$ | $0$ | $0$ | For intermediate values of $c$, the function value is also obtained by linear interpolation between adjacent rows and rounded to the nearest integer. The score of a test point is the minimum $\operatorname{score}(c)$ over all data groups in that test point, and the score of a subtask is the minimum score over its test points. Translated by DeepSeek V4 Pro.

N/A

N/A

### Subtasks See the Constraints section. Translated by ChatGPT 5