问题 25289 --量取

25289: 量取

时间限制: 1 Sec  内存限制: 128 MB
提交: 40  解决: 16
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

星哥要量取Q (1Q20000)体积的清水,把它倒进自己的游泳池中。

星哥向来节约。为了量出Q体积的水,他必须去商店里买一些称量用的提桶。由于每个桶的价格是一样的,你的任务就是帮星哥计算为了量出Q体积的水,最少要买哪一些提桶。由于星哥必须把这些东西搬回家,所以对于任意两个最少数量的候选方案,他会偏向更小一组,即把两组解按升序排列,比较第一个桶的容积,选择容积小的一组。如果排在第一的两个桶容积相同,就比较第二个,一直继续这样的工作,直到找到两个桶的容积不一致为止,例如{3,5,7,100} {3,6,7,8} 要好。

       量水时,星哥会用把提桶装满,然后倒进池子,他决不会把已经在一个桶里的水倒到别的桶里去。如果星哥有一个容积为1的桶,他可以只用这个桶量出所有的份量,但如果他遇到的是其它的组合就不会这么方便了。我们保证所有的测试数据至少有一个解,试确定购买的最优方案。

输入

第一行:单个整数Q 
第二行:单个整数P (1≤P≤100)表示商店里提桶的数量 
第三行到第P+2行:每行只有一个整数,表示某个提桶的容积 (1≤容积≤10000)

输出

输出文件只有一行,由空格分开的整数组成,包括: 
    为了量出指定的体积,需要购买的提桶的最少数量,其次是一个以升序排列的序列,表示需要购买的每个提桶的容积

样例输入

16
3
3
5
7

样例输出

2 3 5

提示

来源

[提交][状态]