【序列】

题目描述

有一个非递减的整数序列 S1,S2,S,……,Sn+1(Si≤Si+1)。定义序列 m1,m,… ,m为 S 的“M序列”,其中 mi=(Si+Si+1)/2。
例如,S=(1, 3, 3, 5),则 m=(2,3,4)。
现在给你序列 m ,要你求有多少个 S 序列的“M序列”是序列 m 。

输入格式

第一行一个整数 n ,
下接 n 行,每行一个整数 mi 。

输出格式

输出一个整数,表示有多少个 S 序列的“M序列”是序列 m 。

样例数据 1

输入

3
2
5
9

输出

4

备注

【样例说明】
存在如下四个数列 S 满足要求:
2,2,8,10;
1,3,7,11;
0,4,6,12;
-1,5,5,13。

【数据范围】
50% 的数据:n≤1000;mi≤20000
100% 的数据:2≤n≤100000;mi≤109

50分应该是暴力吧……正解是首先把S1假定为a 就可以得到n个不等式,先列出前面8个可以乱搞出一些规律,具体规律都写在代码里了,求出初始a的上界和下界即可,注意有MIN>MAX的情况要输出0!

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*