Nearest

 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
75
76
77
78
79
80
81
82
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
using namespace std;
#define FileName "nearest"
#define maxn 10000
#define Min(a, b) ((a) < (b) ? (a) : (b))
int a, n;
int x[maxn];
int fst[4*maxn+1];
int mrk[maxn];
int sign(int a) {
if (a == 0) return 0;
return (a > 0) ? 1 : -1;
}
int good(int i) {
return 0 <= i && i < 4*maxn+1;
}
void chk(int i, int w) {
if (good(i)) fst[i] = Min(fst[i], w);
}
void outof(int ind) {
int i = ind;
while (i != 2*maxn) {
mrk[fst[i]] = 1;
i -= 2*x[fst[i]];
}
int s = x[0];
for (i = 1; i < n; i++) if (mrk[i]) s+=x[i];
else s -= x[i];
printf("%d\n", s);
printf("%d", x[0]);
for (i = 1; i < n; i++) printf("%c%d", mrk[i] == 1 ? '+' : '-', x[i]);
}
int main(void) {
freopen(FileName".in", "r", stdin);
freopen(FileName".out", "w", stdout);
scanf("%d%d", &n, &a);
for (int i = 0; i < n; i++) scanf("%d", x+i);
if (abs(a-x[0])>maxn) {
int s=x[0];
for (int i=1; i<n; i++) if (sign(x[i])==sign(a)) s+=x[i];
else s-=x[i];
printf("%d\n", s);
printf("%d", x[0]);
for (int i=1; i<n; i++) if (sign(x[i])==sign(a)) printf("+%d", x[i]);
else printf("-%d", x[i]);
return 0;
}
int s=0;
for (int i=0; i<n; i++) s+=x[i];
for (int i=0; i<4*maxn+1; i++) fst[i] = 1000000;
fst[2*maxn]=0;
for (int i=1; i<n; i++) {
for (int j=0; j<4*maxn+1; j++) if (fst[j] < i) {
chk(j+2*x[i], i);
}
}
int aa=a+s-2*x[0]; // то, что на самом деле приближаем
/* for (int i = -10; i < 11; i++)
printf("%d:%d ", i, fst[i+2*maxn]); */
for (int i=0; i<=2*maxn; i++) {
if (good(2*maxn+aa-i) && fst[2*maxn+aa-i] < 1000000) {
outof(2*maxn+aa-i);
return 0;
} else if(good(2*maxn+aa+i) && fst[2*maxn+aa+i] < 1000000) {
outof(2*maxn+aa+i);
return 0;
}
}
return 0;
}