2016 TCO Round 1A, 500-Pointer (EllysSocks)

James S. Plank

Sat Nov 19 10:11:08 EST 2016
Your temptation here is to solve this with a greedy algorithm. Something like: choosing the best pair of socks, and removing them from the Sock array, and then maybe putting them back and matching them with the socks around them.

Don't give into that temptation, because this problem has a really straightforward dynamic programming solution. First, sort the socks. Now, let's consider the first sock. Either you are going to match that sock with the next one, or you are not going to match it at all. Let's consider both cases:

The better of these two cases will be your answer.

So, what I did was sort the socks and make the sock vector a member of my class. Then, I wrote the following method:

int GD(int index, int npairs)

This method returns the best answer when I need npairs pairs of socks, and I'm ignoring any socks whose indices are less than index. I'll solve getDifference() by returning GD(0,P).

I have two base cases. If npairs is zero, then my answer is zero, because I have not more matches to make. If index is too big, and I don't have enough socks to make even one pair of socks, then I return a large sentinel -- 1,000,000,001.

Otherwise, I have two cases to try:

  1. Matching S[index] with S[index+1], and calling GD(index+2, pairs-1).
  2. Ignoring S[index] and simply calling GD(index+1).
The better of these two is my answer.

Below, I'm going to show you the memoization cache for each of the example problems. I've added and example #5 to the mix too: { 20, 1000, 1050, 1099, 1500, 3000, 3010, 3022, 6000}. This is a nice example to step through by hand if you're having problems. Use the printouts below to help you.


Example 5 - Answer is 401

Socks: 20 1000 1050 1099 1500 3000 3010 3022 6000

Index / Pairs123
0-1-1401
1-1-1401
2-1491500
3-14012978
41015001000000001
51029781000000001
61210000000011000000001
7297810000000011000000001
8-1-1-1

Example 0

Socks: 36 37 41 42 42 84

Index / Pairs12
0-11
1-14
2042
301000000001
4421000000001
5-1-1

Example 1

Socks: 36 37 41 42 42 84

Index / Pairs123
0-1-142
1-1-11000000001
2-1421000000001
3-110000000011000000001
44210000000011000000001
5-1-1-1

Example 2

Socks: 2 2 3 3 4 4 5 5 6 6 7 7 8 8

Index / Pairs1234567
0-1-1-1-1-1-10
1-1-1-1-1-1-11000000001
2-1-1-1-1-101000000001
3-1-1-1-1-110000000011000000001
4-1-1-1-1010000000011000000001
5-1-1-1-1100000000110000000011000000001
6-1-1-10100000000110000000011000000001
7-1-1-11000000001100000000110000000011000000001
8-1-101000000001100000000110000000011000000001
9-1-110000000011000000001100000000110000000011000000001
10-1010000000011000000001100000000110000000011000000001
11-1100000000110000000011000000001100000000110000000011000000001
120100000000110000000011000000001100000000110000000011000000001
13-1-1-1-1-1-1-1

Example 3

Socks: 2 3 3 5 5 7 7 11 11 13 13 17 17 19

Index / Pairs1234567
0-1-1-1-1-1-14
1-1-1-1-1-1-11000000001
2-1-1-1-1-141000000001
3-1-1-1-1-110000000011000000001
4-1-1-1-1410000000011000000001
5-1-1-1-1100000000110000000011000000001
6-1-1-14100000000110000000011000000001
7-1-1-11000000001100000000110000000011000000001
8-1-141000000001100000000110000000011000000001
9-1-110000000011000000001100000000110000000011000000001
10-1410000000011000000001100000000110000000011000000001
11-1100000000110000000011000000001100000000110000000011000000001
122100000000110000000011000000001100000000110000000011000000001
13-1-1-1-1-1-1-1

Example 4

Socks: 7097711 14685971 15198493 20544910 25475624 30574577 39073007 40498239 53612697 81133258 84672537 94092596 103237637 103522060 107063881 113911604 126303054 131752569 133711906 136721027 138749191 147944789 150802600 153380496 156513984 173978710 177512688 182506778 183966551 189375153 196140741 198304613 213794688 219972874 248268555 262522458 275731772 283496852 296707007 310701088 323567404 339840186 359573809 361913171 361931892 368550363 372047868 379821990 404620563 417177802 418932836 444803289 471852627 478582453 479711181 483031419 519074050 522136404 537655880 540721924 545404205 547204602 547914047 551745921 579004999 581869303 609397213 638781100 640439653 647984700 676943010 684602223 708632712 712568903 735241235 746745228 755486970 758242872 764919655 795755685 802611721 809094427 811450930 812852787 826647953 857788837 867128744 867889991 870676136 879609715 884392679 884870761 892462744 902841101 910208077 913778155 944672732 946129058 949333986 967048445

