POJ 3977

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <utility>
 6 
 7 using namespace std;
 8 
 9 
10 typedef long long ll;
11 typedef pair<ll,int> pii;
12 
13 
14 const ll INF = (1e17) + 5;
15 const  int MAX = 40;
16 
17 int N;
18 ll w[MAX];
19 pii ps[(1 << 20) + 5];
20 int cal[1 << 20],dx[4] = {-1,-2,0,1};
21 
22 ll Abs(ll x) {
23         return x > 0 ? x : -x;
24 }
25 
26 void init() {
27         for(int s = 0; s < (1 << 20); ++s) {
28                 int sum = 0;
29                 for(int i = 0; i < 20; ++i) {
30                         if(s >> i & 1) ++sum;
31                 }
32                 cal[s] = sum;
33         }
34 }
35 void solve() {
36         int n = N / 2;
37         ll sw = 0;
38         for(int s = 0; s < (1 << n); ++s) {
39                 sw = 0;
40                 for(int j = 0; j < n; ++j) {
41                         if(s >> j & 1) sw += w[j];
42                 }
43                 ps[s] = make_pair(sw,cal[s]);
44         }
45         sort(ps,ps + (1 << n));
46 
47         int n1 = N - n;
48         ll ansv = INF;
49         int anss = N;
50         for(int s = 0; s < (1 << n1); ++s) {
51                 sw = 0;
52                 for(int j = n; j < N; ++j) {
53                         if(s >> (j - n) & 1) sw += w[j];
54                 }
55                 int pos = lower_bound(ps,ps + (1 << n),make_pair(-sw,-1)) - ps;
56                 ll v = INF,t = INF;
57                 for(int i = 0; i < 4; ++i) {
58                         int id = pos + dx[i];
59                         if(id >= 0 && id < (1 << n)
60                            && (ps[id].second || s)) {
61                                 if(Abs(ps[id].first + sw) < t) {
62                                         t = Abs(ps[id].first + sw);
63                                         v = ps[id].first;
64                                 }
65                         }
66                 }
67                 pos = lower_bound(ps,ps + (1 << n),make_pair(v,-1)) - ps;
68                 if(s == 0 && ps[pos].second == 0) ++pos;
69                 if(ansv > Abs(v + sw) || ansv == Abs(v + sw) && anss > cal[s] + ps[pos].second) {
70                         ansv = Abs(v + sw);
71                         anss = cal[s] + ps[pos].second;
72                 }
73         }
74 
75         printf("%I64d %d\n",ansv,anss);
76 }
77 
78 int main()
79 {
80     freopen("sw.in","r",stdin);
81     init();
82     while(~scanf("%d",&N) && N) {
83             for(int i = 0; i < N; ++i) scanf("%I64d",&w[i]);
84             solve();
85     }
86 
87     return 0;
88 }