http://acm.pku.edu.cn/JudgeOnline/problem?id=3688
把牌从小到大排序, 然后DP.
复杂度O(NlogN + NM).
/**
* @version 2009/08/22
* @author sbzlyessit
*/
import java.io.*;
import java.util.*;
public class Main {
private static final int MAX_N = 10000, MAX_M = 100000;
private static BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
private static StringTokenizer st;
private static int[] list = new int[MAX_N];
private static int[] state = new int[MAX_M + 1];
private static int N, M;
public static void main(String[] argv) throws Exception {
int i, j, limit, len, result;
while (((N = nextInt()) | (M = nextInt())) != 0) {
for (i = 0; i < N; i++) {
list[i] = nextInt();
}
Arrays.sort(list, 0, N);
Arrays.fill(state, 0, M + 1, 0);
limit = 0;
state[0] = 2;
for (i = 0; i < N; i++) {
len = Math.min(limit, M - list[i]);
for (j = len; j >= 0; j--) {
if (state[j] > 0) {
if (state[j] == 3) {
state[j + list[i]] = 3;
} else {
state[j + list[i]] |= 3 - state[j];
}
}
}
limit = Math.min(limit + list[i], M);
}
for (result = 0, i = 1; i <= M; i++) {
if (state[i] == 1) {
result++;
}
}
System.out.println(result);
}
}
private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens()) {
st = new StringTokenizer(in.readLine());
}
return Integer.parseInt(st.nextToken());
}
}