D. Widget Library

[{"iden":"statement","content":"Vasya 开发了一个用于构建图形用户界面的库。他将这个库命名为 _VTK_（_VasyaToolKit_）。该库的一个有趣特点是小部件可以相互嵌套。\n\n小部件是图形界面的某个元素。每个小部件都有宽度和高度，并占据屏幕上的一个矩形区域。在 Vasya 的库中，所有小部件都是 _Widget_ 类型。为简化起见，我们将小部件与其类型等同看待。\n\n类型 _HBox_ 和 _VBox_ 是 _Widget_ 类型的派生类，因此它们也是 _Widget_ 类型。_HBox_ 和 _VBox_ 是特殊的，它们可以存储其他小部件。这两种小部件都可以使用 _pack()_ 方法直接将其他小部件打包到自身中。_HBox_ 和 _VBox_ 类型的小部件可以存储多个其他小部件，甚至可以存储多个相同的部件——它们会简单地重复出现。使用 _pack()_ 方法时，仅保存被打包小部件的引用，也就是说，当被打包的小部件发生变化时，它在被嵌套的小部件中的显示也会随之改变。\n\n我们假设小部件 #cf_span[a] 被嵌套在小部件 #cf_span[b] 中，当且仅当存在一个由小部件构成的链 #cf_span[a = c1, c2, ..., ck = b]（#cf_span[k ≥ 2]），使得对任意 #cf_span[1 ≤ i < k]，#cf_span[ci] 都直接被打包到 #cf_span[ci + 1] 中。在 Vasya 的库中，不允许小部件 #cf_span[a] 被嵌套在自身 #cf_span[a] 中（即自身嵌套）。如果尝试以这种方式相互嵌套，会立即导致错误。\n\n此外，_HBox_ 和 _VBox_ 小部件具有参数 _border_ 和 _spacing_，分别由方法 _set_border()_ 和 _set_spacing()_ 设置。默认情况下，这两个参数均为 #cf_span[0]。\n\n上图展示了小部件如何被打包进 _HBox_ 和 _VBox_ 中。_HBox_ 和 _VBox_ 会根据所打包小部件的尺寸自动调整自身大小。_HBox_ 和 _VBox_ 的唯一区别在于：_HBox_ 中的小部件水平排列，_VBox_ 中的小部件垂直排列。参数 _spacing_ 设置相邻小部件之间的距离，_border_ 设置围绕所有打包小部件的边框宽度。小部件按调用 _pack()_ 方法的顺序精确排列。如果 _HBox_ 或 _VBox_ 中没有打包任何小部件，则其尺寸为 #cf_span[0 × 0]，无论 _border_ 和 _spacing_ 参数如何设置。",},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] —— 指令的数量（#cf_span[1 ≤ n ≤ 100]）。接下来的 #cf_span[n] 行包含 _VasyaScript_ 语言的指令，每行一条。以下是可能的指令列表：\n\n\"_Widget [name]([x],[y])_\" —— 创建一个类型为 _Widget_ 的新小部件 [name]，其宽度为 [x] 单位，高度为 [y] 单位。\n\n\"_HBox [name]_\" —— 创建一个类型为 _HBox_ 的新小部件 [name]。\n\n\"_VBox [name]_\" —— 创建一个类型为 _VBox_ 的新小部件 [name]。\n\n\"_[name1].pack([name2])_\" —— 将小部件 [name2] 打包进小部件 [name1] 中。此时，小部件 [name1] 必须是 _HBox_ 或 _VBox_ 类型。\n\n\"_[name].set_border([x])_\" —— 将小部件 [name] 的 _border_ 参数设置为 [x] 单位。小部件 [name] 必须是 _HBox_ 或 _VBox_ 类型。\n\n\"_[name].set_spacing([x])_\" —— 将小部件 [name] 的 _spacing_ 参数设置为 [x] 单位。小部件 [name] 必须是 _HBox_ 或 _VBox_ 类型。\n\n所有指令在字符串开头和结尾均无空格。指令内部的单词之间恰好用一个空格分隔。数字前后均无空格。\n\n大小写敏感，例如 \"_wiDget x_\" 不是合法指令。输入数据中的字母大小写均正确。\n\n所有小部件名称均由小写拉丁字母组成，长度为 #cf_span[1] 到 #cf_span[10] 个字符（含）。所有小部件名称互不相同。脚本中的所有数字均为 #cf_span[0] 到 #cf_span[100]（含）之间的整数。\n\n保证上述脚本正确，即所有对小部件的操作均发生在小部件创建之后，且没有任何小部件被嵌套在自身中。保证脚本至少创建了一个小部件。",},{"iden":"output","content":"对每个小部件，输出一行，包含其名称、宽度和高度，以空格分隔。行必须按小部件名称的字典序排列。请勿在 C++ 中使用 _%lld_ 格式说明符读取或写入 64 位整数。推荐使用 _cout_ 流（也可使用 _%I64d_ 格式说明符）",},{"iden":"examples","content":"输入12Widget me(50,40)VBox grandpaHBox fathergrandpa.pack(father)father.pack(me)grandpa.set_border(10)grandpa.set_spacing(20)Widget brother(30,60)father.pack(brother)Widget friend(20,60)Widget uncle(100,20)grandpa.pack(uncle)输出brother 30 60father 80 60friend 20 60grandpa 120 120me 50 40uncle 100 20输入15Widget pack(10,10)HBox dummyHBox xVBox yy.pack(dummy)y.set_border(5)y.set_spacing(55)dummy.set_border(10)dummy.set_spacing(20)x.set_border(10)x.set_spacing(10)x.pack(pack)x.pack(dummy)x.pack(pack)x.set_border(0)输出dummy 0 0pack 10 10x 40 10y 10 10",},{"iden":"note","content":"在第一个样例中，小部件的布局如下： "}] [{"iden":"statement","content":"Vasya 开发了一个用于构建图形用户界面的库。他将这个库命名为 _VTK_（_VasyaToolKit_）。该库的一个有趣特点是小部件可以相互嵌套。\n\n小部件是图形界面的某个元素。每个小部件都有宽度和高度，并占据屏幕上的一个矩形区域。在 Vasya 的库中，所有小部件都是 _Widget_ 类型。为简化起见，我们将小部件与其类型等同看待。\n\n类型 _HBox_ 和 _VBox_ 是 _Widget_ 类型的派生类，因此它们也是 _Widget_ 类型。_HBox_ 和 _VBox_ 是特殊的，它们可以存储其他小部件。这两种小部件都可以使用 _pack()_ 方法直接将其他小部件打包到自身中。_HBox_ 和 _VBox_ 类型的小部件可以存储多个其他小部件，甚至可以存储多个相同的部件——它们会简单地重复出现。使用 _pack()_ 方法时，仅保存被打包小部件的引用，也就是说，当被打包的小部件发生变化时，它在被嵌套的小部件中的显示也会随之改变。\n\n我们假设小部件 #cf_span[a] 被嵌套在小部件 #cf_span[b] 中，当且仅当存在一个由小部件构成的链 #cf_span[a = c1, c2, ..., ck = b]（#cf_span[k ≥ 2]），使得对任意 #cf_span[1 ≤ i < k]，#cf_span[ci] 都直接被打包到 #cf_span[ci + 1] 中。在 Vasya 的库中，不允许小部件 #cf_span[a] 被嵌套在自身 #cf_span[a] 中（即自身嵌套）。如果尝试以这种方式相互嵌套，会立即导致错误。\n\n此外，_HBox_ 和 _VBox_ 小部件具有参数 _border_ 和 _spacing_，分别由方法 _set_border()_ 和 _set_spacing()_ 设置。默认情况下，这两个参数均为 #cf_span[0]。\n\n上图展示了小部件如何被打包进 _HBox_ 和 _VBox_ 中。_HBox_ 和 _VBox_ 会根据所打包小部件的尺寸自动调整自身大小。_HBox_ 和 _VBox_ 的唯一区别在于：_HBox_ 中的小部件水平排列，_VBox_ 中的小部件垂直排列。参数 _spacing_ 设置相邻小部件之间的距离，_border_ 设置围绕所有打包小部件的边框宽度。小部件按调用 _pack()_ 方法的顺序精确排列。如果 _HBox_ 或 _VBox_ 中没有打包任何小部件，则其尺寸为 #cf_span[0 × 0]，无论 _border_ 和 _spacing_ 参数如何设置。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] —— 指令的数量（#cf_span[1 ≤ n ≤ 100]）。接下来的 #cf_span[n] 行包含 _VasyaScript_ 语言的指令，每行一条。以下是可能的指令列表：\n\n\"_Widget [name]([x],[y])_\" —— 创建一个类型为 _Widget_ 的新小部件 [name]，其宽度为 [x] 单位，高度为 [y] 单位。\n\n\"_HBox [name]_\" —— 创建一个类型为 _HBox_ 的新小部件 [name]。\n\n\"_VBox [name]_\" —— 创建一个类型为 _VBox_ 的新小部件 [name]。\n\n\"_[name1].pack([name2])_\" —— 将小部件 [name2] 打包进小部件 [name1] 中。此时，小部件 [name1] 必须是 _HBox_ 或 _VBox_ 类型。\n\n\"_[name].set_border([x])_\" —— 将小部件 [name] 的 _border_ 参数设置为 [x] 单位。小部件 [name] 必须是 _HBox_ 或 _VBox_ 类型。\n\n\"_[name].set_spacing([x])_\" —— 将小部件 [name] 的 _spacing_ 参数设置为 [x] 单位。小部件 [name] 必须是 _HBox_ 或 _VBox_ 类型。\n\n所有指令在字符串开头和结尾均无空格。指令内部的单词之间恰好用一个空格分隔。数字前后均无空格。\n\n大小写敏感，例如 \"_wiDget x_\" 不是合法指令。输入数据中的字母大小写均正确。\n\n所有小部件名称均由小写拉丁字母组成，长度为 #cf_span[1] 到 #cf_span[10] 个字符（含）。所有小部件名称互不相同。脚本中的所有数字均为 #cf_span[0] 到 #cf_span[100]（含）之间的整数。\n\n保证上述脚本正确，即所有对小部件的操作均发生在小部件创建之后，且没有任何小部件被嵌套在自身中。保证脚本至少创建了一个小部件。"},{"iden":"output","content":"对每个小部件，输出一行，包含其名称、宽度和高度，以空格分隔。行必须按小部件名称的字典序排列。请勿在 C++ 中使用 _%lld_ 格式说明符读取或写入 64 位整数。推荐使用 _cout_ 流（也可使用 _%I64d_ 格式说明符）"},{"iden":"examples","content":"输入12Widget me(50,40)VBox grandpaHBox fathergrandpa.pack(father)father.pack(me)grandpa.set_border(10)grandpa.set_spacing(20)Widget brother(30,60)father.pack(brother)Widget friend(20,60)Widget uncle(100,20)grandpa.pack(uncle)输出brother 30 60father 80 60friend 20 60grandpa 120 120me 50 40uncle 100 20输入15Widget pack(10,10)HBox dummyHBox xVBox yy.pack(dummy)y.set_border(5)y.set_spacing(55)dummy.set_border(10)dummy.set_spacing(20)x.set_border(10)x.set_spacing(10)x.pack(pack)x.pack(dummy)x.pack(pack)x.set_border(0)输出dummy 0 0pack 10 10x 40 10y 10 10"},{"iden":"note","content":"在第一个样例中，小部件的布局如下： "}]

**Definitions:** - Let $ W $ be the set of all widgets. - Each widget $ w \in W $ has a type: $ \text{type}(w) \in \{ \text{Widget}, \text{HBox}, \text{VBox} \} $. - For $ w \in \{ \text{HBox}, \text{VBox} \} $, let: - $ \text{children}(w) $ be the ordered list of widgets packed directly into $ w $, - $ \text{border}(w) \in \mathbb{Z}_{\geq 0} $ be the border width, - $ \text{spacing}(w) \in \mathbb{Z}_{\geq 0} $ be the spacing between adjacent children. **Constraints:** - For any widget $ w $, if $ \text{type}(w) \neq \text{HBox} $ and $ \text{type}(w) \neq \text{VBox} $, then $ \text{children}(w) = \emptyset $. - For $ w \in \{ \text{HBox}, \text{VBox} \} $, the packing relation forms a directed acyclic graph (DAG): no widget is packed (directly or indirectly) into itself. - Initially, $ \text{border}(w) = 0 $, $ \text{spacing}(w) = 0 $ for all $ w $, unless explicitly set. **Size Computation Rules:** - For a non-container widget $ w $ (i.e., $ \text{type}(w) = \text{Widget} $), let $ (\text{width}(w), \text{height}(w)) $ be given as input via `set_size(w, w_w, w_h)`. - For an HBox widget $ h $: $$ \text{width}(h) = \begin{cases} 0 & \text{if } |\text{children}(h)| = 0 \\ \sum_{c \in \text{children}(h)} \text{width}(c) + (\text{len}(\text{children}(h)) - 1) \cdot \text{spacing}(h) + 2 \cdot \text{border}(h) & \text{otherwise} \end{cases} $$ $$ \text{height}(h) = \begin{cases} 0 & \text{if } |\text{children}(h)| = 0 \\ \max_{c \in \text{children}(h)} \text{height}(c) + 2 \cdot \text{border}(h) & \text{otherwise} \end{cases} $$ - For a VBox widget $ v $: $$ \text{width}(v) = \begin{cases} 0 & \text{if } |\text{children}(v)| = 0 \\ \max_{c \in \text{children}(v)} \text{width}(c) + 2 \cdot \text{border}(v) & \text{otherwise} \end{cases} $$ $$ \text{height}(v) = \begin{cases} 0 & \text{if } |\text{children}(v)| = 0 \\ \sum_{c \in \text{children}(v)} \text{height}(c) + (\text{len}(\text{children}(v)) - 1) \cdot \text{spacing}(v) + 2 \cdot \text{border}(v) & \text{otherwise} \end{cases} $$ **Input Processing:** - Parse $ n $ instructions. - Track for each widget: - Its type (initially `Widget`), - Its children (initially empty), - Its border and spacing (initially 0), - Its width and height (initially undefined for containers, 0 for leaf widgets unless set). - For each instruction: - `create HBox name`: add $ \text{type}(name) = \text{HBox} $, $ \text{children}(name) = \emptyset $. - `create VBox name`: add $ \text{type}(name) = \text{VBox} $, $ \text{children}(name) = \emptyset $. - `create Widget name`: add $ \text{type}(name) = \text{Widget} $, $ \text{width}(name) = 0 $, $ \text{height}(name) = 0 $. - `pack name1 name2`: append $ \text{children}(name1) \leftarrow \text{children}(name1) + [\text{name2}] $. - `set_border name b`: set $ \text{border}(name) = b $. - `set_spacing name s`: set $ \text{spacing}(name) = s $. - `set_size name w h`: set $ \text{width}(name) = w $, $ \text{height}(name) = h $. **Output:** - For each widget $ w \in W $, compute $ \text{width}(w) $, $ \text{height}(w) $ recursively using the above rules (topological sort on dependency graph). - Output each widget as: `name width height`, sorted lexicographically by `name`.