Problem Statement
You have a tree. Its vertices are numbered from 0 to N-1.
You want to place some tokens onto the vertices of the tree. Each vertex may contain at most one token. Each simple path may contain at most K tokens. Maximize the number of tokens on the tree and return that maximum.
For each i between 0 and N-2, inclusive, the tree contains an undirected edge between vertices (i+1) and P[i].
For all i we will have P[i] < (i+1), which ensures that the collection of N-1 edges is a tree.
In order to keep the input small, the tree is (mostly) pseudorandom. Please use the pseudocode below to generate its array P.
state = seed
L = length(Pprefix)
for i = 0 to L-1:
P[i] = Pprefix[i]
for i = L to N-2:
lo = max(0, i-D+1)
state = (state * 1103515245 + 12345) modulo 2^31
P[i] = lo + (state modulo (i-lo+1))
Definition
- Class:
- TokenTree
- Method:
- maxTokens
- Parameters:
- int, int, int[], int, int
- Returns:
- int
- Method signature:
- int maxTokens(int N, int K, int[] Pprefix, int D, int seed)
- (be sure your method is public)
Notes
- The reference solution does not depend on the input being pseudorandom.
- The parameter D used in the pseudocode influences the shape of the resulting tree.
Constraints
- N will be between 1 and 500,000, inclusive.
- K will be between 1 and N, inclusive.
- Pprefix will contain between 0 and min(N-1, 200) elements.
- For each i, Pprefix[i] will be between 0 and i, inclusive.
- D will be between 1 and N, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
Examples
8
4
{}
1
47
Returns: 4
Regardless of the random seed, the choice D = 1 ensures that the generated tree will be a path: you will get P = {0, 1, 2, 3, 4, 5, 6} and thus the tree edges are 0-1, 1-2, ..., 6-7. Clearly, you can place up to four tokens anywhere you like and you will have a valid solution. You cannot place more than four tokens because then the path that is the whole tree would contain too many tokens.
8
2
{0, 0, 0, 0, 0, 0, 0}
8
42
Returns: 7
We are given the entire array P in Pprefix. The tree is a star with 0 in the center. No path may contain more than two tokens. The optimal solution is to place a token into each of the vertices 1-7.
8
7
{0, 0, 0, 0, 0, 0, 0}
8
23236
Returns: 8
Same graph as in the previous example but now each path may contain up to 7 tokens. The optimal solution is to simply place a token everywhere, so the total number of tokens is N = 8.
10
4
{0, 0, 1}
4
12345
Returns: 7
Here you should generate P = {0, 0, 1, 2, 4, 2, 4, 6, 8}. The generated tree is depicted below. 3 --- 1 --- 0 --- 2 --- 6 --- 8 --- 9 | | 5 --- 4 --- 7 One optimal solution is to place seven tokens at vertices 0, 1, 4, 5, 6, 7, and 9.
1234
1
{}
47
23325
Returns: 1
If no simple path may contain more than one token, there can only be at most one token on the entire tree. We can place one token anywhere we like, all those solutions are valid and therefore optimal.
500000
500
{}
4
3226236
Returns: 375496
500000
15000
{}
1
12512
Returns: 15000
500000
30
{}
500000
500000
Returns: 499948
1
1
{}
1
284290351
Returns: 1
2
1
{0}
2
1983085133
Returns: 1
3
1
{}
1
2144595767
Returns: 1
4
1
{}
2
581846500
Returns: 1
5
1
{}
1
1396777957
Returns: 1
6
3
{}
1
819222983
Returns: 3
7
7
{}
3
1397798546
Returns: 7
8
1
{}
2
1646888126
Returns: 1
9
6
{0, 0, 0, 2, 4, 5, 2, 0}
1
822004006
Returns: 9
10
4
{0, 1, 2, 1, 1, 5}
4
1037122419
Returns: 7
11
4
{}
10
1254627237
Returns: 8
12
1
{0, 1, 1, 2, 2, 3, 6}
8
1579559189
Returns: 1
13
1
{0, 1}
10
763289261
Returns: 1
14
3
{0, 1, 0, 1, 4, 5, 4, 3}
12
1536326541
Returns: 8
15
14
{0, 1, 1, 2, 4, 0, 6, 3, 4, 7}
3
932258961
Returns: 15
16
14
{0, 0, 0, 1, 1, 4, 0}
6
1952515208
Returns: 16
17
6
{0, 1, 1, 3, 2, 4, 0}
6
1963767647
Returns: 14
18
2
{0, 1, 2, 2, 4, 1, 5, 5, 5}
3
1993797869
Returns: 8
19
6
{0, 1, 0, 1, 1, 2, 1, 4, 0, 3}
1
39643438
Returns: 11
20
2
{}
3
1941996298
Returns: 7
21
21
{}
7
1184530319
Returns: 21
22
12
{}
1
809585589
Returns: 12
23
1
{}
1
1062406038
Returns: 1
24
6
{}
3
1314441501
Returns: 12
25
7
{0, 1, 2, 1}
14
1870066971
Returns: 23
418422
7
{}
128
1103924062
Returns: 415138
471044
1
{0, 0, 1, 0, 0, 1, 1, 5, 5, 1, 10, 7, 4, 4, 12, 11, 6, 1, 8, 15, 7, 21, 3, 16, 9, 5, 12, 8, 23, 18, 29, 12, 17, 10, 10, 20, 9, 17, 30, 6, 18, 16, 9, 25, 43, 14, 14, 11, 5, 18, 33, 9, 52, 29, 49, 18, 2, 6, 56, 43, 35, 61, 14, 26, 13, 25, 63, 49, 38, 32, 1, 42, 46, 53, 12, 11, 42, 33, 68, 29, 74, 17, 31, 63, 70, 80, 25, 4, 21, 3, 72, 40, 29, 87, 46, 29, 31, 62, 47, 25, 54, 23, 59, 76, 78, 28, 4, 98, 52, 59, 29, 54, 98, 2, 54, 79, 65, 8, 62, 24, 50, 24, 92, 0, 30, 63, 66, 3, 75, 122, 80, 78, 132, 129, 96, 56}
2
938498403
Returns: 1
499898
61671
{0, 0, 1, 2, 0, 5, 4, 5, 8, 1, 9, 5, 8, 13, 6, 8, 4, 1, 6, 1, 18, 8, 22, 8, 5, 11, 19, 11, 7, 18, 18, 8, 15, 6, 8, 23, 3, 9, 11, 24, 17, 33, 4, 39, 34, 9, 15, 20, 29, 33, 47, 45, 16, 6, 22, 48, 16, 0, 40, 35, 17, 34, 17, 59, 59, 19, 46, 17, 26, 2, 12, 6, 49, 63, 26, 67, 73, 20, 47, 7, 71, 23, 70, 30, 61, 61, 54, 7, 63, 88, 89, 88, 29, 65, 73, 41, 65, 28, 49, 94, 58, 17}
42
850885441
Returns: 499898
443584
1
{0, 1, 2, 3, 4, 3, 6, 0, 2, 9, 6, 6, 0, 8, 0, 1, 3, 6, 15, 6, 17, 1, 17, 3, 0, 10, 8, 15, 8, 3, 29, 7, 22, 30, 0, 17, 36, 29, 28, 11, 7}
444
2000790934
Returns: 1
407065
34915
{0, 0, 1, 1, 1, 5, 4, 2, 3, 7, 8, 11, 1, 4, 12, 3, 15, 6, 1, 4, 16, 8, 4, 8, 11, 4, 10, 27, 25, 21, 26, 23, 8, 9, 27, 26, 36, 20, 11, 38, 24, 1, 6, 27, 10, 43, 4, 6, 8, 6, 50, 4, 51, 13, 1, 11, 52, 24, 6, 4, 52, 35, 30, 2, 15, 22, 42, 16, 16, 35, 28, 17, 6, 49, 20, 53, 70, 3, 9, 31, 64, 54, 65, 80, 76, 8, 45, 31, 45, 34, 24, 5, 39, 5, 22, 7, 67, 39, 39, 55, 91, 43, 6, 47, 95, 100, 83, 76, 32, 81, 23, 66, 100, 101, 80, 20, 24, 79, 3, 68, 96, 101, 59, 29, 100, 33, 53, 122, 1, 13, 87, 104, 23, 19, 87, 53, 66, 87, 30, 38, 115, 96, 86, 51, 65, 70, 117, 63, 123, 45, 147, 104, 99, 50, 9, 82, 11, 60, 17, 29, 70, 61, 123, 112}
19
35518693
Returns: 401372
476891
1604
{}
447
1600369265
Returns: 475745
447849
37
{0, 1, 2, 2, 4, 3, 1, 4, 1, 7, 6, 9, 10, 4, 3, 7, 1, 5, 1, 9, 20, 13}
48990
910412986
Returns: 443405
407392
364
{}
1585
572486780
Returns: 404523
454557
9
{}
89037
779601002
Returns: 352176
479019
14
{0, 1, 2, 1, 4, 0, 5, 4, 4, 6, 9, 9, 5, 5, 3, 9, 6, 10, 12, 11, 6, 4, 11, 16, 0, 14, 4, 17, 11, 28, 12, 5, 5, 4, 26, 32, 9, 11, 10, 28, 4, 13, 23, 43, 24, 12, 31, 44, 4, 40, 35, 31, 12, 3, 1, 20, 35, 12, 24, 0, 8, 35, 42, 50, 47, 29, 13, 31}
113
1106715330
Returns: 376306
477212
29368
{0, 0, 0, 1, 2, 4, 6, 5, 2, 0, 10, 0, 2, 10, 2, 5, 1, 0, 11, 6, 0, 16, 4, 0, 23, 10, 23, 8, 9, 13, 27, 9, 28, 28, 10, 10, 33, 27, 0, 8, 11, 31, 8, 26, 23, 1, 0, 37, 29, 13, 19, 10, 17, 33, 46, 49, 19, 42, 39, 26, 11, 54, 20, 12, 47, 28, 26, 58, 56, 23, 28, 35, 3, 12, 50, 6, 46, 72, 7, 56, 4, 13, 32, 43, 84, 27, 47, 1, 44, 28, 27, 25, 23, 43, 30, 49, 7, 85, 14, 16, 78, 65, 79, 53, 41, 46, 57, 62, 59, 101, 63, 75, 21, 113, 97, 4, 53, 75, 112, 64, 104, 69, 59}
1782
1860540694
Returns: 477212
422342
95589
{0, 1, 1, 1, 3, 1, 6, 3, 1, 7, 10, 6, 9, 3, 7, 0, 10, 7, 6, 10, 18, 16, 7, 0, 12, 22, 1, 16, 18, 10, 17, 20, 22, 32, 29, 2, 36, 11, 6, 13, 4, 16, 36, 17, 24, 37, 42, 1, 6, 33, 32, 49, 43, 23, 46, 26, 16, 49, 22, 58, 17, 44, 9, 63, 16, 19, 39, 36, 5, 55, 46, 69, 49, 72, 56, 70, 0, 33, 36, 61, 32, 71, 49, 20, 25, 50, 52, 81, 59, 7, 37, 63, 12, 66, 80, 38, 91, 46, 66, 70, 31, 10, 73, 8, 4}
24
1356985685
Returns: 422342
453426
5
{0, 0, 2, 1, 3, 1, 0, 7, 0, 3, 1, 5, 0, 7, 1, 2, 15, 6, 5, 2, 5, 2, 6, 6, 5, 18, 25, 23, 21, 28, 6, 25, 30, 25, 2, 34, 10, 12, 35, 39, 3, 21, 5, 17, 32, 29, 28, 26, 14, 31, 13}
343
1664609069
Returns: 240958
439725
353121
{}
543
181239049
Returns: 439725
499486
181065
{}
305411
1874260721
Returns: 499486
473051
129
{}
247
1877815465
Returns: 457430
411625
72390
{}
6454
1474073195
Returns: 411625
439347
8162
{}
803
1327818572
Returns: 439347
464604
1697
{0, 0, 2, 0, 0, 5, 3, 7, 8, 4, 6, 5, 10, 2, 10, 2, 3, 11, 6, 8, 15, 9, 19, 11, 23, 10, 6, 6, 6, 27, 28, 11, 10, 13, 30, 23, 19, 10, 25, 20, 37, 24, 7, 7, 26, 0, 1, 12, 24, 10, 43, 45, 43, 43, 42, 30, 7, 2, 15, 42, 1, 13, 4, 54, 52, 25, 28, 17, 60, 57, 9, 20, 39, 10, 55, 74, 51, 36, 66, 22, 18, 27, 45, 66, 47, 32, 9, 17, 69, 85, 10, 31, 77, 39, 46, 58, 92, 80, 21, 82, 64, 56, 77, 55, 12, 20, 90, 95, 70, 5, 18, 60, 100, 76}
929
1987193479
Returns: 464604
466428
14977
{}
100861
753817100
Returns: 466428
455838
13
{0, 1, 2, 0, 1, 0, 6, 2, 5, 5, 10, 6, 4, 13, 11, 1, 14, 13, 0, 17, 1, 0, 22, 1, 19, 3, 1, 3, 17, 28, 3, 15, 0, 9, 19, 32, 30, 0, 5, 32, 38, 34, 39, 36, 16, 30, 11, 13}
106
363472480
Returns: 395122
487987
8
{0, 0, 0, 3, 3, 1, 5, 1, 6, 5, 6, 5, 12, 11, 13, 5, 9, 13, 15, 18, 7, 9, 14, 10, 12, 16, 9, 26, 13, 19, 24, 21, 28, 0, 9, 15, 22, 14, 7, 19, 5, 30, 20, 6, 20, 0, 25, 12, 33, 17, 34, 15, 8, 47, 50, 40, 2, 3, 19, 8, 38, 31, 50, 38, 12, 63, 55, 24, 53, 14, 46, 50, 59, 23, 35, 36, 4, 75, 74, 36, 31, 4, 37, 43, 3, 62, 72, 49, 88, 85, 35, 82, 53, 77, 22, 85, 14, 75, 0, 49, 83, 68, 97, 71, 47, 93, 11, 71, 84, 88, 25, 72, 56, 65, 69, 98, 67, 108, 90, 94, 85, 19, 31, 120, 77, 45, 102, 122, 102, 95, 108, 73, 101, 43, 46, 52, 127, 91, 138, 65, 107, 91, 97, 67, 42, 101, 13, 11, 98, 137, 112, 83, 9, 70, 98, 99, 57, 99, 57, 94, 6, 31, 75, 31, 137, 157, 29, 105, 160, 165, 101, 65, 94, 97, 93}
3
1836004745
Returns: 234801
422089
86876
{0, 1, 1, 2, 0, 5, 4, 7, 3, 9, 1, 4, 10, 8, 12, 2, 13, 15, 17, 16, 12, 11, 16, 6, 20, 18, 14, 6, 12, 15, 10, 15, 24, 17, 25, 24, 6, 23, 0, 0, 14, 17, 2, 7, 28, 21, 29, 46, 15, 27, 36, 0, 17, 28, 24, 20, 56, 10, 23, 20, 53, 23, 52, 44, 29, 42, 33, 52, 4, 24, 36, 70, 7, 22, 50, 10, 34, 60, 14, 7, 6, 19, 36, 74, 21, 60, 66, 87, 49, 65, 84, 87, 10, 31, 63, 92, 40, 54, 67, 72, 28, 28, 37, 38, 15, 19, 62, 86, 8, 25, 66, 51, 61, 67, 54, 86, 27, 112, 33, 32, 115, 5, 48, 77, 48, 36, 102, 43, 3, 105, 80, 18, 46, 64, 106, 43, 39, 32, 113, 48, 53, 98, 110, 68, 31, 72, 75, 118, 127, 15, 7, 51, 1, 111, 4, 26, 137, 107, 43, 113, 74, 117, 81, 105, 117, 113, 28, 155, 125, 141, 56, 66, 15, 0, 147, 102, 14, 165, 171, 131, 7}
78164
589556703
Returns: 422089
479064
3
{}
1980
1567134618
Returns: 271499
496371
28583
{}
15466
1158129014
Returns: 496371
416166
1047
{0, 1, 0, 1, 3, 0, 1, 3, 4, 2, 7, 11, 7, 3, 13, 14, 10, 8, 16, 5, 14, 11, 7, 1, 16, 0, 9, 5, 15, 26, 5, 31, 18, 32, 9, 34, 28, 23, 31, 12, 5, 41, 15, 26, 33, 6, 45, 15, 20, 42, 0, 3, 33, 32, 20, 6, 3, 56, 38, 3, 28, 21, 33, 63, 47, 16, 15, 30, 17, 6, 9, 30, 32, 16, 16, 30, 14, 46, 41, 50, 52, 77, 51, 51, 25, 31, 51, 52, 33, 89, 72, 17, 52, 81, 22, 87, 90, 62, 29, 22, 56, 90, 98, 3, 101, 17, 91, 83, 87, 2, 4, 83, 80, 6, 114, 24, 40, 111, 82, 88, 102, 94, 22, 45, 89, 51, 43, 53, 28, 109, 88, 40, 22, 80, 97, 26, 129, 50, 26, 78, 140, 69, 137, 42, 88}
786
1618600284
Returns: 415705
400691
262
{0, 1, 0, 2, 3, 3, 3, 5, 2, 5, 1, 1, 2, 11, 11, 10, 9, 12, 2, 19, 3, 19, 0, 19, 15, 16, 15, 11, 17, 4, 5, 25, 21, 11, 25, 34, 13, 15, 0, 28, 13, 35, 5, 34, 20, 4, 37, 0, 4, 14, 32, 6, 30, 24, 49, 35, 40, 8, 38, 22, 45, 19, 0, 41, 54, 61, 19, 3, 14, 36, 33, 68, 67, 9, 6, 48, 9, 15, 6, 75, 69, 12, 39, 14, 57, 61, 75, 80, 41, 26, 58, 42, 30, 21, 44, 7, 14, 20, 1, 10, 33, 72, 59, 30}
52638
1871897694
Returns: 400691
489018
25
{0, 1, 0, 3, 2, 1, 6, 5, 0, 5, 10, 8, 3, 0, 0, 0, 7, 16, 9, 18, 8, 21, 3, 21, 0, 6, 16, 14, 24, 20, 7, 15, 24, 26, 22, 22, 33, 17, 28, 16, 19, 16, 36, 42, 11, 41, 19, 14, 34, 37, 33, 48, 2, 45, 17, 51, 9, 48, 35, 32, 56, 20, 50, 5, 57, 10, 1, 8, 37, 30, 26, 29, 14, 10, 43, 22, 65, 66, 35, 20, 34, 53, 10, 50, 53, 37, 13, 9, 3, 25, 70, 77, 23, 65, 62, 45, 71, 45, 41, 55, 0, 32, 7, 43, 77, 4, 5, 13, 52, 38, 108, 63, 52, 50, 100, 49, 32, 86, 70, 93, 36, 104, 79, 19, 37, 122, 29, 61, 100, 92, 117, 118, 115, 118, 81, 51, 82, 4, 80, 11, 128, 70, 23, 24, 98, 143, 120, 121, 128, 139, 65, 96, 115, 90, 140, 141, 18, 94, 102, 69, 24, 143, 139, 158, 114, 34, 151, 120, 39, 166, 142, 90, 12, 74, 126, 125, 41, 148, 34, 120, 9, 62, 136, 100, 153, 72, 69, 11, 114, 13, 71, 26, 139, 40}
1958
1965167647
Returns: 453926
426852
17679
{0, 1, 0, 2, 2, 1, 4, 7, 8, 6, 9, 10, 4, 5, 9, 11, 16, 1, 15, 15, 9, 2, 20, 14, 5, 6, 8, 1, 16, 16, 11, 22, 19, 11, 7, 13, 20, 8, 37, 25, 10, 24, 27, 34, 31, 14, 19, 6, 10, 20, 7, 28, 16, 9, 44, 16, 16, 38, 46, 48, 6, 27, 62, 41, 23, 9, 29, 16, 20, 29, 4, 67, 0, 42, 73, 7, 16, 11, 35, 3, 80, 6, 46, 0, 73, 34, 37, 0, 22, 58, 26, 30, 40, 49, 39, 15, 13, 10, 57, 1, 22, 37, 23, 10, 85, 74, 69, 43, 10, 90}
61772
1060331720
Returns: 426852
464320
420
{0, 1, 1, 1, 4, 1, 1, 1, 6, 7}
38
355112072
Returns: 441677
412932
246337
{0, 0, 1, 0, 3}
5
1156729687
Returns: 412932
414732
3444
{0, 0, 1, 1, 0, 0, 4, 7, 6, 1, 0, 2, 6, 11, 8, 9, 1, 8, 8, 1, 8, 3, 3, 16, 22, 20, 24, 8, 14, 5, 17, 11, 10, 29, 5, 32, 3, 32, 22, 24, 3, 7, 35, 24, 19, 36, 31, 43, 20, 40, 5, 16, 23, 11, 39, 5, 20, 17, 11, 55, 51, 37, 28, 3, 52, 51, 54, 62, 68, 52, 63, 27, 65, 55, 4, 54, 27, 0, 49, 57, 37, 35, 45, 21, 80, 9, 36, 12, 37, 53, 83, 7, 62, 15, 66, 53, 4, 3, 89, 89, 20, 27, 14, 21, 69, 51, 13, 43, 2, 105, 30, 24, 85, 60, 20, 61, 23, 109, 32, 6, 5, 23, 95, 70, 21, 20, 66, 50, 42, 129, 120, 37, 106, 50, 59, 32, 134, 57, 70, 33, 33, 51, 135, 92, 114, 11, 25, 84, 72, 13, 17, 116, 90, 53, 113, 139, 52, 48, 154, 158, 129, 40, 130, 66}
81439
1412146829
Returns: 414732
428367
828
{}
1
1630156572
Returns: 828
496716
1
{0, 0, 1, 2, 0, 5, 4, 4, 3, 5, 0, 9, 10, 2, 13, 10, 16, 16, 13, 18, 5, 0, 6, 1, 15, 4, 15, 20, 24, 20, 23, 5, 0, 3, 6, 29, 19, 7, 26, 33, 36, 14, 2, 27, 6, 27, 9, 43, 35, 41, 23, 28, 10, 29, 26, 38, 13, 10, 25, 33, 49, 13, 26, 54, 28, 48, 19, 7, 58, 24, 36, 66, 34, 16, 49, 9, 34, 15, 31, 75, 37, 76, 47, 27, 43, 30, 26, 6, 65, 27, 73, 18, 33, 36, 28, 3, 74, 42, 60, 33, 1, 99, 46, 63, 69, 83, 69, 31, 89, 35, 98, 14, 73, 61, 64, 94, 78, 21, 15, 59, 6, 27, 74, 66, 42, 65, 84, 10, 84, 97, 121, 21, 111, 70, 18, 87, 46, 106, 24, 134, 20, 113, 37, 99, 138, 90, 109, 5, 121, 109, 46, 49, 106, 93, 58, 15, 143, 10, 16, 104, 151, 50, 67, 99, 94, 83, 70, 66, 137}
454
428359044
Returns: 1
463777
123
{0, 1, 0, 0, 3, 0, 3, 6, 3, 9, 0, 9, 10, 12, 4, 3, 7, 0, 13, 6, 7, 6, 16, 17, 6, 21, 2, 2, 6, 2, 29, 4, 23, 18, 18, 28, 35, 10, 35, 24, 29, 23, 28, 0, 22, 17, 35, 30, 44, 4, 21, 31, 16, 40, 54, 48, 47, 42, 54, 38}
502
1747998476
Returns: 456170
486570
413432
{}
27767
1619719013
Returns: 486570
483449
269267
{0, 0, 1, 2, 4, 1, 5, 3, 4, 6, 1, 1, 2, 5, 11, 10, 10, 5, 6, 19, 0, 1, 3, 19, 3, 21, 14, 18, 0, 2, 27, 2, 4, 29, 13, 13, 17, 15, 29, 16, 13, 12, 33, 40, 14, 24, 12, 38, 43, 43, 42, 6, 45, 16, 27, 25, 11, 12, 8, 35, 28, 56, 50, 12, 34, 60, 7, 14, 65, 14, 30, 71, 49, 72, 68, 6, 20, 36, 73, 7, 78, 68, 43, 51, 22, 22, 44, 10, 39, 63, 73, 0, 12, 82, 85, 65, 50, 4, 28, 99, 76, 72, 102, 53, 27, 34, 93, 52, 57, 8, 6, 79, 82, 105, 32, 54, 1, 99, 113, 42, 17, 82, 24, 10, 115, 115, 37, 99, 115, 108, 83, 59, 126, 75, 59, 19, 88, 70, 3, 133, 79, 96, 129, 92, 43, 31, 119, 130, 117, 143, 66, 92}
767
1338609926
Returns: 483449
431008
6698
{0, 0, 0, 1, 2, 2, 1, 2, 5, 4, 10, 8, 8, 5, 13, 15, 5, 2, 1, 9, 16, 9, 18, 3, 16, 7, 8, 3, 19, 2, 9, 31, 24, 13, 9, 12, 9, 6, 0, 15, 36, 38, 21, 14, 9, 22, 7, 8, 37, 45, 27, 42, 21, 16, 32, 30, 48, 28, 39, 27, 28, 29, 32, 33, 21, 28, 17, 50, 64, 16, 16, 38, 9, 22, 15, 68, 10, 6, 61, 57, 41, 49, 16, 58, 2, 61, 44, 50, 64, 79, 0, 64, 79, 78, 48, 53, 96, 52, 5, 28, 39}
7
294893691
Returns: 329689
487342
5953
{}
1
1235786895
Returns: 5953
474922
45777
{}
30
1302650274
Returns: 474922
491865
224
{}
272847
816572032
Returns: 491865
474357
1439
{}
2634
1217934295
Returns: 474357
497309
35885
{}
490416
744206205
Returns: 497309
427154
1982
{}
89570
1719867949
Returns: 427154
417685
976
{}
47
1781634630
Returns: 401162
463500
164645
{}
5319
862081975
Returns: 463500
440751
209
{}
457
1065116040
Returns: 432486
498062
247
{0, 0, 1, 3, 3, 3, 1, 7, 3, 8, 6, 10, 11, 6, 12, 10, 14, 5, 4, 17, 6, 4, 7, 1, 12, 3, 6, 15, 17, 18, 11, 5, 27, 11}
14
778528433
Returns: 435974
471302
439905
{0, 1, 0, 3, 0, 4, 1, 2, 7, 5, 1, 10, 4, 5, 14, 10, 14, 8, 7, 2, 5, 2, 0, 14, 1, 23, 9, 24, 5, 12, 16, 8, 23, 21, 21, 9, 20, 22, 1, 24, 22, 21, 22, 43, 21, 21, 8, 17, 33, 8, 33, 49, 36, 32, 26, 21, 17, 1, 21, 44, 10, 6, 3, 22, 37, 41, 8, 7, 52, 67, 8, 40, 12, 20, 60, 3, 56, 31, 52, 69}
467
83972221
Returns: 471302
472635
5
{}
19
1250019702
Returns: 243729
416563
226398
{}
5852
1000938630
Returns: 416563
419997
20928
{0, 0, 2, 3, 4, 3, 6, 4, 8}
3
1410398581
Returns: 231067
453631
55
{}
198
1944446212
Returns: 436310
485588
5157
{}
62
1770758136
Returns: 475564
439961
43
{0, 0, 2, 2, 0, 2, 1, 2, 0, 6, 6, 3, 0, 3, 2, 7, 1, 1, 15, 17, 2, 10, 13, 7, 18, 3, 21, 1, 21, 4, 26, 4, 16, 8, 18, 24, 27, 20, 26, 37, 9, 33, 33, 22, 0, 44, 23, 42, 1, 45, 22, 28, 17, 42, 20, 50, 29, 13, 21, 57, 35, 8, 26, 18, 54, 57, 63, 35, 6, 12, 1, 64, 47, 4, 39, 25, 15, 74, 75, 61, 60, 65, 23, 46, 25, 46}
337
297149889
Returns: 403170
500000
4
{ }
1
47
Returns: 4
500000
123
{ }
123
123123123
Returns: 481114