Untitled

mail@pastecode.io avatar
unknown
plain_text
4 years ago
829 B
2
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int dp[1000005];
int min(int a, int b) {
	return a < b ? a : b;
}
signed main() {
	int n;
	scanf("%d", &n);
	int b[102];
	for (int i = 0; i < 1000005; ++i)
		dp[i] = 1e9;
	for (int i = 0; i < n; ++i)
		scanf("%d", &b[i]), dp[b[i]] = 1;
	int mm;
	scanf("%d", &mm);
	dp[0] = 0;
	for (int i = 0; i <= mm; ++i) {
		if (dp[i] == -1)
			continue;
		for (int j = 0; j < n; ++j)
			if (i + b[j] <= mm)
				dp[i + b[j]] = min(dp[i + b[j]], dp[i] + 1);
	}
	if (dp[n] == 1e9) {
		printf("-1");
		return 0;
	}
	printf("%d\n", dp[mm]);
	int m = mm;
	int lm = m;
	while (m) {
		for (int j = 0; j < n; ++j)
			if (m - b[j] >= 0 && dp[m - b[j]] == dp[m] - 1) {
				m -= b[j];
				printf("%d ", b[j]);
				break;
			}
		if (lm == m) break;
		lm = m;
	}
}