比赛场次 196
比赛名称 20110414pm
比赛状态 已结束比赛成绩
开始时间 2013-04-01 14:30:00
结束时间 2013-04-01 17:30:00
开放分组 全部用户
注释介绍
题目名称 气象牛
输入输出 baric.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatarfeng AAAAAAAAAA 0.011 s 3.23 MiB 100

气象牛

★★★   输入文件:baric.in   输出文件:baric.out   简单对比
时间限制:1 s   内存限制:128 MiB

气象牛 [Jeffrey Wang, 2007]

为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1...M_N(1 <= M_i <= 1,000,000). 

Betsy想找出一部分测量结果来总结整天的气压分布.她想用K(1 <= K <= N)个数s_j (1 <= s_1 < s_2 < ... < s_K <= N)来概括所有

测量结果. 她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.

更明确第说,对于每一个和所有s_j都不同的i:

 如果 i 小于 s_1, 误差是: 2 * | M_i - M_(s_1) | 

 如果i在s_j和s_(j+1)之间,误差是: | 2 * M_i - Sum(s_j, s_(j+1)) | 

 注:Sum(x, y) = M_x + M_y; (M_x 和 M_y 之和) * 

 如果i大于s_K,误差为: 2 * | M_i - M_(s_K) |

 Besty给了最大允许的误差E (1 <= E <= 1,000,000),找出最小的一部分结果使得误差最多为E.


输入格式: 

    第一行: 两个空格分离的数: N 和 E * 第2..N+1行: 第i+1行包含一次测量记录:M_i 

输出格式:

    第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目和使用那个测量 数目能达到的最小误差.

样例输入:

    4 20 10 3 20 40

输入解释: 

    Bessie做了4次记录,分别为10,3,20,和40.最大允许误差是20.

样例输出 :

    2 17

输出解释:

   选择第二和第四次测量结果能达到最小误差17. 第一次结果的误差是2*|10-3| = 14; 第三次结果的误差是|2*20 - (3+40)|=3.