UOJ Logo

NOI.AC

#84. ticket

统计

列车抢票

时间限制:1秒,内存限制:128MB

读入文件名:ticket.in

输出文件名:ticket.out

【题目描述】

有一列火车,它有四种席位的票,分别是软卧、硬卧、硬座、无座,其中软卧、硬卧、硬座分别有$a$、$b$、$c$张票,无座不限票数。

现在有n个订单购票,依次为$x_1$张卧票,$x_2$张坐票,$x_3$张卧票,$x_4$张坐票……卧票订单和坐票订单交替,且第一个订单是卧票订单。

系统根据实际剩余票数按照订单顺序自动进行分配票种,具体规则如下:

对于卧票,优先提供软卧;如果软卧售空,则提供硬卧;如果卧票(包括软卧和硬卧)全部售空,则改为硬座;如果硬座也售空,则分配为无座。

对于坐票,优先提供硬座;如果硬座售空,但仍有硬卧,则会将一张硬卧替换为三张硬座出售;如果硬座和硬卧都售空,则分配为无座。

问最后共分配了多少无座。

注意:软卧不会被替换为硬座出售;每张硬卧被替换为硬座后,只能以硬座票出售,不得以卧票出售。

【输入格式】

输入分为2行。

第一行为四个正整数$a$、$b$、$c$、$n$,分别表示软卧、硬卧、硬座的票数,以及订单总数,用一个空格分隔。

第二行为n个正整数$x_1$到$x_n$,$x_i$表示第$i$个订单的票数,用一个空格分隔。

【输出格式】

输出一行一个数,表示最终分配的无座票个数。

【输入输出样例1】

ticket.in

2 2 2 4
2 1 1 4

ticket.out

0

【输入输出样例2】

ticket.in

1 1 1 2
4 2

ticket.out

3

【输入输出样例3】

ticket.in

2 2 1 4
1 10 1 1

ticket.out

4

【输入输出样例4】

ticket.in

2 2 1 4
1 3 3 2

ticket.out

2

【数据规模与约定】

对于前50%的数据,$1\le a,b,c\le 100000,1\le n\le 1000,\sum x_i\le 1000000$;

对于100%的数据,$1\le a,b,c\le 10^{12},1\le n\le 10^5,∑x_i\le 10^{15}$;

【样例解释】

对于样例1,第一个订单分配了2个软卧,第二个订单分配了1个硬座,第三个订单分配了1个硬卧,第四个订单将1个硬卧改为3个硬座,分配了4个硬座,因此没有售出无座。

对于样例2,第一个订单分配了1个软卧、1个硬卧、1个硬座和1个无座,第二个订单分配了2个无座,因此售出3个无座。

对于样例3,第一个订单分配了1个软卧,第二个订单将2个硬卧改为6个硬座,分配了7个硬座和3个无座,第三个订单分配了1个软卧,第四个订单分配了1个无座,因此售出了4个无座。

对于样例4,第一个订单分配了1个软卧,第二个订单将1个硬卧改为3个硬座,分配了3个硬座,第三个订单分配了1个软卧、1个硬卧、1个硬座,第四个订单分配了2个无座,因此售出了2个无座。