#P1252. Euro Efficiency

    ID: 253 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>动态规划贪心难度普及/提高-Northwestern Europe 2002

Euro Efficiency

题目描述

2002年1月1日,荷兰和其他几个欧洲国家放弃本国货币,改用欧元。这一变化不仅在国际支付中,在日常支付中也带来了便利。

举例来说,在1月1日之前,学生购买一本价值68荷兰盾的书籍时,可以用1张50盾纸币和2张10盾纸币支付,并收到2盾的找零。简而言之:50+10+10-1-1=68。其他支付方式还有:50+25-5-1-1或100-25-5-1-1。无论哪种方式,支付过程中总是涉及5个单位(纸币或硬币),且无法用少于5个单位完成。

如今购买一本68欧元的书籍则更为简单:50+20-2=68,仅涉及3个单位。这并非巧合,在许多其他情况下,使用欧元支付比使用荷兰盾更高效。平均而言,欧元支付更高效。当然,这与欧元的价值无关,而是与所选的货币单位有关。荷兰盾的单位曾是:1, 2.5, 5, 10, 25, 50,而欧元的单位是:1, 2, 5, 10, 20, 50。

本题我们限制金额在100分以内。欧元硬币的面值为1, 2, 5, 10, 20, 50欧分。在支付[1,100]欧分范围内的任意金额时,平均涉及2.96个硬币(无论是支付还是找零)。欧元系列在这方面并非最优。例如,使用1, 24, 34, 39, 46, 50的硬币系列,支付68欧分只需2个硬币。在[1,100]范围内支付金额的平均硬币数为2.52。

然而,后者的计算更为复杂(尤其是心算)。这些计算可以很容易地编程到手机中,而如今几乎每个人都随身携带手机。为未来做准备,欧洲央行的一个委员会正在研究硬币系列的效率,以找到针对100欧分以下金额的最优硬币系列。他们需要你的帮助。

编写一个程序,给定一个硬币系列,计算支付1到100分(含)任意金额所需的平均和最大硬币数。假设支付双方都有足够的硬币可用。

输入格式

  • 第一行输入包含测试用例的数量。
  • 每个测试用例由一行6个不同的正整数描述:硬币的面值,按升序排列。第一个数字始终为1。最后一个数字小于100。

输出格式

  • 对于每个测试用例,输出一行,首先为平均硬币数(保留两位小数),然后是最大硬币数,两者用空格分隔。

示例输入输出

输入示例 1

3
1 2 5 10 20 50
1 24 34 39 46 50
1 2 3 7 19 72

输出示例 1

2.96 5
2.52 3
2.80 4