Gaby And Addition Gym - 101466A （初学字典树）

93 阅读 0 评论 62 点赞

我是靠谱客的博主美好夕阳，这篇文章主要介绍Gaby And Addition Gym - 101466A （初学字典树），现在分享给大家，希望可以做个参考。

Gaby is a little baby who loves playing with numbers. Recently she has learned how to add 2 numbers using the standard addition algorithm which we summarize in 3 steps:

Line up the numbers vertically matching digits places.
Add together the numbers that share the same place value from right to left.
Carry if necessary.

it means when adding two numbers we will get something like this:

$\text{[math]}$

Unfortunately as Gaby is too young she doesn't know what the third step means so she just omitted this step using her own standard algorithm (Gaby's addition algorithm). When adding two numbers without carrying when necessary she gets something like the following:

$\text{[math]}$

Gaby loves playing with numbers so she wants to practice the algorithm she has just learned (in the way she learned it) with a list of numbers adding every possible pair looking for the pair which generates the largest value and the smallest one.

She needs to check if she is doing it correctly so she asks for your help to find the largest and the smallest value generated from the list of numbers using Gaby's addition algorithm.

Input

The input starts with an integer n (2 ≤ n ≤ 10⁶) indicating the number of integers Gaby will be playing with. The next line contains n numbers n_i (0 ≤ n_i ≤ 10¹⁸) separated by a single space.

Output

Output the smallest and the largest number you can get from adding two numbers from the list using Gaby's addition algorithm.

Examples

Input

复制代码

1
6
17 5 11 0 42 99

Output

复制代码

1
0 99

Input

复制代码

1
7
506823119072235413 991096248449924896 204242310783332529 778958050378192979 384042493592684633 942496553147499866 410043616343857825

Output

复制代码

1
52990443860776502 972190360051424498

Note

In the first sample input this is how you get the minimum and the maximum value

这题也是被安排的明明白白组队训练的时候这题不会做

后面说是字典树学了2个小时字典树还是没写出来

心态蹦了

现学字典树

复制代码

1 #include <bits/stdc++.h>
 2 #define
pi acos(-1.0)
 3 #define
eps 1e-6
 4 #define
fi first
 5 #define
se second
 6 #define
lson l,m,rt<<1
 7 #define
rson m+1,r,rt<<1|1
 8 #define
bug
printf("******n")
 9 #define
mem(a,b)
memset(a,b,sizeof(a))
10 #define
fuck(x)
cout<<"["<<x<<"]"<<endl
11 #define
f(a)
a*a
12 #define
sf(n)
scanf("%d", &n)
13 #define
sff(a,b)
scanf("%d %d", &a, &b)
14 #define
sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
15 #define
sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
16 #define
pf
printf
17 #define
FIN
freopen("DATA.txt","r",stdin)
18 #define
gcd(a,b)
__gcd(a,b)
19 #define
lowbit(x)
x&-x
20 #pragma
comment (linker,"/STACK:102400000,102400000")
21 using namespace std;
22 typedef long long LL;
23 typedef unsigned long long ULL;
24 const int INF = 0x7fffffff;
25 const LL LLINF = 0x3f3f3f3f3f3f3f3fll;
26 const int maxn = 1e6 + 10;
27 const int mod = 1e9 + 7;
28 LL t[20], a[maxn];
29 struct trie {
30
int cnt[maxn * 15], tree[maxn * 15][10], arr[20], root, rear;
31
int newnode() {
32
cnt[++rear] = 0;
33
mem(tree[rear], 0);
34
return rear;
35 
}
36
void init() {
37
rear = 0;
38
root = newnode();
39 
}
40
void add(LL x) {
41
int now = root, temp;
42
for (int i = 0 ; i < 19 ; i++) arr[i] = x % 10, x /= 10;
43
for (int i = 18 ; i >= 0 ; i--) {
44
temp = arr[i];
45
if (!tree[now][temp]) tree[now][temp] = newnode();
46
now = tree[now][temp];
47
cnt[now]++;
48 
}
49 
}
50 
LL query1(LL x) {
51
int now = root, maxx, idx;
52
LL ret = 0;
53
for (int i = 0 ; i < 19 ; i++) arr[i] = x % 10, x /= 10;
54
for (int i = 18 ; i >= 0 ; i--) {
55
maxx = -1, idx = -1;
56
for (int j = 0 ; j < 10 ; j++)
57
if (tree[now][j] && (arr[i] + j) % 10 > maxx) maxx = (arr[i] + j) % 10, idx = j;
58
ret += t[i] * maxx;
59
now = tree[now][idx];
60 
}
61
return ret;
62 
}
63 
LL query2(LL x) {
64
int now = root, maxx, idx;
65
LL ret = 0;
66
for (int i = 0 ; i < 19 ; i++) arr[i] = x % 10, x /= 10;
67
for (int i = 18 ; i >= 0 ; i--) {
68
maxx = 10, idx = -1;
69
for (int j = 0 ; j < 10 ; j++)
70
if (tree[now][j] && (arr[i] + j) % 10 < maxx
)
maxx = (arr[i] + j) % 10, idx = j;
71
ret += t[i] * maxx;
72
now = tree[now][idx];
73 
}
74
return ret;
75 
}
76 } tr;
77 int main() {
78
t[0] = 1;
79
for (int i = 1 ; i < 19 ; i++) t[i] = t[i - 1] * 10;
80
int n;
81 
sf(n);
82
LL ans1 = (1LL) << 62, ans2 = 0;
83 
tr.init();
84
for (int i = 0 ; i < n ; i++) {
85
scanf("%lld", &a[i]);
86
if (i) {
87
ans1 = min(ans1, tr.query2(a[i]));
88
ans2 = max(ans2, tr.query1(a[i]));
89 
}
90 
tr.add(a[i]);
91 
}
92
printf("%lld %lldn", ans1, ans2);
93
return 0;
94 }

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 1 #include <bits/stdc++.h>
 2 #define
