1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
#include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> using namespace std;
const int maxn = 12; const int maxm = (1 << 16) + 10; int a[maxn]; bool dp[maxm];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int main() { freopen("nuggets.in", "r", stdin); freopen("nuggets.out", "w", stdout); int n; scanf("%d", &n); dp[0] = true; for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); if (a[i] == 1) { puts("0"); return 0; } for (int j = a[i]; j < maxm; ++j) { dp[j] |= dp[j - a[i]]; } } for (int i = 1; i < n; ++i) { a[i] = gcd(a[i], a[i - 1]); } if (a[n - 1] != 1) { puts("0"); return 0; } int ans = maxm - 1; while (dp[ans]) { --ans; } printf("%d\n", ans); return 0; }
|