TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3779
  • 题目
  • P3779账本
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    Byteasar有一个帐户在byteotian位银行(BBB的简称)。该账户最开始有p bythalers,最后剩下q bythalers。该账户中,每一笔交易是要么是存1 个bythaler,要么是取1个bythaler,该账户的余额从来都没有出现过负数。银行前台准备了交易报表:一个只有加号和减号的有序序列(分别表示存钱和取钱)

    然而悲剧的事情是:这个报表是有问题,现在前台人员必须更正已经打印出来的报表,报表并不需要与事实完全相符,只要满足以下两个条件就行了:

    1、 最后的余额与给出的余额一致;

    2、 账户中的余额从未是负数;

    你需要计算,前台修改报表需要的最小时间,前台人员可以做这些事情:

    操作1:x时间内,将某一项操作改成对立面(+改成-号,-改成+);

    操作2:y时间,将最后一项提到最前。

    例如:p=2,q=3,则:--++-+-++-+-+是一个正确的报表,但是---++++++就不是一个正确的报表,因为在第3笔交易后余额就为负数了(不满足条件2),同时,最后,账户的余额变成了5,但正确的应该是3.但是可以通过将第二个+号改成-,然后再将最后一个操作放到最前面,使得报表符合条件。

    现在你的任务是,写一个程序,计算出前台修改报表所需要的最小时间

    输入格式

    第一行5个变量:n,p,q,x,y,n表示报表长度,p,q,x,y如题目所述意义

    第二行n个字符,表示报表

    输出格式

    一行,表示最少需要调整的时间,保证输入数据都是有解的。

    样例输入

    9 2 3 2 1
    ---++++++

    样例输出

    3

    提示

    20%: 1≤ n ≤ 100, 1 ≤ p,q ≤100

    50%:  1≤ n ≤ 10000,

    100% : 1 ≤ n ≤ 1000000, 0 ≤ p,q ≤ 1000000, 1 ≤ x,y ≤ 1000