Index / Pairs123456789101112131415161718192021222324252627282930313233343536373839404142
0-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316
1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-113114458
2-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155
3-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11311445813210155
4-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166
5-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1131144581321015513795166
6-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782
7-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-113114458132101551379516616272782
8-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217714459
9-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217714459
10-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821746472617714459
11-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821771445925870453
12-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782174647261771445925870453
13-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782177144592587045328958310
14-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217464726177144592587045328958310
15-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217714459258704532895831031140884
16-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821746472617714459258704532895831031140884
17-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782177144592587045328958310311408841000000001
18-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217464726177144592587045328958310311408841000000001
19-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821771445925870453289583103114088410000000011000000001
20-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782174647261771445925870453289583103114088410000000011000000001
21-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217714459258704532895831031140884100000000110000000011000000001
22-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821746472617714459258704532895831031140884100000000110000000011000000001
23-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782177144592587045328958310311408841000000001100000000110000000011000000001
24-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217464726177144592587045328958310311408841000000001100000000110000000011000000001
25-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821771445925870453289583103114088410000000011000000001100000000110000000011000000001
26-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-19339907128663161321015513795166162727821771445925870453289583103114088410000000011000000001100000000110000000011000000001
27-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217714459258704532895831031140884100000000110000000011000000001100000000110000000011000000001
28-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-193399071286631613210155137951661627278217714459258704532895831031140884100000000110000000011000000001100000000110000000011000000001
29-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-112866316132101551379516616272782177144592587045328958310311408841000000001100000000110000000011000000001100000000110000000011000000001
30-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1933990712866316132101551379516616272782177144592587045328958310311408841000000001100000000110000000011000000001100000000110000000011000000001
31-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1128663161321015513795166162727821771445925870453289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001
32-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-19339907128663161321015513795166162727821771445925870453289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001
33-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-11286631613210155137951661627278217714459258704532895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
34-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-193399071286631613210155137951661627278217714459258704532895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
35-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-19339907128663161321015513795166177144592479857328958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
36-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-187417429339907128663161379516616272782177144592587045328958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
37-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-193399071286631613210155137951661771445924798573289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
38-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1874174293399071286631613795166162727821771445925870453289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
39-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-187417429339907128663161379516617714459247985732895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
40-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1777412287417429339907137951661627278217714459258704532895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
41-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-177741228741742933990713795166177144592479857328958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
42-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1765921377741228741742933990713795166177144592587045328958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
43-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1765921387417429339907137951661771445924798573289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
44-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-17659213777412287417429339907137951661771445925870453289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
45-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-17659213874174293399071379516617714459247985732895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
46-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-176592137774122874174293399071379516617714459258704532895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
47-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-176592138741742933990713795166177144592479857328958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
48-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1759198376592138741742933990713795166177144592587045328958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
49-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-175919837659213874174293399071379516617714459289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
50-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-17591983765921387417429339907137951661771445925870453289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
51-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1759198376592138741742933990713795166177144592895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
52-1-1-1-1-1-1-1-1-1-1-1-1-1-1-16729826759198376592138741742933990713795166177144592895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
53-1-1-1-1-1-1-1-1-1-1-1-1-1-1-17591983765921387417429339907137951661771445928958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
54-1-1-1-1-1-1-1-1-1-1-1-1-1-164827067591983765921387417429339907137951661771445928958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
55-1-1-1-1-1-1-1-1-1-1-1-1-1-175919837659213874174293399071379516617714459289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
56-1-1-1-1-1-1-1-1-1-1-1-1-1648270675919837659213874174293399071379516617714459289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
57-1-1-1-1-1-1-1-1-1-1-1-1-1759198376592138741742933990713795166177144592752791028958310100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
58-1-1-1-1-1-1-1-1-1-1-1-16482706759198376592138741742933990713795166177144592895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
59-1-1-1-1-1-1-1-1-1-1-1-17591983765921387417429339907137951661771445927527910289583101000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
60-1-1-1-1-1-1-1-1-1-1-164827067591983765921387417429339907137951661771445928958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
61-1-1-1-1-1-1-1-1-1-1-175919837659213874174293399071379516617714459275279102895831010000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
62-1-1-1-1-1-1-1-1-1-1648270675919837659213874174293399071379516617714459289583103114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
63-1-1-1-1-1-1-1-1-1-1759198376592138741742933990713795166177144592752791028958310100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
64-1-1-1-1-1-1-1-1-16482706759198376592138741742933990713795166177144592895831031140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
65-1-1-1-1-1-1-1-1-17591983765921387417429339907137951661771445927527910289583101000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
66-1-1-1-1-1-1-1-164827067591983765921387417429339907137951661771445928958310311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
67-1-1-1-1-1-1-1-16482706759198376592138741742933990713795166177144592895831010000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
68-1-1-1-1-1-1-164827067545047759198376592138741742933990713795166177144593114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
69-1-1-1-1-1-1-164827067591983765921387417429339907137951661771445928958310100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
70-1-1-1-1-1-1393619164827067591983765921387417429339907137951661771445931140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
71-1-1-1-1-1-1393619164827067591983874174293399071379516617714459240304891000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
72-1-1-1-1-13570078393619164827067591983874174293399071379516617714459311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
73-1-1-1-1-13570078648270675919838741742933990713795166177144592267233210000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
74-1-1-1-127559023570078648270675919838741742933990713795166177144593114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
75-1-1-1-12755902357007864827067591983874174293399071379516617714459100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
76-1-1-1145632627559023570078648270675919839339907137951661771445931140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
77-1-1-114563263570078648270666767837591983933990713795166177144591000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
78-1-11401857145632635700786482706759198393399071379516617714459311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
79-1-1140185714563263570078648270675919839339907137951661771445910000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
80-1761247140185714563263570078648270675919839339907177144593114088410000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
81-1761247140185714563263570078759198393399071379516617714459100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
82478082761247140185714563263570078759198393399071771445931140884100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
83478082761247145632635700787591983933990713795166177144591000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
84478082761247145632635700787591983933990717714459311408841000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
8547808276124714563263570078759198393399071771445910000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
86478082761247145632635700787591983103783571771445910000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
87478082145632627861453570078759198317714459100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
884780821456326357007875919831037835717714459100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
89478082145632635700787591983177144591000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
904780821456326357007810378357177144591000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
911456326357007875919831771445910000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
9214563263570078103783571771445910000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
931456326357007817714459100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
941456326357007817714459100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
951456326177144591000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
961456326177144591000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
97320492810000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
981771445910000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001100000000110000000011000000001
99-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1