P2131 彩球树

    • 1通过
    • 26提交
  • 题目提供者 LittleZ
  • 评测方式 云端评测
  • 标签 字符串 树形结构 高性能
  • 难度 尚无评定
  • 时空限制 256ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    ((B)())
    输出样例#1: 复制
    0
    输入样例#2: 复制
    ((((B)(B))((B)()))(B))
    输出样例#2: 复制
    impossible
    输入样例#3: 复制
    (()(((B)(B))(B)))
    输出样例#3: 复制
    1

    说明

    【图解】

    [PIC=1259]

    【数据规模】

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

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

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

    (PS:1字节≈1字符)

    【时空限制】

    0.1s/128M

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。