D. Draw Brackets!

Codeforces

IDCF770D

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

A sequence of square brackets is regular if by inserting symbols "_+_" and "_1_" into it, you can get a regular mathematical expression from it. For example, sequences "_\[\[\]\]\[\]_", "_\[\]_" and "_\[\[\]\[\[\]\]\]_" — are regular, at the same time "_\]\[_", "_\[\[\]_" and "_\[\[\]\]\]\[_" — are irregular. Draw the given sequence using a minimalistic pseudographics in the strip of the lowest possible height — use symbols '_+_', '_\-_' and '_|_'. For example, the sequence "_\[\[\]\[\]\]\[\]_" should be represented as: +- -++- -+ |+- -++- -+|| | || || ||| | |+- -++- -+|| | +- -++- -+ Each bracket should be represented with the hepl of one or more symbols '_|_' (the vertical part) and symbols '_+_' and '_\-_' as on the example which is given above. Brackets should be drawn without spaces one by one, only dividing pairs of consecutive pairwise brackets with a single-space bar (so that the two brackets do not visually merge into one symbol). The image should have the minimum possible height. The enclosed bracket is always smaller than the surrounding bracket, but each bracket separately strives to maximize the height of the image. So the pair of final brackets in the example above occupies the entire height of the image. Study carefully the examples below, they adequately explain the condition of the problem. Pay attention that in this problem the answer (the image) is unique. ## Input The first line contains an even integer _n_ (2 ≤ _n_ ≤ 100) — the length of the sequence of brackets. The second line contains the sequence of brackets — these are _n_ symbols "_\[_" and "_\]_". It is guaranteed that the given sequence of brackets is regular. ## Output Print the drawn bracket sequence in the format which is given in the condition. Don't print extra (unnecessary) spaces. [samples]

[{"iden":"statement","content":"一个方括号序列是合法的，如果通过在其间插入符号 \"_+_\" 和 \"_1_\"，可以得到一个合法的数学表达式。例如，序列 \"_[[]][]_\"、\"_[]_\" 和 \"_[[][[]]]_\" 是合法的，而 \"_][_\"、\"_[[]_\" 和 \"_[[]]][_\" 是不合法的。\n\n请使用最简化的伪图形，在尽可能低的高度的条带上绘制给定的序列——使用符号 '_+_'、'_-_' 和 '_|_'。例如，序列 \"_[[][]][]_\" 应表示为：\n\n每个括号应通过一个或多个符号 '_|_'（垂直部分）以及符号 '_+_' 和 '_-_' 来表示，如上例所示。\n\n括号应逐个绘制，无空格，仅在连续的成对括号之间用单个空格分隔（以避免两个括号在视觉上合并为一个符号）。图像应具有尽可能小的高度。\n\n嵌套的括号总是比外层括号小，但每个括号单独力求最大化图像的高度。因此，上例中最后一对括号占据了图像的整个高度。\n\n请仔细研究下面的例子，它们充分解释了题意。请注意，本题的答案（图像）是唯一的。\n\n第一行包含一个偶数整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100]）——括号序列的长度。\n\n第二行包含括号序列——这些是 #cf_span[n] 个符号 \"_[_\" 和 \"_]_\"。保证给定的括号序列是合法的。\n\n请按题面中给出的格式打印绘制出的括号序列。不要打印额外（不必要的）空格。"},{"iden":"input","content":"第一行包含一个偶数整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 100]）——括号序列的长度。第二行包含括号序列——这些是 #cf_span[n] 个符号 \"_[_\" 和 \"_]_\"。保证给定的括号序列是合法的。 "},{"iden":"output","content":"请按题面中给出的格式打印绘制出的括号序列。不要打印额外（不必要的）空格。 "},{"iden":"examples","content":"输入8[[][]][]输出+- -++- -+|+- -++- -+|| ||| || ||| ||+- -++- -+|| |+- -++- -+输入6[[[]]]输出+- -+|+- -+|||+- -+||||| |||||+- -+|||+- -+|+- -+输入6[[][]]输出+- -+|+- -++- -+||| || |||+- -++- -+|+- -+输入2[]输出+- -+| |+- -+输入4[][]输出+- -++- -+| || |+- -++- -+"}]}

**Definitions** Let $ S $ be a regular bracket sequence of length $ n $, where $ n $ is even and $ n \in [2, 100] $. Let $ S = s_1 s_2 \dots s_n $, where each $ s_i \in \{ \texttt{[}, \texttt{]} \} $. **Constraints** 1. $ S $ is a well-formed (regular) bracket sequence. 2. Each opening bracket $ \texttt{[} $ has a unique matching closing bracket $ \texttt{]} $. 3. Nested brackets are properly enclosed: if $ s_i = \texttt{[} $ and $ s_j = \texttt{]} $ form a pair, then any bracket between them is contained within this pair. **Objective** Render $ S $ as a 2D pseudographic diagram using only characters `|`, `+`, `-`, and single spaces ` ` between adjacent top-level bracket pairs, such that: - Each bracket pair is drawn as a rectangle defined by: - Top and bottom edges: `+` at ends, `-` in between. - Vertical sides: `|`. - Nested brackets are drawn inside the parent bracket’s rectangle, centered vertically and horizontally. - The height of the entire drawing is minimized. - Each bracket pair maximizes its own height within its containing pair. - Adjacent top-level bracket pairs are separated by exactly one space; no other spaces are allowed. - The diagram must be uniquely determined by the structure of $ S $. **Output** The minimal-height pseudographic representation of $ S $.

Samples

Input #1

8
\[\[\]\[\]\]\[\]

Output #1

+-        -++- -+
|+- -++- -+||   |
||   ||   |||   |
|+- -++- -+||   |
+-        -++- -+

Input #2

6
\[\[\[\]\]\]

Output #2

+-     -+
|+-   -+|
||+- -+||
|||   |||
||+- -+||
|+-   -+|
+-     -+

Input #3

6
\[\[\]\[\]\]

Output #3

+-        -+
|+- -++- -+|
||   ||   ||
|+- -++- -+|
+-        -+

Input #4

2
\[\]

Output #4

+- -+
|   |
+- -+

Input #5

4
\[\]\[\]

Output #5

+- -++- -+
|   ||   |
+- -++- -+

API Response (JSON)

{
  "problem": {
    "name": "D. Draw Brackets!",
    "description": {
      "content": "A sequence of square brackets is regular if by inserting symbols \"_+_\" and \"_1_\" into it, you can get a regular mathematical expression from it. For example, sequences \"_\\[\\[\\]\\]\\[\\]_\", \"_\\[\\]_\" and \"",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF770D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A sequence of square brackets is regular if by inserting symbols \"_+_\" and \"_1_\" into it, you can get a regular mathematical expression from it. For example, sequences \"_\\[\\[\\]\\]\\[\\]_\", \"_\\[\\]_\" and \"...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"一个方括号序列是合法的，如果通过在其间插入符号 \\\"_+_\\\" 和 \\\"_1_\\\"，可以得到一个合法的数学表达式。例如，序列 \\\"_[[]][]_\\\"、\\\"_[]_\\\" 和 \\\"_[[][[]]]_\\\" 是合法的，而 \\\"_][_\\\"、\\\"_[[]_\\\" 和 \\\"_[[]]][_\\\" 是不合法的。\\n\\n请使用最简化的伪图形，在尽可能...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ S $ be a regular bracket sequence of length $ n $, where $ n $ is even and $ n \\in [2, 100] $.  \nLet $ S = s_1 s_2 \\dots s_n $, where each $ s_i \\in \\{ \\texttt{[}, \\texttt{]} \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments