logo AlgoBeat OnlineJudge
登录 注册

#201110. 彩球树

内存限制:125 MiB 时间限制:256 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

小 Z 是一个聪明的小学生,他用塑料管和橡皮泥搭成了一棵树,每个橡皮泥上都连接着一个向下的塑料管,有的连接着两根向上的塑料管,有的则连接着一些彩球。

然而,这个工艺品很快因为不平衡倒了下来。于是,小 Z 请教了和他在同一个班上的妹子小 C。在百科全书上看到天平平衡原理的小 C 知道,如果任何一块橡皮泥向上连接的两根管子的载重量之差超过一个彩球的重量,工艺品就会不平衡倒下来。由于彩球比较重,橡皮泥和塑料管的重量可以忽略不计。

由于移动彩球需要花时间拆卸和固定,小 C 希望移动最少次数彩球让这个工艺品平衡起来。你能帮助她吗?


给定一棵叶子带权值二叉树,保证每个非叶子结点都有两个儿子,权值只能是

你可以进行以下操作若干次:选中两个叶子,交换它们的权值。

定义一颗子树的权值为子树内所有叶子的权值之和。

你希望通过以上操作使得任意非叶子结点的左子树权值和右子树权值相差不超过

求达成以上目标需要的最少操作次数。

输入格式

一行一个字符串 ,以中序遍历的方式描述了这棵树,B 表示彩球。


形式化的, 的 CFG(上下文无关文法)定义为:

<T> := (<T><T>) | (B) | ()
项目 含义
(<T><T>) 一个非叶子结点,两个 <T> 分别为它的左子树和右子树
(B) 一个权值为 的叶子结点
() 一个权值为 的叶子结点

输出格式

输出一个数字,表示最少移动多少个彩球就能使它平衡,或输出 impossible,表示如何移动多少个都无法平衡。


输出一个数字,表示至少需要多少次操作,或输出 impossible,表示不可能达成目标。

样例

样例输入 1

((B)())

样例输出 1

0

样例输入 2

((((B)(B))((B)()))(B))

样例输出 2

impossible

样例输入 3

(()(((B)(B))(B)))

样例输出 3

1

数据范围与提示

【样例解释】

【数据规模】

为字符串 的长度。

对于 的数据,

对于 的数据,

对于 的数据,