【题解】闯关游戏 | 您所在的位置:网站首页 › 游戏闯关关卡 › 【题解】闯关游戏 |
题目描述
艾伦正在闯关。游戏有N个关卡,按照必须完成的顺序编号为1到N。每个关卡可以用两个参数来描述:prob [i]和value [i]。这些参数的含义如下: 每当艾伦尝试闯第i关时,他要么顺利通过,要么“挂掉”。他完成该关卡的概率总是prob [i] / 1000。(他总是尽力完成每个关卡。)在关卡i的末尾有一个宝箱,其中包含价值 value[i]单位的黄金。当艾伦完成关卡时,他从拿起该关卡的金币。 初始化时,艾伦从第1级关卡开始,艾伦没有黄金。对于每个有效的i,每当Allen完成关卡i时,他就会继续进行关卡i + 1,一旦完成第N个关卡,游戏就会结束。 每当艾伦“挂掉”时,下面4件事情会按顺序发生: 1、除了艾伦携带的黄金,其他黄金都被从游戏中移除。 2、艾伦目前所携带的所有黄金都“坠落”,“坠落”的地点就是艾伦“挂掉”的那个关卡的开头处。一旦艾伦以后再次达到这个关卡,即使在尝试闯该关卡之前,他也能够再次“捡起”上次“坠落”到这个地方的黄金。(请注意,如果他在到达这个关卡之前再次“挂掉”,这些黄金将永远消失。) 3、所有箱子都添加了新的黄金,各个箱子黄金的量就是它们最初所含的量(相当于初始化各个箱子的黄金量)。 4、艾伦回到了第1级的开头,且他没有携带金币。艾伦有无限条“生命”,“挂掉”后可以重新开始游戏。 通过上面的规则可以发现,艾伦“挂掉”后,最多只有一堆金币不在宝箱中,这一堆金币的位置就是艾伦最近“挂掉”所在的关卡的开头处。 为了避免精确错误,数据保证艾伦在一次性闯关全部成功的情况下赢得整个游戏的概率将至少为10 ^( - 6)。你的任务是输出艾伦顺利闯完第N关时所携带的黄金的期望值。 输入格式 多组测试数据。 第一行,一个整数G,表示有G组测试数据。1 |
CopyRight 2018-2019 实验室设备网 版权所有 |