Preparing NOJ
ACM程序设计竞赛组织者有一个想法,为本次竞赛取得优秀成绩的选手准备一组奖品。如果获胜者的做题X道,那么他(她)必须选择总价值为X元的奖品。
组织者有一批来自于之前竞赛中的备用奖品,价值分别为a1, a2, . . . , an元。不幸地是,他们不知道获胜者的做出多少题。因此,组织者决定再购买m个奖品,使不能给获胜者发放奖品的最小整数得分最大化。
如果他们已经有了价值2, 3和9元的奖品,他们想购买2个奖品,则他们应购买1元和7元的奖品。那么,ACM程序设计竞赛的获胜者将能够收集从1到22中任何得分的奖品。
输入第一行包括两个整数:n和m ―― 组织者拥有的奖品数和他们准备购买的奖品数 (0 ≤ n ≤ 30, 1 ≤ m ≤ 30)。
第二行包括n个1和109之间的整数,即组织者拥有的奖品值。
输出m个整数,即组织者即将购买的奖品值。输出数以递增数目排序。如果解不唯一,则打印出所有的解。
注意:输出部分的结尾要求包含一个多余的空行。
3 2
2 3 9
1 7
本题由旧版NOJ导入,来源:“IBM南邮杯”个人赛2009