#P2131. 彩球树

彩球树

题目描述

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

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

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

输入格式

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

输出格式

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

((B)())
0
((((B)(B))((B)()))(B))
impossible
(()(((B)(B))(B)))
1

提示

【图解】

[PIC=1259]

【数据规模】

对于 15% 的数据,保证输入文件不超过 25 字节。

对于 50% 的数据,保证输入文件不超过 250 字节。

对于 100% 的数据,保证输入文件不超过 5000 字节。

(PS:1字节≈1字符)

【时空限制】

0.1s/128M