Problem Statement
The time limit for this problem is 4 seconds.
A small group of the best players in the whole league has been pre-selected as those who would deserve to play in an exhibition "all-stars" game.
For simplicity, each of these players has been assigned a positive integer representing their skill level. These are given in the
The entertainment the viewers get from an all-stars game comes from two factors: they want to see an exciting, balanced game, but they also want to see all their favorite players. In this problem we'll try to balance these two goals somehow.
Ideally, we would like to split the selected players into two teams with exactly equal skill. (The skill of a team will, naturally, be calculated simply as the sum of skills of its members.) Of course, this might be impossible to achieve, so we'll want to get as close to this ideal goal as possible.
We can deviate from the ideal goal in two ways: First, we can decide not to invite some of the pre-selected players to the all-stars game. Let U be the sum of skills of the uninvited players. Clearly, the higher U is, the farther we are from the goal of showing all the good players, so we want to keep U small.
Second, when dividing the invited players into the two teams who will face each other, we may be unable to achieve a perfect split. Let D be the non-negative difference between the skills of the two teams. Clearly, the higher D is, the farther we are from the goal of having a balanced match, so we want to keep D small.
In order to balance these two goals, we have chosen a positive integer K and we have decided to minimize the total value of (U + K*D).
Calculate and return the smallest achievable value of (U + K*D) over all ways to invite players to the all-stars game and select the two teams who will play each other.
Definition
- Class:
- HockeyAllStars
- Method:
- split
- Parameters:
- int[], int
- Returns:
- long
- Method signature:
- long split(int[] skill, int K)
- (be sure your method is public)
Constraints
- skill will have between 1 and 26 elements, inclusive.
- Each element of skill will be between 1 and 80,000,000, inclusive.
- K will be between 1 and 1,000,000, inclusive.
Examples
{100, 200, 300, 400, 1000}
47
Returns: 0
It is possible to split these players perfectly: the first four will play against the fifth.
{100}
1
Returns: 100
All mathematically possible ways to invite and split players should be considered valid solutions, even if they don't make much sense in real life. E.g., there can be a perfectly balanced exhibition game with zero players on each side, or an exhibition game in which a non-empty team plays against an empty team. In this case it does not matter whether we invite the only player or not. If we don't, we have U=100 and D=0, if we do, we have U=0 and D=100. In both cases the total badness of the solution is 100.
{100, 200, 300, 1000, 4000, 4010, 400}
2
Returns: 20
The optimal solution is to invite everyone (U = 0) and create two teams with a small skill difference: D = 10.
{100, 200, 300, 1000, 4000, 4010, 400}
1000
Returns: 8010
These are the same players but now K is much bigger. Now the optimal solution is to uninvite the two best players (U = 8010) and then to split the remaining players perfectly (D = 0), as in Example 0.
{47224006, 8391988, 57738621, 74308314, 60890673, 76610215, 46099729, 34551385, 68779119, 51882812, 52669104, 5490676, 56174496, 3175573, 13751392, 84089, 35407528, 64632920, 73375192, 1226181}
1899
Returns: 175241
{30876380, 31909170, 70232057, 68981569, 48195186, 59353898, 32487244, 4464634, 75288849, 50219876, 47439602, 45890889, 74865366, 77189027, 26304436, 32026926, 4735058, 16844270, 44819067, 13146234, 48699377}
463249
Returns: 39435979
{68223646, 72494800, 33934876, 13032362, 30461760, 44944006, 29333810, 63220607, 14783506, 55923194, 47385437, 38428994, 32075750, 74526546, 35109974, 47908113, 71495689, 75884515, 5383447, 64954138, 41903667, 75529437}
6227
Returns: 1120860
{69712563, 29653665, 15292187, 27794651, 50984922, 65149124, 33975703, 74899271, 20025591, 59577420, 2038796, 22856692, 73416108, 11109993, 10013282, 35668352, 68616780, 73398917, 63956112, 58466977, 49067131, 4453565, 35569502}
127377
Returns: 6624368
{42277653, 2984115, 77433000, 32617533, 28368894, 46434550, 57933396, 24698211, 23713244, 63054543, 26665903, 17163265, 13209404, 18342177, 76453270, 46178285, 70786584, 52661755, 14506944, 35818038, 59582024, 60653, 16425003, 55575541}
6
Returns: 282
{2781208, 35466738, 5597579, 18849326, 24317464, 68673581, 65898658, 26997685, 66396816, 70903855, 60879960, 75645856, 76146683, 1340479, 9911364, 23504514, 20208789, 72939858, 45411577, 6266053, 31474227, 8218842, 50832166, 16528644, 2981515}
6
Returns: 18
{7233265, 73531947, 41294168, 32093870, 71791362, 20294364, 73810122, 77813849, 36662996, 76616138, 10831796, 75559089, 65934993, 45998527, 74695084, 7003813, 15380714, 55496059, 56055471, 47478537, 40642778, 75741865, 65666713, 18743785, 8527695, 68165870}
15
Returns: 150
{79999968, 46445568, 78951424, 79999872, 79999984, 79999992, 63222784, 77902848, 79999998, 71611392, 79475712, 79999936, 79967232, 79999999, 79999488, 75805696, 79995904, 79934464, 79999744, 79998976, 79737856, 79983616, 79868928, 79991808, 79999996, 79997952}
1
Returns: 8191
{79999999, 79999744, 79999984, 75805696, 63222784, 79967232, 79998976, 78951424, 79999968, 79475712, 79999872, 79737856, 79999998, 79999992, 71611392, 79868928, 79983616, 79934464, 46445568, 79999996, 79999488, 79999936, 79991808, 79995904, 79997952, 77902848}
999999
Returns: 987956417
{79999992, 79999998, 79999968, 79999984, 79999996, 79999999}
42
Returns: 294
{79737856, 79999968, 79998976, 79999872, 79999999, 79997952, 79999984, 79999996, 79999936, 79868928, 79991808, 79999998, 79995904, 79934464, 79475712, 79999744, 79999992, 79999488, 79983616, 79967232}
309202
Returns: 316313646
{79999488, 79999936, 79999968, 79999999, 79999998, 79999992, 79999872, 79991808, 79983616, 79999996, 79999744, 79997952, 79998976, 79995904, 79999984}
3393
Returns: 80414527
{79999998, 79999996, 79999999}
105262
Returns: 80105258
{79999996, 79999998, 79999936, 79999872, 79999984, 79999999, 79999744, 79999992, 79999488, 79999968}
40
Returns: 1240
{79999488, 79997952, 79934464, 79983616, 79999872, 79868928, 79991808, 79999968, 79999992, 79999996, 79999999, 79999936, 79998976, 79995904, 79999984, 79967232, 79999744, 79999998}
50
Returns: 25550
{79999998, 79999936, 79999996, 79999968, 79999992, 79999984, 79999999}
659
Returns: 80004549
{79999999, 79999936, 79999992, 79999998, 79999984, 79999968, 79999996}
5
Returns: 79999971
{79999488, 79999992, 79999968, 75805696, 79737856, 79868928, 79999936, 79983616, 79999744, 79999998, 79995904, 79999999, 79999872, 79967232, 79998976, 79934464, 79999984, 79475712, 79991808, 79999996, 77902848, 79997952, 78951424}
491560
Returns: 643060696
{79991808, 79999984, 79999968, 79737856, 79995904, 79983616, 78951424, 79999488, 77902848, 79868928, 79475712, 79999996, 79999999, 79999992, 79997952, 71611392, 79999998, 75805696, 79934464, 79999744, 79998976, 79999872, 79999936, 79967232}
142
Returns: 581490
{79967232, 79991808, 79999936, 77902848, 79999744, 79998976, 79934464, 79999968, 79999996, 79999984, 79983616, 78951424, 79995904, 79737856, 75805696, 79997952, 79999872, 79868928, 79999999, 79999998, 79475712, 79999488, 79999992}
76
Returns: 75961268
{79999992, 79999998, 79999996, 79737856, 79997952, 79868928, 79967232, 77902848, 63222784, 79999984, 79999936, 79934464, 75805696, 79991808, 79999744, 79999872, 79999488, 79999999, 79475712, 79999968, 79983616, 79995904, 71611392, 79998976, 78951424}
31
Returns: 63349729
{71611392, 79999999, 79999996, 79999998, 79475712, 79934464, 79967232, 79999936, 79995904, 77902848, 79868928, 79999872, 79999968, 79737856, 79999992, 75805696, 79997952, 79983616, 79999488, 78951424, 79998976, 79999744, 63222784, 79999984, 79991808}
512
Returns: 65319424
{46445568, 79999968, 63222784, 79999744, 79999872, 79995904, 79967232, 71611392, 79868928, 79998976, 78951424, 79737856, 79991808, 79997952, 79999992, 79999984, 79999488, 79999996, 79999936, 79934464, 79983616, 79475712, 79999998, 75805696, 79999999, 77902848}
572
Returns: 4685252
{71611392, 79999936, 79999996, 78951424, 79999488, 79999992, 79999984, 75805696, 46445568, 79997952, 79475712, 79934464, 79999998, 79999744, 79737856, 79991808, 63222784, 79999872, 79868928, 79999999, 79998976, 77902848, 79983616, 79999968, 79995904, 79967232}
8
Returns: 65528
{79999999, 79475712, 79934464, 79999996, 79967232, 79991808, 79999872, 79999998, 71611392, 63222784, 79997952, 79998976, 79868928, 79999488, 78951424, 79999992, 79995904, 75805696, 79737856, 79983616, 79999984, 79999744, 79999968, 79999936, 77902848}
374
Returns: 64754314
{63800936}
88202
Returns: 63800936
{862457, 3498, 27325}
227
Returns: 893280
{1, 3501}
3852
Returns: 3502
{114, 242, 901, 2535802}
69308
Returns: 2537059
{5549488, 64351782, 36621802, 1115959, 7432372, 29833314}
1039
Returns: 144904717
{4936960, 32411169, 77402675, 55953366}
113026
Returns: 170704170
{5779, 35508421}
942535
Returns: 35514200
{34863000, 6972600, 8367120, 60661620, 72515040, 9064380}
9319
Returns: 192443760
{3499004, 38949419, 3980160, 24745507, 56975242, 26462480}
26922
Returns: 154611812
{17704040, 50271428, 49168429, 37695146, 58587169}
14
Returns: 29189776
{8175405, 436975, 421085, 643545, 3011155}
179060
Returns: 12688165
{39231, 134, 1550, 5377695, 248154, 137}
190
Returns: 5666901
{191700, 6360606, 3834, 225780, 69629700}
27
Returns: 76411620
{60587296}
27
Returns: 60587296
{13141323}
215696
Returns: 13141323
{78486056, 58642105}
243574
Returns: 137128161
{62, 28349210, 4, 4962, 48796811, 888, 52918818, 106, 2204395, 244631, 7, 44016, 29259275, 3046428, 372454, 19714, 32856, 504, 373410, 1, 13, 11663, 88893, 16, 31730993}
751
Returns: 28370316
{62342947, 18998415, 78245324, 23220285, 4784786, 40248494, 59528367, 53195562, 25471949, 13087797, 39263391, 11821236}
12680
Returns: 18998415
{18124551, 7087608, 65253753, 77582178, 44214183, 68500827, 79024851, 76003857, 36896256, 8191161, 34125363, 15740820, 64773333, 13317525, 68222466, 17949339, 31881519, 76683510, 42772923, 79345602, 74629008, 7316514}
40
Returns: 56520
{55123025, 4067330, 33501955, 14449725, 53517500, 6100995, 749245, 78670725, 5672855, 28792415, 75138570, 8669835, 42921035, 78991830, 43991385, 51590870, 48807960, 67967225, 55123025, 41529580, 25795435, 54373780, 7385415, 15091935}
9
Returns: 0
{24896614, 46053948, 28574937, 32596791, 69565397, 45738166, 15336922, 60322859, 53625716, 16288448, 55690452, 24043755, 37318155, 315666, 25731238}
4475
Returns: 9648100
{16557527, 65344880, 35169346, 67964642, 25167687, 29106541, 36782196, 65076528, 27428944, 73095917}
1683
Returns: 62612880
{256745, 679112, 4919037, 3, 26337657, 61921, 58574686, 4134, 21422, 181, 360, 45377932, 45538, 14493, 176, 14, 55854199, 1616404, 833387}
655664
Returns: 72394899
{3, 722, 114096, 29843720, 585905, 2, 10878, 14, 30, 1141, 1095148, 42, 144011, 60346, 54742, 12727, 51, 6470198, 10758}
56149
Returns: 37995760
{76257312, 69127968, 9724032, 32442768, 71458848, 35561952, 61619472, 27509904, 49560288, 79313280, 4595520, 33556416, 54630000, 12124608, 58810224, 9606000}
458
Returns: 2726016
{8171214, 93922, 1033142, 939220, 1033142, 3005504, 6011008, 93922, 1408830, 845298, 1314908, 3193348, 1314908, 1690596, 14463988, 6762384}
17591
Returns: 93922
{36973289, 64394380, 19435605, 65424930, 67700879, 64692187, 59166485, 47517550, 62527849, 2854045, 26309108, 77150965, 38573016}
14688
Returns: 41952521
{2173305, 818, 46, 9318696, 25705470, 960, 76, 100, 2705, 281026, 750776, 976827, 12157327, 4237388, 877824, 59893, 121000, 19385, 535, 83, 11183163}
1867
Returns: 750905
{5142423, 35961, 30842551, 59935, 119870, 17956526, 539415, 3943723}
9
Returns: 27402282
{5131188, 35918316, 46180692, 5131188, 15393564, 15393564, 30787128, 35918316, 35918316, 15393564, 46180692, 30787128, 5131188, 66705444, 10262376, 20524752, 10262376, 66705444, 41049504, 51311880, 30787128, 5131188, 71836632, 71836632, 51311880}
1
Returns: 0
{5, 11900, 1399, 1949174, 1314, 99, 74888244}
25901
Returns: 76852135
{1366939, 25626008, 24005627, 40893280, 67540871, 21117656, 1522386, 38922494, 40618209, 72396146, 19132424, 57204060, 38677434, 23080979, 55049011}
2112
Returns: 130944
{15914080, 29852016, 76807296, 54684976, 72295392, 7309984, 3497600, 42355936, 4144656, 44944160, 48161952, 8114432, 69864560, 20863184, 8271824, 24150928, 40117472, 14445088, 29694624, 51292304, 57972720, 51869408, 33122272, 43090432, 58182576, 35972816}
18267
Returns: 4144656
{13040590, 59906440, 59599510, 17014940, 38661375, 10030315, 76665605, 14201415, 48487070, 36320050, 4210450, 19328720, 34820815, 55676315, 1200175, 63085920, 9444000, 14893975, 39932380, 51442255, 23767400, 45575170, 38897475, 2502660}
169
Returns: 0
{68464215, 72398940, 40921140, 8656395, 18099735, 39347250, 11804175, 50364480, 25969185, 48003645, 11804175, 13378065, 64529490, 47216700, 43281975, 16525845, 70825050, 3934725, 1573890, 24395295, 72398940, 24395295, 52725315, 9443340, 55873095, 38560305}
38471
Returns: 0
{28526792, 56472346, 22096270, 20823082, 74693696, 39145918, 59387762, 44303252, 31128524, 22539118, 67497416, 70385154, 74186266, 75385646, 52394454, 50226344, 77350784, 17068100, 22040914, 33693352, 32088028, 31377626, 31082394, 35040348, 78919204}
3
Returns: 27678
{75829684, 74299220, 26145042, 12720884, 62747348, 61392968, 79752316, 72810272, 20638382, 33891554, 54315645, 27356260, 10507711, 39125812, 51630746, 59089034, 21980952, 42048627, 54371095, 75696870, 32367959, 14248120, 55829144, 69417, 8905424, 62009120}
59768
Returns: 1683153
{96, 588580, 2681510, 2645, 7507726, 16191590, 53, 7278330, 239, 748, 987, 647604, 17, 53996632, 51044969, 2, 350, 616, 3, 55, 5948, 3, 595974, 20, 63968}
26
Returns: 725942
{12378151, 55689585, 53094828, 20741402, 7220890, 77051196, 2826620, 24254609, 52640787, 12445574, 3107477, 4264294, 18467101, 39464381, 13001770, 30932331, 47522979, 25678191, 17931472, 32700910, 23981569, 41151043, 25389180, 61822551}
1159
Returns: 54473
{300873, 106889, 13, 16, 1107902, 504150, 30463463, 27915, 151826, 3339388, 1797775, 613, 10561013, 558, 23572, 46241, 2335026, 49522058, 254171, 1, 1, 77333953, 5062608, 13058, 13841251, 186}
494
Returns: 0
{71414674, 31974011, 11647926, 68293716, 45426408, 79296803, 38977834, 23213612, 37971072, 63316684, 76040927, 50454281, 59208332, 22490678, 79584850, 45353428, 66756459, 44852310, 47078851, 14953020, 8067079, 65749721, 4975394, 28045390, 65842093, 31462902}
139597
Returns: 139597
{8405064, 1605000, 14124, 956580, 249096, 208008, 1284, 487920, 1284, 21828, 17976, 10069128, 5096196, 525156, 1284, 32100, 14124, 259368, 6420, 57780, 86028, 889812, 6420, 97584, 14124, 2564148}
62294
Returns: 1284
{3472388, 2142771, 3, 6487014, 1021852, 1017, 28202418, 10, 115, 2, 921151, 19, 5136, 866590, 90, 244, 600442, 6503, 5655836, 340, 286896, 6583, 2008, 472745, 687}
2
Returns: 12503952
{17751574, 18469752, 3561329, 69692719, 34660668, 59643800, 2420704, 2248082, 5829979, 24089181, 53204146, 34949344, 63491671, 28975084, 17218954, 557190, 7549481, 72924929, 32331567, 27545818, 72844731, 74488582, 24087769, 74826287, 52545835, 18269285}
851679
Returns: 3272383
{77889, 77889, 55976228, 129815, 155778, 1557780, 15551837, 155778, 1064483, 2518411, 597149, 181741, 46993030, 389445, 25963, 25963, 752927, 25028332, 2103003, 25963, 752927, 78512112, 25963, 155778, 31181563}
66538
Returns: 25963
{54003122, 79987125, 78757835, 54792928, 52177583, 76282394, 36753527, 72643386, 27437299, 63153112, 4985859, 71063189, 4115714, 12474854, 29092494, 42456071, 67500121, 53505928, 13701311, 57027683, 13596890, 7919794, 61119244, 9686986, 74819828}
571
Returns: 5139
{34844994, 1819322, 29338892, 46857114, 35184134, 55529252, 32606670, 39149884, 45972615, 63814661, 49766060, 13236306, 14222547, 37387450, 73212121, 39895445, 21360350, 15396956, 28471897, 78358844, 78274059, 60571498, 55917075}
85216
Returns: 0
{22634380, 26930855, 3626530, 51825825, 11090955, 30510790, 28964500, 66251740, 66357465, 63922725, 44378895, 79800365, 27779545, 34147690, 18253625, 51756480, 19144530, 78148095, 922740, 57203925, 52972950, 33077330, 18579495, 33352565}
94172
Returns: 1393600
{22361028, 39453620, 4381777, 12325282, 64662284, 8427850, 751449, 69710294, 77860620, 2373295, 27066824, 78027576, 45157017, 67358521, 26196982, 68001627, 35696120, 59672879, 48735056, 66732317, 59620231, 52972609, 16331815, 12253925, 27719892}
3
Returns: 18
{437, 19, 1776999, 12230869, 3247715, 3550862, 14236, 67171, 325199, 65, 5451010, 3, 1280138, 407188, 30, 1, 2943379, 165156, 12792, 55, 1837, 1074, 7134, 3, 100}
247918
Returns: 1108
{34243444, 49288, 2253512, 461368, 35552, 9399868, 17776, 347036, 404, 1500052, 8080, 388648, 10614696, 209272, 808, 8888, 25979624, 545804, 22220, 404, 216544, 29088, 404, 56560, 2828}
3605
Returns: 9400272
{27037308, 21473269, 18431633, 33534710, 18517851, 71237140, 62443632, 64048167, 41482410, 20354425, 64056649, 22198530, 7964276, 45410870, 13416518, 6443088, 73726530, 61171585, 71001966, 392241, 58646600, 73722480, 55034826, 19284370}
1
Returns: 14
{417811, 32, 520, 2265735, 29, 223, 1170608, 67, 241, 1509990, 330830, 13382, 9, 1103894, 102, 4, 972685, 879, 25, 101, 1087, 47271, 3377}
258448
Returns: 0
{48587869, 38232851, 70760657, 22691795, 31578306, 56585552, 10848751, 46220535, 11026775, 73379632, 38237702, 66854308, 72386341, 47956769, 22023000, 71813855, 24325696, 77110463, 46827810, 1754097, 5727932, 67460095, 22834163, 53045323, 67931002, 25033523}
140
Returns: 1400
{79398564, 37814373, 74114590, 70744099, 26562564, 69178134, 44915736, 27419509, 35472209, 10860607, 47171119, 40681350, 30723390, 30347509, 76327832, 6276009, 3737066, 33301235, 57932362, 21107302, 52185913, 35018546, 56368099, 61060133, 43591767}
3314
Returns: 3314
{76, 12256356, 192, 12392, 60736, 14355840, 100, 46719904, 13356, 10467504, 40, 5235096, 380, 4176, 1164, 364, 1462124, 6340960, 40812, 6301776, 1480, 4, 1967072}
138
Returns: 7776336
{391896, 1959480, 26126400, 27302088, 1175688, 6531600, 914424, 914424, 33703056, 29653464, 17504688, 1959480, 5355912, 130632, 10581192, 1567584, 1828848, 27432720, 914424, 130632, 22729968, 261264, 51730272, 391896, 65838528, 261264}
486172
Returns: 0
{28366679, 10461735, 10265995, 27896674, 11449159, 77673954, 3435669, 68272098, 12950180, 54087134, 31315580, 56458557, 66310909, 58311567, 3493446, 16937472, 13863041, 55653712, 27279741, 77219685, 228672, 63852373, 24291179, 8258815}
210
Returns: 18900
{54, 54579, 30895313, 112788, 23058, 4706, 28089, 62807976, 883, 10, 108174, 29, 27034212, 24559108, 21895260, 30, 14, 295, 463896, 9570853, 14, 6574, 3920788, 33256534, 30, 226}
20954
Returns: 5005
{1832, 40991, 7117320, 230832, 13184446, 7328, 916, 46258, 333653, 2290, 30074341, 229, 1374, 21938429, 3253861, 5496, 50838, 214573, 99615, 29690537, 891268, 458, 50328933}
114
Returns: 10371410
{70950026, 48990079, 36534433, 74995792, 58699460, 60388580, 49258061, 72763914, 4330740, 53056761, 22432759, 59104398, 19175240, 40536730, 12795151, 15219354, 52048689, 67897014, 19492963, 56347741, 15539498, 26820056, 35494579, 56410001, 57066648}
1871
Returns: 9355
{112251, 3743451, 1464006, 45739095, 50504739, 25076445, 76100925, 39136482, 19546566, 2924136, 1020, 1404540, 270912, 24939, 2295, 765, 12003921, 1530, 3654405, 1071, 255, 8470998, 1071}
410
Returns: 0
{125, 18034, 441444, 26504363, 154819, 359871, 68, 1040004, 616, 29383, 462050, 1493, 1380, 27, 3857, 2652, 10, 156518, 2744123, 1998, 24339599, 1782707, 251414}
38589
Returns: 653
{218880, 5106060, 37620, 3420, 10260, 3420, 3334500, 1296180, 6840, 10260, 20520, 18129420, 41040, 338580, 32069340, 892620, 160740, 6792120, 3420, 23940, 47880, 30923640, 742140}
31
Returns: 0
{25, 18870903, 318, 62004342, 29126, 7907495, 34583001, 7, 6, 30, 15, 117, 78645499, 358, 2539511, 35152, 2012058, 53492, 58837195, 38, 2801364, 382, 1650314, 1802737}
149
Returns: 1758647
{19874410, 5742664, 2476156, 1675294, 17755594, 10510, 313198, 180772, 48346, 12612, 662130, 69366, 14714, 6194594, 92488, 7829950, 54652, 28719626, 4204, 3169816, 38359398, 8408, 14541636, 25516178, 14714}
855176
Returns: 10510
{61032251, 48482448, 21501501, 47420765, 46197732, 45119914, 34945183, 37878526, 79238985, 116172, 848701, 48124251, 28294336, 69745151, 53387488, 45897621, 17348352, 41602484, 68109062, 65085363, 51312527, 76515397, 28778386, 79574593, 79000187}
2125
Returns: 0
{27769912, 18543, 3921148, 944696, 413082, 12, 3368821, 11822, 35394678, 32, 3, 9962, 1728936, 36715571, 85684, 229014, 1, 899646, 50571, 53540825, 32, 412831, 7651282}
32133
Returns: 95658
{8680, 829646, 144334, 321, 1436539, 14, 14627, 28279348, 1467, 1, 1222835, 413, 2, 245, 58, 21, 5384269, 2841, 52287, 11, 177153, 34307075, 3, 3970954, 7, 9}
40
Returns: 205302
{16915989, 9289804, 9782497, 27142308, 39111158, 29372280, 37893834, 41745704, 14263198, 6050260, 17572616, 59672970, 50249118, 49310928, 26600081, 54495164, 64875135, 34401298, 66216101, 47365334, 54210855, 1823115, 13622441, 79663098}
17
Returns: 238
{261029, 80, 9169343, 249934, 108, 8658999, 1, 16014977, 946, 2105048, 52, 5978540, 293672, 6, 1, 1, 27348, 31315869, 2817070, 11743, 34854, 53, 21}
610
Returns: 4859032
{1, 73, 26494, 290486, 47393949, 2637, 1782, 76, 54777872, 620, 268388, 32, 964586, 9, 55277358, 122227, 387, 1, 29712, 58194, 14, 6554, 2486, 401571}
3438
Returns: 47420453
{33963, 5, 11551, 7, 139, 42200142, 13999620, 15028, 89206, 236, 8859, 897351, 4961193, 135, 48016, 44143, 11, 1, 1, 3, 52039, 906, 10497284, 57, 13450, 543752}
83658
Returns: 42200142
{73495662, 43219655, 6387051, 48365193, 18218531, 30326196, 77908683, 28353082, 74297479, 50810276, 9538242, 2788448, 54820405, 68148579, 57888253, 34694505, 42793332, 17296162, 75248123, 29104307, 67237645, 55738443, 36215566, 77486612, 13193389, 645073}
164028
Returns: 984168
{10, 20, 147, 147, 1000, 1001}
100
Returns: 130
Here the optimal solution is a trade-off: we cut the two weakest players (U = 10+20 = 30) and then we form two almost-equal teams with D = 1. (One is 147+1000 and the other 147+1001.)
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
1000000
Returns: 0
{80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000, 80000000}
1
Returns: 80000000
{57957856, 57407462, 27358346, 27077549, 57824271, 57704990, 27383666, 27140781, 27252710, 57771687, 27007590, 27181464, 27023845, 57752372, 57882281, 27109715, 27008907, 27546636, 27215851, 27240877, 57618044, 26841576, 27111765, 27152055, 27265630}
54490
Returns: 0
{57348124, 62568799, 57352633, 57279596, 62396580, 62404100, 57984199, 57328567, 56983229, 62740036, 62211879, 57654062, 62788509, 57741060, 57333903, 56848247, 62916204, 57217794, 57464501, 62677711, 62438069, 62822893, 62571135}
639
Returns: 0
{50244715, 31790743, 31640470, 31639563, 50942729, 50559573, 50757107, 50998159, 31830169, 32165673, 50861029, 31690822, 51067648, 50896858, 31731329, 31943244, 31590045, 31615531, 50690392, 31783433, 31353779, 31912325, 51074743, 31655495, 31919796, 31830536}
354
Returns: 0
{71131752, 70479314, 69787172, 70627199, 64870518, 64845565, 64380075, 64251200, 70293999, 70511997, 70164929, 65085461, 64466503, 64494991, 64910883, 70923701, 64366326, 70773467, 64637059, 70475952, 64431086, 64621416, 70191601}
3712
Returns: 0
{6366364, 2976677, 2846223, 2950657, 6254235, 6411201, 6258364, 2947810, 6346919, 2932942, 3037680, 3027817, 2953157, 2988054, 3008612, 2922801, 2799435, 3047957, 2937645, 6240105, 6261095, 3016831, 3034902, 6335629, 3044712}
21
Returns: 0
{23990919, 24362649, 24592129, 24264651, 23989654, 59085656, 58609447, 58907836, 24378509, 24091049, 59149670, 24534730, 24157606, 24063525, 24261135, 24292838, 58516541, 24315046, 58956176, 59068811, 24318582, 24337134, 24204827, 24139154}
91374
Returns: 0
{9386512, 9534984, 9524748, 9667714, 9481487, 21893080, 9496510, 9453014, 9620553, 9585171, 21947360, 21728120, 21739427, 9668669, 9505154, 21760710, 9584192, 9437746, 9758914, 9536106, 9574408, 21788051, 21959134}
1820
Returns: 0
{56113788, 42995939, 43414963, 43298776, 43016108, 56016988, 43177893, 43226430, 43701108, 56218869, 56054052, 56547244, 43235086, 43085386, 56385717, 56197022, 56027199, 55864319, 43216975, 42956190, 56193542, 43090392, 43203494}
88
Returns: 0
{29768331, 29646664, 18486089, 18405438, 29826004, 29115868, 18628541, 18729384, 29622024, 18647192, 29835059, 29791773, 18433644, 18434509, 29640555, 29781762, 18392777, 18586249, 18642533, 29784090, 18603516, 18460558, 18644668, 18454923, 18529410, 18732699}
2465
Returns: 0
{17164399, 17024977, 18643079, 17115545, 16999111, 17367537, 18506730, 17251342, 16996610, 18726091, 18484782, 17107039, 17190084, 18718444, 18693835, 18786163, 17036327, 18602965, 18738713, 18736770, 16980476, 18837135, 17241260}
11
Returns: 0
{39649516, 23443102, 64436001, 58884082, 68841855, 55991226, 8374185, 78424865, 79658308, 2998796, 79553298, 26875735, 49357361, 1615169, 69529680, 43664697, 59300198, 16045244, 51547339, 78183458, 29315940, 34401059, 26794336, 53431977, 34391423, 2472906 }
1
Returns: 24
{44289384, 46930887, 1692778, 34636916, 37747794, 24238336, 79885387, 49760493, 36516650, 69641422, 65202363, 70490028, 63368691, 62520060, 44897764, 47513927, 5180541, 20383427, 64089173, 23455737, 35005212, 41595369, 54702568, 46956430, 16465783, 61021531 }
34567
Returns: 1140711
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432 }
447234
Returns: 447234
{46078705, 25754108, 22546393, 29118330, 60137366, 59932169, 49957932, 33226917, 75669847, 46937972, 76032868, 57206980, 68706223, 3638549, 52567592, 43488164, 4776169, 48126551, 21950427, 72516190, 66542624, 49040635, 61604920, 40427944, 74719310, 38269862 }
10000
Returns: 130000
{649, 70, 266, 659, 979, 169, 671, 686, 842, 424, 265, 540, 1133, 70, 762, 927, 432, 760, 1183, 605, 653, 788, 579, 457, 334, 328 }
666
Returns: 169
{79999999, 79999998, 79999996, 79999992, 79999984, 79999968, 79999936, 79999872, 79999744, 79999488, 79998976, 79997952, 79995904, 79991808, 79983616, 79967232, 79934464, 79868928, 79737856, 79475712, 78951424, 77902848, 75805696, 71611392, 63222784, 46445568 }
1000000
Returns: 987956672