Statistics

Problem Statement for "KnapsackTweak"

Problem Statement

Time limit is 4 seconds.


There is a collection of items for sale, their prices are given in the int[] items.

We would love to have a subset of items such that its total price is exactly target.

We are allowed to tweak the prices of items. The smaller the maximum change, the better. The new prices must be integers but they may be negative.

Find and return the smallest non-negative X with the following property: it is possible to adjust the price of each item by at most X in such a way that there will be a subset of items with sum exactly equal to target.

Definition

Class:
KnapsackTweak
Method:
smallest
Parameters:
int[], int
Returns:
int
Method signature:
int smallest(int[] items, int target)
(be sure your method is public)

Constraints

  • items will contain between 1 and 50 elements, inclusive.
  • Each element of items will be between 1 and 10^5, inclusive.
  • target will be between 1 and 10^5, inclusive.

Examples

  1. {11, 21, 31, 41, 51}

    150

    Returns: 1

    The best we can do is make all items one cheaper.

  2. {11, 21, 31, 41, 51}

    154

    Returns: 1

    The best we can do is make one item cheaper by 1. Or three items cheaper by 1 and the other two more expensive by 1.

  3. {11, 21, 31, 41, 51}

    73

    Returns: 0

    We can reach the target using the current prices (11 + 21 + 41) so no tweaking is needed.

  4. {100000, 99999, 99997, 99998}

    1

    Returns: 99996

  5. {100, 100, 100, 100, 100000}

    383

    Returns: 5

  6. {10001, 9992, 10003, 10007, 10004, 10008, 10000, 9998, 10006, 10002, 10002, 10009, 9991, 10003, 9990, 9993, 9990, 9998, 10005, 10007, 9990, 10000, 10008, 10003, 9997, 87, 96, 96, 91, 94, 87, 81, 97, 91, 91, 99, 90, 97, 98, 86, 87, 81, 84, 90, 83, 91, 98, 92, 96, 97}

    92000

    Returns: 0

  7. {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000}

    100000

    Returns: 0

  8. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 200, 100, 200, 300, 200, 300, 200, 200, 300, 200, 200, 300, 100, 200, 300, 100, 100, 100, 200, 200}

    90514

    Returns: 1

  9. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 200, 100, 200, 300, 200, 300, 200, 200, 300, 200, 200, 300, 100, 200, 300, 100, 100, 100, 200, 200}

    90515

    Returns: 2

  10. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 200, 100, 200, 300, 200, 300, 200, 200, 300, 200, 200, 300, 100, 200, 300, 100, 100, 100, 200, 200}

    90916

    Returns: 1

  11. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 200, 100, 200, 300, 200, 300, 200, 200, 300, 200, 200, 300, 100, 200, 300, 100, 100, 100, 200, 200}

    90917

    Returns: 2

  12. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 200, 100, 200, 300, 200, 300, 200, 200, 300, 200, 200, 300, 100, 200, 300, 100, 100, 100, 200, 200}

    90950

    Returns: 4

  13. {99000, 99001, 99002, 99003, 99004}

    100000

    Returns: 996

  14. {66695, 66658, 66705, 66720, 66708, 66723, 66693, 66682, 66715, 66699, 66700, 66728, 66655, 66703, 66734, 66653, 66663, 66650, 66683, 66711, 66742, 66719, 66651, 66690, 66722, 66704, 66679, 66680, 66716, 66715, 66695, 66706, 66680, 66654, 66721, 66697, 66741, 66738, 66695, 66726, 66693, 66721, 66723, 66747, 66675, 66680, 66750, 66743, 66654, 66666}

    100000

    Returns: 16651

  15. {75035, 74998, 75045, 75060, 75048, 75063, 75033, 75022, 75055, 75039, 75040, 75068, 74995, 75091, 75043, 75074, 74993, 75003, 74990, 75023, 75091, 75051, 75082, 75059, 74991, 75094, 75030, 75062, 75044, 75019, 75020, 75056, 75055, 75035, 75046, 75020, 74994, 75061, 75037, 75081, 75078, 75035, 75066, 75033, 75061, 75063, 75087, 75015, 75020, 75090}

    100000

    Returns: 24906

  16. {74935, 74898, 74945, 74960, 74948, 74963, 74933, 74922, 74955, 74939, 74940, 74968, 74895, 74991, 74943, 74974, 74893, 74903, 74890, 74923, 74991, 74951, 74982, 74959, 74891, 74994, 74930, 74962, 74944, 74919, 74920, 74956, 74955, 74935, 74946, 74920, 74894, 74961, 74937, 74981, 74978, 74935, 74966, 74933, 74961, 74963, 74987, 74915, 74920, 74990}

    100000

    Returns: 24891

  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, 1, 1, 100000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    100000

    Returns: 0

  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, 1, 1, 1, 100000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    50000

    Returns: 1001

  19. {2, 8, 70}

    50

    Returns: 10

    The best solution is to tweak all three prices: to {-8, -2, 60}.

  20. {2, 8, 70}

    30

    Returns: 10

  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, 1, 1, 1, 1, 100000, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    30000

    Returns: 612

  22. {82944, 69120, 85248, 50688, 39168, 76032, 57600, 59904, 92160, 6912, 62208, 99072, 4608, 16128, 2304, 39168, 71424, 80640, 2304, 48384, 85248, 64512, 34560, 36864, 78336, 76032, 52992, 66816, 36864, 6912, 82944, 55296, 52992, 89856, 50688, 82944, 85248, 29952, 36864, 6912, 20736, 50688, 16128, 55296, 87552, 57600, 76032, 80640}

    33140

    Returns: 177

  23. {60357, 39391, 84898, 19855, 75097, 63635, 51612, 43076, 47146, 64339, 96008, 7238, 87219, 56276, 71280, 46904, 93610, 39820, 20537, 37323, 68464, 87483, 45628, 26895, 80003, 2739, 30701, 98582, 14927, 13453, 47905, 92147, 98560, 85888, 78518, 65890, 5984, 47762, 93170, 85041, 56771, 4015, 43802, 38093, 62359, 77792, 33165, 31845, 84678, 35816}

    16762

    Returns: 159

  24. {93330, 56370, 86410, 64290, 17710, 43730, 72740, 80, 20060, 67850, 11010, 60500, 3400, 43300, 6840, 23010, 29690, 83840, 80450, 32960, 81060, 86560, 74320, 92350, 92960, 1640, 12100, 28700, 24670, 89040, 55440, 7650, 38430, 10040, 62060, 20180, 3640, 14520, 49600, 8830, 89770, 50410, 39180, 87640, 24780, 90110, 94990, 44760, 93530, 13230}

    73789

    Returns: 1

  25. {55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228, 55228}

    12214

    Returns: 43014

  26. {42294, 70490, 98686, 14098, 56392, 84588, 98686, 42294, 42294, 28196, 42294, 28196, 56392, 98686, 84588, 98686, 98686, 42294, 56392, 98686, 56392, 42294, 98686, 84588, 14098, 28196, 70490, 56392, 14098, 14098, 56392, 98686, 56392, 70490, 56392, 70490, 98686, 98686, 42294, 42294, 14098, 42294, 14098, 28196, 56392}

    44127

    Returns: 611

  27. {60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686, 60686}

    17369

    Returns: 43317

  28. {54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595, 54595}

    73281

    Returns: 17955

  29. {88790, 34008, 81874, 76206, 70668, 99970, 97578, 45708, 53924, 58162, 60996, 80184, 82004, 72436, 95940, 37518, 84942, 55536, 55328, 45318, 67938, 46774, 46462, 72020, 44018, 77506, 52260, 2418, 20748, 34788, 5226, 63882, 99944, 45656, 95992, 10790, 46774, 82368, 62088, 13234, 10270, 90168, 35646, 46566, 78702}

    7735

    Returns: 46

  30. {74571, 85827, 94269, 85827, 94269, 22512, 42210, 36582, 5628, 98490, 90048, 59094, 26733, 29547, 53466, 14070, 9849, 54873, 8442, 1407, 46431, 63315, 35175, 39396, 67536, 67536, 25326, 36582, 81606, 7035, 54873, 54873, 75978, 21105, 77385, 75978, 63315, 90048, 46431, 8442, 88641, 42210, 49245, 73164, 11256, 5628, 71757, 35175, 75978, 66129}

    68184

    Returns: 81

  31. {66654, 86748, 13326, 12870, 93030, 52458, 12654, 31902, 40254, 44718, 82992, 92928, 38826, 58338, 1170, 22452, 2334, 49374, 41880, 73272, 92610, 42126, 65358, 78738, 7542, 81540, 63990, 67776, 1476, 21492, 4044, 61140, 9558, 42996, 666, 6870, 9690, 75390, 91236, 37548, 17652, 54516, 77748, 68394, 7434, 12834, 59778, 61188, 10230, 86856}

    60741

    Returns: 1

  32. {13641, 40923, 95487, 54564, 40923, 13641, 81846, 54564, 54564, 27282, 40923, 13641, 13641, 68205, 81846, 68205, 95487, 27282, 27282, 68205, 27282, 13641, 13641, 54564, 54564, 54564, 81846, 54564, 68205, 81846, 27282, 27282, 95487, 81846, 81846, 81846, 95487, 54564, 68205, 81846, 54564, 40923, 81846, 95487, 81846, 27282, 13641, 13641, 68205, 27282}

    95813

    Returns: 47

  33. {20214, 18090, 76464, 18774, 90270, 43092, 84060, 88884, 61686, 80730, 71982, 90324, 85680, 3474, 24696, 88164, 79920, 85284, 93402, 21510, 34110, 17298, 22356, 42048, 90954, 71424, 95922, 72270, 67932, 89226, 45612, 60426, 66330, 89298, 27072, 1890, 63108, 71874, 72216, 60174, 50652, 55296, 81954, 44532, 45324}

    51705

    Returns: 32

  34. {74579, 39483, 21935, 65805, 57031, 17548, 96514, 17548, 83353, 8774, 52644, 92127, 48257, 96514, 96514, 83353, 21935, 4387, 39483, 52644, 26322, 87740, 8774, 61418, 70192, 48257, 21935, 39483, 39483, 48257, 61418, 96514, 17548, 30709, 96514, 26322, 87740, 35096, 43870, 96514, 35096, 65805, 74579, 48257, 21935, 74579, 52644, 17548, 21935}

    23294

    Returns: 453

  35. {85260, 68880, 58380, 22260, 85050, 68670, 26880, 4410, 39480, 40950, 96600, 81270, 18690, 52710, 65520, 78960, 97020, 78120, 18480, 99540, 94080, 20790, 43470, 86520, 78330, 72030, 5880, 50610, 35280, 59010, 98280, 58170, 8190, 27930, 10290, 14910, 91560, 72030, 88410, 55440, 80430, 62370, 72030, 22470, 29610, 64260, 42000, 93660, 11970, 27510}

    72471

    Returns: 5

  36. {60888, 88795, 38055, 48203, 43129, 98943, 53277, 93869, 7611, 35518, 48203, 73573, 53277, 20296, 25370, 96406, 30444, 43129, 55814, 45666, 17759, 48203, 35518, 7611, 45666, 35518, 32981, 81184, 81184, 12685, 63425, 5074, 96406, 25370, 17759, 68499, 50740, 38055, 68499, 32981, 15222, 35518, 38055, 91332, 15222, 91332, 68499, 50740}

    41336

    Returns: 186

  37. {53214, 76020, 35476, 20272, 15204, 88690, 55748, 93758, 78554, 38010, 10136, 53214, 50680, 63350, 43078, 96292, 10136, 12670, 43078, 76020, 83622, 38010, 83622, 83622, 81088, 48146, 53214, 70952, 86156, 40544, 55748, 93758, 35476, 93758, 30408, 32942, 40544, 7602, 5068, 98826, 83622, 98826, 43078, 98826, 48146}

    26026

    Returns: 229

  38. {20556, 82224, 85650, 94215, 35973, 41112, 20556, 18843, 73659, 80511, 54816, 8565, 5139, 44538, 51390, 77085, 49677, 32547, 68520, 11991, 87363, 70233, 77085, 54816, 89076, 70233, 94215, 30834, 37686, 32547, 77085, 23982, 90789, 90789, 99354, 77085, 94215, 89076, 47964, 8565, 29121, 68520, 42825, 35973, 51390, 32547, 18843, 27408, 20556}

    47536

    Returns: 107

  39. {22977, 73278, 61065, 50301, 2691, 37881, 1035, 66861, 30222, 29187, 58788, 44091, 80316, 56304, 97911, 25047, 48231, 48231, 5796, 87147, 96876, 8901, 76590, 13869, 77832, 42849, 46989, 19872, 26289, 4968, 42642, 71415, 48024, 56511, 55683, 10764, 59202, 2898, 57753, 47610, 57339, 51543, 89217, 62514, 17181}

    20780

    Returns: 20

  40. {32472, 19800, 56628, 97812, 68508, 86526, 50094, 51678, 81378, 75438, 27918, 46728, 25938, 34254, 53262, 11880, 97416, 22572, 77220, 98802, 25938, 79596, 96228, 22968, 3366, 79398, 14058, 24948, 69894, 74844, 89298, 93852, 72270, 94842, 45540, 74646, 72468, 88308, 78804, 8712, 32868, 73854, 55638, 74844, 65538, 66528, 97812, 96624, 21978, 99990}

    42404

    Returns: 11

  41. {30888, 54660, 70956, 27432, 32376, 15480, 36228, 10980, 35304, 20196, 56256, 8256, 63036, 36468, 17004, 88404, 54228, 19404, 58680, 38412, 97320, 28320, 26796, 47844, 47280, 61440, 50508, 89340, 5172, 60768, 37068, 5004, 84696, 34272, 52836, 95736, 37104, 88188, 2532, 72660, 48636, 78936, 99732, 35208, 34680, 35196, 9876, 42300, 61968}

    79952

    Returns: 1

  42. {32760, 72072, 13104, 32760, 26208, 6552, 58968, 52416, 98280, 98280, 91728, 32760, 26208, 32760, 91728, 52416, 19656, 19656, 58968, 32760, 85176, 52416, 32760, 32760, 65520, 78624, 6552, 91728, 32760, 98280, 6552, 72072, 91728, 13104, 65520, 65520, 45864, 65520, 58968, 45864, 19656, 45864, 45864, 72072, 58968, 26208, 58968, 58968, 45864, 78624}

    58323

    Returns: 129

  43. {63024, 65904, 24528, 74352, 85632, 27648, 17664, 85296, 49104, 46368, 720, 50544, 4992, 66288, 78000, 59568, 38976, 49872, 13344, 9984, 47760, 34368, 69360, 68112, 16464, 98160, 51312, 55200, 72384, 40224, 9456, 51216, 95808, 45792, 21504, 60096, 36336, 78048, 55296, 39648, 55104, 31584, 31776, 62976, 30144, 54720, 94800, 19440}

    37447

    Returns: 14

  44. {37629, 37962, 30636, 14985, 49617, 88245, 24975, 79587, 50616, 5661, 18315, 94905, 37962, 35631, 18315, 33633, 85248, 65601, 51615, 43623, 2331, 57276, 61605, 71928, 16650, 15318, 56277, 44622, 91242, 39627, 99234, 23643, 41958, 84915, 94239, 34299, 5994, 28638, 4329, 97236, 53613, 38961, 62604, 39294, 41958, 83583, 63270, 34632}

    55663

    Returns: 11

  45. {76860, 27816, 4453, 96197, 50813, 58255, 28975, 52948, 95709, 2318, 52826, 77287, 64050, 8296, 61305, 24217, 48861, 23485, 90524, 305, 29951, 61549, 64965, 1525, 68808, 36966, 59902, 39284, 38308, 76372, 87474, 83082, 64904, 88633, 86559, 93147, 78324, 63074, 46970, 78080, 27816, 84241, 6771, 27206, 27328, 95221, 61427, 73505, 55144}

    65325

    Returns: 2

  46. {51730, 44340, 7390, 88680, 66510, 44340, 66510, 88680, 14780, 96070, 73900, 44340, 66510, 51730, 36950, 22170, 7390, 29560, 7390, 73900, 36950, 88680, 36950, 22170, 44340, 73900, 44340, 29560, 73900, 73900, 66510, 96070, 22170, 29560, 14780, 22170, 44340, 7390, 22170, 88680, 22170, 51730, 96070, 96070, 88680, 81290}

    35465

    Returns: 372

  47. {52790, 74465, 84940, 43040, 15435, 57455, 42035, 1550, 90625, 45735, 87410, 43850, 76175, 85945, 76515, 24670, 59555, 22110, 34070, 3230, 16095, 8875, 62985, 80920, 33760, 86645, 94360, 25860, 60250, 9515, 91385, 29780, 90100, 39055, 78895, 78555, 69950, 9345, 81450, 38390, 83985, 94380, 53195, 83525, 36050, 63630}

    97202

    Returns: 1

  48. {41662, 41662, 41662, 62493, 20831, 41662, 83324, 41662, 62493, 83324, 83324, 83324, 20831, 41662, 83324, 83324, 20831, 20831, 20831, 20831, 41662, 83324, 41662, 20831, 20831, 20831, 62493, 62493, 83324, 62493, 20831, 20831, 62493, 83324, 20831, 62493, 83324, 83324, 41662, 20831, 62493, 62493, 83324, 20831, 83324, 20831, 83324, 20831, 41662, 62493}

    25713

    Returns: 4882

  49. {83312, 86428, 18040, 48872, 90856, 16728, 82328, 32636, 6396, 25256, 85116, 43460, 24928, 47232, 62648, 24764, 55924, 89380, 62320, 21484, 24108, 71996, 68388, 95940, 53464, 30340, 63140, 3280, 17712, 71340, 28044, 10988, 17056, 21812, 17384, 12956, 36736, 4920, 30504, 64944, 16236, 10824, 93808, 81016, 2952, 20664}

    22655

    Returns: 8

  50. {21964, 46512, 37468, 23256, 9044, 64600, 27132, 69768, 91732, 5168, 12920, 41344, 83980, 71060, 85272, 99484, 11628, 59432, 41344, 59432, 45220, 32300, 7752, 51680, 7752, 29716, 10336, 87856, 51680, 51680, 72352, 56848, 9044, 62016, 99484, 42636, 31008, 86564, 27132, 32300, 5168, 89148, 77520, 38760, 43928, 69768, 80104, 1292, 9044, 56848}

    80908

    Returns: 49

  51. {97120, 58272, 38848, 48560, 58272, 19424, 97120, 29136, 97120, 77696, 67984, 97120, 58272, 38848, 48560, 48560, 77696, 38848, 77696, 29136, 97120, 67984, 67984, 38848, 9712, 58272, 9712, 38848, 19424, 19424, 48560, 38848, 77696, 77696, 29136, 97120, 19424, 9712, 97120, 58272, 48560, 97120, 9712, 48560, 58272}

    48840

    Returns: 70

  52. {8496, 6336, 4752, 9504, 7200, 7344, 864, 7776, 576, 2016, 144, 4896, 8928, 288, 5904, 7920, 4320, 4464, 9648, 9504, 6624, 8208, 4464, 720, 6912, 6624, 6336, 3744, 4464, 720, 2448, 6192, 1872, 6768, 7200, 9504, 4752, 1872, 4320, 6192, 4032, 8784, 2160, 7776, 6624, 5328, 4464, 4896}

    73392

    Returns: 2

  53. {5530, 7189, 4977, 9401, 4424, 2212, 3871, 7189, 8848, 4977, 9954, 2765, 8295, 553, 3318, 9954, 1659, 1659, 4977, 9401, 9954, 8848, 7742, 6636, 1106, 4977, 9401, 8848, 6083, 553, 4424, 3871, 6636, 7742, 3318, 3318, 8848, 3871, 2765, 2212, 2765, 6636, 9401, 7189, 2212, 4977, 8295, 553}

    92770

    Returns: 5

  54. {5510, 348, 3944, 638, 2088, 2726, 7598, 7308, 3016, 7366, 7888, 6786, 8410, 8468, 174, 1102, 2610, 2262, 8120, 5046, 9454, 696, 9280, 3538, 928, 5626, 1856, 348, 1334, 4524, 812, 8178, 4582, 3596, 9106, 7946, 2262, 8178, 8642, 4060, 9222, 8526, 1218, 8410, 7308}

    72460

    Returns: 1

  55. {7910, 7910, 6780, 5650, 9040, 2825, 1695, 9605, 2260, 8475, 8475, 565, 7910, 9605, 1695, 5650, 9040, 9605, 2260, 4520, 6780, 6215, 3390, 8475, 565, 2260, 8475, 8475, 5085, 565, 3955, 5650, 1130, 5085, 9040, 7345, 1695, 2260, 9605, 9040, 6780, 5650, 7910, 3955, 1695}

    56729

    Returns: 12

  56. {4944, 7416, 4944, 1648, 1648, 8240, 9888, 5768, 4944, 824, 4944, 8240, 824, 5768, 9064, 4120, 4120, 3296, 4120, 3296, 6592, 9064, 4120, 6592, 6592, 4944, 9064, 824, 2472, 8240, 6592, 824, 824, 5768, 6592, 7416, 6592, 8240, 4120, 4120, 1648, 4120, 1648, 2472, 5768, 4944, 6592, 5768}

    65368

    Returns: 13

  57. {7029, 781, 7810, 8591, 5467, 7810, 7810, 9372, 7810, 9372, 7810, 6248, 7810, 7029, 2343, 8591, 9372, 5467, 781, 2343, 7810, 2343, 7810, 1562, 6248, 5467, 781, 3124, 6248, 2343, 7810, 5467, 781, 7810, 2343, 9372, 1562, 7029, 5467, 781, 5467, 6248, 9372, 6248, 8591, 4686, 9372}

    58027

    Returns: 13

  58. {1844, 6454, 6454, 8298, 1844, 9220, 2766, 7376, 7376, 7376, 9220, 1844, 6454, 8298, 8298, 5532, 6454, 3688, 5532, 6454, 1844, 2766, 7376, 5532, 1844, 4610, 7376, 1844, 5532, 922, 6454, 9220, 1844, 9220, 3688, 8298, 3688, 8298, 4610, 4610, 8298, 9220, 1844, 8298, 922}

    68802

    Returns: 16

  59. {3906, 6552, 9954, 7686, 126, 9576, 6552, 9828, 3906, 8946, 6048, 1764, 5544, 1134, 2646, 9576, 1764, 3906, 3024, 1386, 2394, 8316, 2772, 2772, 1260, 1512, 2142, 9576, 6426, 5670, 2016, 6804, 4788, 8946, 3654, 5670, 1512, 5166, 1764, 630, 3276, 9072, 2268, 5418, 1512, 5166, 6930, 8190, 8820, 9324}

    99342

    Returns: 2

  60. {6844, 6608, 6372, 7552, 472, 3068, 4956, 944, 9204, 6608, 1652, 6844, 8968, 1888, 1652, 5192, 6608, 944, 5192, 2832, 6372, 7316, 8024, 7316, 8024, 1888, 3540, 3068, 9676, 472, 8260, 7552, 4956, 2360, 2596, 4484, 1180, 944, 9204, 4720, 708, 9912, 9440, 236, 4012, 5428, 3068, 8496, 3304, 5664}

    74293

    Returns: 2

  61. {7031, 445, 9078, 8455, 9345, 3471, 6942, 7654, 3471, 4806, 1335, 4895, 9612, 4806, 4005, 8633, 5696, 2937, 534, 8277, 6497, 8277, 7921, 5607, 2670, 3115, 4628, 712, 9968, 356, 4539, 2225, 8811, 4806, 4183, 5963, 1068, 4005, 8277, 9968, 7120, 7209, 3916, 5073, 9879, 9612, 801, 801}

    81009

    Returns: 1

  62. {3888, 4320, 7920, 8784, 3744, 5472, 144, 2160, 288, 4752, 9936, 4032, 9936, 6912, 8784, 4032, 6192, 7488, 720, 7776, 6048, 9936, 6480, 144, 2016, 432, 5760, 1008, 4032, 9792, 144, 720, 1008, 7200, 8640, 3600, 1728, 5184, 7344, 9504, 6480, 720, 1296, 5616, 5760, 1008}

    89990

    Returns: 1

  63. {5423, 1479, 4437, 6902, 5916, 1972, 6409, 6409, 2958, 4930, 493, 493, 9367, 9367, 3451, 2465, 8874, 3944, 1479, 493, 6902, 6902, 6902, 6902, 9367, 2465, 2465, 6409, 8874, 7395, 4437, 2465, 1479, 986, 9367, 3944, 9367, 2465, 1479, 493, 2465, 1972, 8381, 2465, 9860, 4930, 9367, 9860}

    77414

    Returns: 1

  64. {1011, 3033, 9099, 3033, 4044, 2022, 3033, 5055, 8088, 8088, 8088, 5055, 7077, 8088, 3033, 1011, 7077, 8088, 8088, 7077, 6066, 6066, 9099, 5055, 5055, 7077, 7077, 1011, 9099, 5055, 3033, 8088, 7077, 2022, 2022, 1011, 6066, 6066, 3033, 1011, 5055, 6066, 3033, 1011, 7077, 8088, 6066, 3033, 5055}

    66787

    Returns: 3

  65. {1856, 3248, 9976, 2784, 9280, 3480, 4408, 9976, 3712, 6960, 7888, 5104, 2320, 7888, 5568, 1856, 2320, 2784, 8584, 3480, 8120, 8584, 7888, 4872, 9512, 9512, 8120, 3248, 9512, 3712, 696, 5568, 5800, 2784, 7424, 9048, 2552, 3016, 6032, 9976, 928, 7192, 4872, 8352, 8120, 1160, 3944, 1624, 2088, 9976}

    83773

    Returns: 1

  66. {7250, 5075, 1450, 3625, 6525, 4350, 1450, 5075, 4350, 7975, 6525, 2900, 3625, 3625, 7250, 7975, 8700, 7975, 4350, 7250, 725, 9425, 7250, 2900, 3625, 5800, 9425, 4350, 9425, 1450, 2175, 7250, 2175, 3625, 4350, 3625, 1450, 3625, 2900, 725, 9425, 3625, 7250, 7975, 2900, 2900, 7975}

    82266

    Returns: 13

  67. {6336, 9504, 144, 6336, 5285, 864, 4464, 8784, 8208, 9648, 7200, 4320, 720, 8928, 7776, 4896, 9504, 7920, 3744, 2160, 1872, 576, 720, 6624, 4915, 4032, 6624, 4464, 7344, 8496, 1872, 2016, 6192, 6192, 6912, 288, 7776, 5904, 6768, 4320, 6624, 5691, 9504, 2448, 4752, 4752, 7200, 4464}

    63851

    Returns: 1

  68. {3808, 952, 5236, 6188, 7616, 2142, 7854, 476, 2856, 5474, 8806, 8092, 2142, 3094, 4284, 714, 7140, 2856, 714, 238, 238, 1904, 7378, 2142, 1904, 5950, 2856, 1190, 9520, 1666, 6902, 7616, 8806, 5959, 4046, 8806, 1666, 2380, 6426, 8330, 476, 8092, 1190, 9758, 9996, 5712, 2856, 3094}

    93970

    Returns: 2

  69. {5892, 9329, 4910, 8347, 1964, 1964, 9820, 8838, 5892, 4419, 4419, 8347, 982, 5892, 1473, 1473, 8838, 8838, 3437, 7856, 1473, 9329, 982, 4910, 9820, 6383, 982, 7856, 6874, 6383, 4910, 4419, 5892, 5401, 491, 8838, 1964, 9329, 6383, 3437, 6874, 8618, 8838, 4910, 3437}

    90886

    Returns: 3

  70. {1449, 126, 8883, 9702, 1701, 4095, 1701, 1197, 5103, 9639, 7875, 6804, 6851, 9072, 2518, 7497, 6300, 2142, 6426, 8253, 7119, 8064, 7686, 6993, 1008, 1512, 3213, 6237, 5292, 6678, 6048, 63, 6489, 2898, 2268, 5418, 1701, 2016, 8505, 8064, 8190, 7371, 6426, 6426, 1260, 2835, 3654}

    72827

    Returns: 1

  71. {6380, 9512, 7714, 9860, 1856, 1392, 754, 1392, 7308, 6554, 4988, 5162, 928, 9570, 1450, 1508, 7540, 4698, 2030, 580, 8178, 7772, 6148, 6554, 348, 6496, 8526, 6496, 6322, 8700, 3306, 8120, 8352, 3016, 5278, 4872, 6380, 9512, 4930, 4756, 1566, 4988, 7697, 8932, 2900}

    77414

    Returns: 1

  72. {9808, 6885, 9435, 3315, 4335, 510, 8925, 7905, 7794, 4590, 1275, 5610, 6630, 7140, 3570, 7905, 1275, 5865, 3570, 4845, 6630, 3315, 2040, 765, 6120, 7395, 9945, 4590, 1275, 6630, 3570, 8670, 255, 3825, 5610, 8925, 8160, 6332, 255, 1530, 6120, 3825, 7905, 9435, 1020, 765, 2805}

    51952

    Returns: 2

  73. {7853, 8360, 88, 1452, 1012, 1760, 8800, 5192, 9328, 4708, 1452, 4796, 4796, 2992, 9968, 8272, 9636, 880, 7216, 6336, 4840, 6688, 1672, 8712, 6644, 6072, 836, 8360, 7260, 7260, 484, 2728, 4268, 220, 8008, 8140, 6556, 6908, 1452, 1408, 8272, 2552, 1584, 5852, 9196}

    56641

    Returns: 1

  74. {4284, 4167, 9418, 9214, 5950, 7140, 3094, 5780, 4046, 2584, 9452, 6120, 9860, 8024, 3604, 5610, 9962, 5644, 1972, 8398, 714, 3789, 6392, 9214, 4658, 2550, 2584, 4352, 714, 3026, 6290, 5950, 3604, 4488, 3978, 7208, 2788, 1972, 4556, 9962, 9214, 4930, 3094, 34, 6630, 2720}

    67730

    Returns: 1

  75. {5138, 8808, 1468, 2936, 5138, 5872, 5872, 6606, 8074, 9542, 4404, 1468, 3670, 8074, 5138, 6606, 1468, 8074, 2936, 734, 1468, 5872, 8933, 8074, 8074, 8074, 8074, 2936, 3670, 2202, 7340, 1468, 4404, 2936, 1468, 4404, 1468, 5138, 4586, 9542, 9542, 6606, 2936, 8074, 1468}

    98976

    Returns: 5

  76. {5129, 1115, 6913, 9676, 7136, 3791, 2453, 8920, 9143, 8028, 4460, 8251, 4683, 669, 5575, 8920, 4237, 3568, 3122, 669, 1561, 4237, 6467, 6690, 4014, 6244, 2453, 446, 3345, 4014, 3122, 9589, 6690, 223, 9143, 7136, 4906, 9143, 2676, 4237, 4237, 5798, 1115, 4867, 5352}

    71241

    Returns: 1

  77. {9821, 2199, 3665, 7330, 5864, 9529, 8063, 9529, 8796, 3665, 733, 7330, 3665, 6597, 2199, 8796, 733, 2199, 3665, 9529, 2199, 7330, 1466, 2199, 2199, 1466, 4398, 6597, 2932, 8063, 9529, 9529, 3665, 7330, 1466, 4398, 7330, 2199, 9529, 1466, 1466, 2199, 9529, 5864, 6597}

    61587

    Returns: 1

  78. {9864, 4110, 1644, 4110, 5754, 3288, 8220, 5754, 6576, 4110, 5754, 3288, 2466, 8220, 9706, 9042, 9864, 822, 2466, 822, 1644, 8220, 5754, 822, 7398, 9042, 3288, 1644, 4932, 4110, 7398, 7398, 5754, 5754, 7398, 4932, 4110, 5754, 7398, 5754, 2466, 9864, 822, 5754, 8220, 7498, 7398}

    64536

    Returns: 13

  79. {2100, 525, 4275, 750, 9000, 5700, 8100, 300, 2100, 6075, 7425, 4950, 3225, 4725, 4798, 8175, 4275, 7939, 4050, 3900, 4725, 6375, 2700, 3900, 6975, 5025, 4500, 1725, 3825, 9600, 9450, 1875, 7125, 4425, 8925, 6450, 9975, 7875, 9600, 5850, 4425, 675, 7050, 3600, 675, 2850}

    85765

    Returns: 1

  80. {3080, 8690, 9790, 1925, 5445, 4950, 3300, 6435, 165, 5115, 5500, 2200, 1540, 5280, 7315, 3355, 1925, 8800, 8195, 2475, 9405, 7370, 2200, 4565, 8085, 3740, 8910, 770, 3410, 7810, 7810, 3630, 2530, 9740, 1375, 935, 2090, 770, 7975, 3740, 5280, 9735, 770, 3685, 5384, 3740, 7535, 3850}

    60720

    Returns: 0

  81. {6214, 1912, 478, 1912, 7409, 7409, 3346, 4063, 7170, 956, 7170, 5258, 4775, 8604, 7409, 2868, 9082, 1673, 8365, 1434, 7409, 1912, 5497, 8604, 478, 4302, 956, 239, 956, 717, 2629, 3107, 717, 3346, 6692, 9321, 6692, 7648, 6931, 5736, 717, 6692, 8843, 4302, 1673, 8604, 4063, 5736}

    56324

    Returns: 3

  82. {1}

    100000

    Returns: 99999

  83. {100000,100000,100000}

    1

    Returns: 99999

  84. {20000, 20000, 8005, 8005, 8005, 8005, 8005}

    40010

    Returns: 3

  85. {75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 75000, 1, 1 }

    100000

    Returns: 8333

  86. {1 }

    100000

    Returns: 99999

  87. {507, 530, 534, 549, 555, 562, 578, 606, 608, 620, 622, 656, 696, 700, 710, 737, 744, 753, 756, 760, 818, 825, 840, 858, 863, 882, 899, 900, 940, 962, 1034, 1040, 1054, 1081, 1102, 1109, 1126, 1133, 1178, 1226, 1229, 1268, 1269, 1330, 1341, 1368, 1454, 1459, 1467, 5162 }

    50000

    Returns: 0

  88. {100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000 }

    100000

    Returns: 0

  89. {1000, 1000, 1000 }

    1

    Returns: 999

  90. {60000, 60000 }

    100000

    Returns: 10000

  91. {100000 }

    1

    Returns: 99999

  92. {23309, 3504, 52498, 51624, 83397, 75321, 2068, 62133, 34154, 93645, 47207, 87570, 28893, 4091, 7216, 85669, 4209, 82799, 80465, 20802, 9382, 30928, 27516, 68388, 9036, 18584, 72189, 64140, 19022, 46464, 89203, 10034, 97547, 19675, 2746, 45671, 51042, 28693, 93828, 49914, 94196, 49495, 80861, 13127, 3520, 72325, 32880, 78325, 68538, 93820 }

    1386

    Returns: 682

  93. {5, 5, 10 }

    12

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: