/* -*- coding: utf-8 -*- * * 27.cc: No.27 板の準備 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_V = 30; const int N = 4; typedef long long ll; const int INF = 1 << 30; const ll LINF = 1LL << 60; /* typedef */ typedef vector vi; typedef queue qi; typedef pair pii; /* global variables */ int vs[N], dp[2][MAX_V + 1]; /* subroutines */ int knapsak(int m, int a, int b, int c) { int cs[3] = {a, b, c}; for (int i = 0; i <= m; i++) dp[0][i] = INF; dp[0][0] = 0; int cur = 0, nxt = 1; for (int i = 0; i < 3; i++) { memcpy(dp[nxt], dp[cur], sizeof(dp[cur])); int ci = cs[i], c = ci; int v = 1; while (c <= m) { int max_j = m - c; for (int j = 0; j <= max_j; j++) if (dp[cur][j] < INF) { int d = dp[cur][j] + v; if (dp[nxt][j + c] > d) dp[nxt][j + c] = d; } c += ci; v++; } cur ^= 1; nxt ^= 1; } return dp[cur][m]; } /* main */ int main() { int minv = INF, maxv = 0; for (int i = 0; i < N; i++) { cin >> vs[i]; if (minv > vs[i]) minv = vs[i]; if (maxv < vs[i]) maxv = vs[i]; } //printf("%d-%d\n", minv, maxv); int minsum = INF, mina, minb, minc; for (int a = 1; a <= minv; a++) for (int b = a; b <= maxv; b++) for (int c = b; c <= maxv; c++) { //printf("a,b,c=%d,%d,%d\n", a, b, c); int sum = 0; for (int i = 0; i < N; i++) { int d = knapsak(vs[i], a, b, c); if (d >= INF) { sum = INF; break; } sum += d; } if (minsum > sum) minsum = sum, mina = a, minb = b, minc = c; } printf("%d\n", minsum); //printf("%d,%d,%d\n", mina, minb, minc); return 0; }