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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <bits/stdc++.h>
#define per(i, a, b) for(int i=(a);i<=b;i++)
#define _debug(x) cerr<<#x<<" = "<<x<<endl
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 59;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 59;
int kase, n, ans;
int a[105];
int b[105];
bool chek(int x, int i, int j, int k) {
per(_10, 0, i)
per(_20, 0, j)
per(_50, 0, k)
if (_10 * 10 + _20 * 20 + _50 * 50 == x)
return true;
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> kase;
while (kase--) {
ans = INF;
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
per(_10, 0, 10)
per(_20, 0, 5)
per(_50, 0, 2) {
int _100 = 0;
bool valid = true;
for (int i = 1; valid && i <= n; ++i) {
if (chek(a[i], _10, _20, _50)) {
_100 = max(_100, 0);
} else if (a[i] >= 300 && chek(a[i] % 100 + 200, _10, _20, _50)) {
_100 = max(_100, a[i] / 100 - 2);
} else if (a[i] >= 200 && chek(a[i] % 100 + 100, _10, _20, _50)) {
_100 = max(_100, a[i] / 100 - 1);
} else if (a[i] >= 100 && chek(a[i] % 100, _10, _20, _50)) {
_100 = max(_100, a[i] / 100);
} else {
valid = false;
}
}
if (valid)
ans = min(ans, _10 + _20 + _50 + _100);
}
if (ans == INF)ans = -1;
cout << ans << endl;
}
return 0;
}
|
