logo AlgoBeat OnlineJudge
登录 注册

#101575. [BZOJ 1575] [Usaco2009 Jan]气象牛Baric

内存限制:64 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

为了研究农场的气候, Betsy 帮助 FJ 做了 次气压测量并按顺序记录了结果 )。Betsy 想找出一部分测量结果来总结整天的气压分布。她想用 个数 )来概括所有测量结果。她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差。总误差是所有测量结果的误差之和。更明确地说,对于每一个和所有 都不同的

  • 如果 ,误差是
  • 如果 ,误差是
  • 如果 ,误差是

Besty 给了最大允许的误差 ,找出最小的一部分结果使得误差最多为

输入格式

第一行:两个空格分隔的数:

行:第 行包含一次测量记录:

输出格式

  • 第一行:共两个数:最少能达到误差小于等于 的测量数目和使用那个测量数目能达到的最小误差。

样例

样例输入 #1

4 20
10
3
20
40

样例输出 #1

2 17

数据范围与提示

对于 的数据,。 Bessie 做了 次记录,分别为 .最大允许误差是 ,选择第二和第四次测量结果能达到最小误差 。第一次结果的误差是,第三次结果的误差是

Usaco 2009 Jan Gold