pi acos(-1.0)
 3 #define
eps 1e-6
 4 #define
fi first
 5 #define
se second
 6 #define
lson l,m,rt<<1
 7 #define
rson m+1,r,rt<<1|1
 8 #define
bug
printf("******n")
 9 #define
mem(a,b)
memset(a,b,sizeof(a))
10 #define
fuck(x)
cout<<"["<<x<<"]"<<endl
11 #define
f(a)
a*a
12 #define
sf(n)
scanf("%d", &n)
13 #define
sff(a,b)
scanf("%d %d", &a, &b)
14 #define
sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
15 #define
sffff(a,b,c,d) scanf("%d %d %d %d", &a, &b, &c, &d)
16 #define
pf
printf
17 #define
FIN
freopen("DATA.txt","r",stdin)
18 #define
gcd(a,b)
__gcd(a,b)
19 #define
lowbit(x)
x&-x
20 #pragma
comment (linker,"/STACK:102400000,102400000")
21 using namespace std;
22 typedef long long LL;
23 typedef unsigned long long ULL;
24 const int INF = 0x7fffffff;
25 const LL LLINF = 0x3f3f3f3f3f3f3f3fll;
26 const int maxn = 1e6 + 10;
27 const int mod = 1e9 + 7;
28 LL t[20], a[maxn];
29 struct trie {
30
int cnt[maxn * 15], tree[maxn * 15][10], arr[20], root, rear;
31
int newnode() {
32
cnt[++rear] = 0;
33
mem(tree[rear], 0);
34
return rear;
35 
}
36
void init() {
37
rear = 0;
38
root = newnode();
39 
}
40
void add(LL x) {
41
int now = root, temp;
42
for (int i = 0 ; i < 19 ; i++) arr[i] = x % 10, x /= 10;
43
for (int i = 18 ; i >= 0 ; i--) {
44
temp = arr[i];
45
if (!tree[now][temp]) tree[now][temp] = newnode();
46
now = tree[now][temp];
47
cnt[now]++;
48 
}
49 
}
50 
LL query1(LL x) {
51
int now = root, maxx, idx;
52
LL ret = 0;
53
for (int i = 0 ; i < 19 ; i++) arr[i] = x % 10, x /= 10;
54
for (int i = 18 ; i >= 0 ; i--) {
55
maxx = -1, idx = -1;
56
for (int j = 0 ; j < 10 ; j++)
57
if (tree[now][j] && (arr[i] + j) % 10 > maxx) maxx = (arr[i] + j) % 10, idx = j;
58
ret += t[i] * maxx;
59
now = tree[now][idx];
60 
}
61
return ret;
62 
}
63 
LL query2(LL x) {
64
int now = root, maxx, idx;
65
LL ret = 0;
66
for (int i = 0 ; i < 19 ; i++) arr[i] = x % 10, x /= 10;
67
for (int i = 18 ; i >= 0 ; i--) {
68
maxx = 10, idx = -1;
69
for (int j = 0 ; j < 10 ; j++)
70
if (tree[now][j] && (arr[i] + j) % 10 < maxx
)
maxx = (arr[i] + j) % 10, idx = j;
71
ret += t[i] * maxx;
72
now = tree[now][idx];
73 
}
74
return ret;
75 
}
76 } tr;
77 int main() {
78
t[0] = 1;
79
for (int i = 1 ; i < 19 ; i++) t[i] = t[i - 1] * 10;
80
int n;
81 
sf(n);
82
LL ans1 = (1LL) << 62, ans2 = 0;
83 
tr.init();
84
for (int i = 0 ; i < n ; i++) {
85
scanf("%lld", &a[i]);
86
if (i) {
87
ans1 = min(ans1, tr.query2(a[i]));
88
ans2 = max(ans2, tr.query1(a[i]));
89 
}
90 
tr.add(a[i]);
91 
}
92
printf("%lld %lldn", ans1, ans2);
93
return 0;
94 }