/ Vijos / 题库 /

不给糖就捣乱

不给糖就捣乱

描述

万圣节就要到了。孩子们装扮成各种恐怖的样子,挨家挨户按响邻居的门铃,大喊:“Trick or Treat!(不给糖就捣乱)”。

XX准备了许多奇特有趣的面具——为了晚上的假面舞会,同时为了防止被孩子们捣乱,XX准备了万圣节糖果来发给索要糖果的孩子们。

XX有N种糖果罐,第i种糖果罐有a[i]颗糖果。每当有孩子来讨糖果时,他会将从中选出若干不同种类的糖果罐,使得其中的糖果总数恰好等于孩子讨要的糖果数;否则,孩子将无法得到糖果,而XX的假面舞会也将无法顺利的进行。

例如,XX有4种糖果罐,分别有1,4,5,5个糖果。那么他只能提供1,4,5,6,9,10,11,14,15这些数量的糖果。

现在XX可以调整其中一种糖果罐中糖果的数量为任意正整数,他想要能够提供的不同糖果数量尽可能多,也就是尽可能满足更多孩子的需求。问:
1. 应该调整哪一种糖果罐,如果有多个最优的糖果罐可以调整,应该调整编号最小的糖果罐。

2. 经过最优化调整之后该种糖果罐应该有多少个糖果,如果有多个最优调整方法,请使调整后该种糖果罐中糖果数最少(调整后的数量可以与调整前的数量相等)。

格式

输入格式

第一行是一个整数N,表示糖果罐种数。

下面N行,每行a[i]表示第i种糖果罐中糖果数。

输出格式

输出包括2行,每行一个整数,分别表示两问的答案。

样例1

样例输入1

4
1
4
5
5

样例输出1

3
7

限制

每个测试点2s。

提示

本题总共有10组数据,每组数据10分。

第一组——第三组:1<=N<=20,1<=a[i]<=20。

第四组——第六组:1<=N<=100,1<=a[i]<=7000,且a[i]均为偶数。

第七组——第十组:1<=N<=100,1<=a[i]<=7000。

From Boi2010

信息

ID
1747
难度
6
分类
动态规划 点击显示
标签
(无)
递交数
156
已通过
38
通过率
24%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Vijos2012年10月份月赛