硬币问题

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 kouka.in 输出文件 kouka.out

【题目描述】

有 n 种硬币，面值分别为 $v_1, v_2, \cdots , v_n$ ，每种都有无限多。给定非负整数 S ，可以选用多少个硬币，使得面值之和恰好为 S ？输出硬币数目的最小值和最大值。

【输入格式】

第一行两个整数 $n, S (1\le n\le 100, 0\le S\le 100000)$。

第二行 $n$ 个整数 $v_{i=1..n} (1\le v_i \le S) $。

【输出格式】

第一行两个整数，分别表示硬币数目的最小值 a 和最大值 b 。无解则输出 -1 。

第二行 a 个整数分别表示使用的是第几种硬币。

第三行 b 个整数分别表示使用的是第几种硬币。

【样例输入】 

6 12
1 2 3 4 5 6

【样例输出】 

2 12
6 6
1 1 1 1 1 1 1 1 1 1 1 1

【提示】

样例是特殊的，编号和面值是相同的。你编写程序的时候要注意输出编号而不是面值。

结果按编号升序输出字典序小一种。

【来源】

算法竞赛入门经典 例题 9-3