Statistics

Problem Statement for "Knapsack"

Problem Statement

Given n objects, each object having a positive integer value and a positive integer weight, find a subset of these objects so the total value of the objects in the set is maximized while the total weight of the same objects is not greater than a given maximum total weight.

If there are several subsets yielding the same best total value, pick the subset among these with the lowest total weight. If there is still a tie, pick the subset with the fewest objects. If there's a tie again, pick the subset that comes first lexicographically. If A and B are two sorted (in ascending order) int[] containing the indexes of the objects in the subsets, then A is lexicographically before B if there exist some j so that A[i]=B[i] (0<=i<j) and A[j]<B[j]. For instance, {0,1,5,8,9} is lexicographically before {0,2,3,4,5}.

Create a class Knapsack which contains the method whichObjects which takes a int[] weight and a int[] value and returns a int[] containing the index of the objects (0-based) in the best possible subset according to the priorities above. The elements in the return value should be in increasing order. Element 0 in value and weight correspond to object 0, etc.

Definition

Class:
Knapsack
Method:
whichObjects
Parameters:
int[], int[], int
Returns:
int[]
Method signature:
int[] whichObjects(int[] weight, int[] value, int maxWeight)
(be sure your method is public)

Constraints

  • weight will contain between 1 and 34 elements, inclusive.
  • value will contain between 1 and 34 elements, inclusive.
  • weight will contain the same number of elements as value.
  • Each element in weight will be between 1 and 2,000,000,000, inclusive.
  • Each element in value will be between 1 and 2,000,000,000, inclusive.
  • The sum of all elements in weight will be between 1 and 2,000,000,000, inclusive.
  • The sum of all elements in value will be between 1 and 2,000,000,000, inclusive.
  • maxWeight will be between 1 and 2,000,000,000, inclusive.

Examples

  1. {415,528,744,555,526,530,274,154,769}

    {428,200,627,470,891,167,974,101,770}

    2205

    Returns: { 0, 4, 6, 7, 8 }

    The best objects to select are 0, 4, 6, 7 and 8. The total weight becomes 2138, and the value 2534.

  2. {2,4,8,16,16,4,8,32,16,16,24,24,8,16,12}

    {1,2,4,8,8,2,4,16,8,8,12,12,4,8,6}

    100

    Returns: { 1, 3, 7, 10, 11 }

    The value of all objects are exactly half their weight, so obviously the maximum value is at most 50. There are several ways to get that value, for instance, {1,2,3,4,7,10}, {3,4,7,10,14} and {1,3,7,10,11}. The first of these contains more objects than the other two, so that one is not the answer. Of the other two, the latter is lexicographically smaller, so this one is preferred.

  3. {1,2,1,2,1,2,2,4,2,4,1,1,1,1,2,2,4}

    {8,4,4,2,8,4,4,4,4,8,1,4,2,1,1,4,1}

    15

    Returns: { 0, 1, 2, 4, 5, 6, 9, 11, 12 }

  4. {10,15,20}

    {20,25,30}

    8

    Returns: { }

    All objects weight more than the maximum weight, so the method returns {}.

  5. {51302,27983,71667,12089,19588,64031, 97596,2003,5100,61584,27432,7419,50365, 2582,12821,51090,34725,94152,29702, 99239,64167,661,40163}

    {61693,84646,83719,51302,88549,5379, 92979,2577,79031,72574,21805,63706, 55248,36660,68135,25281,57868,35613, 96663,78418,84348,92573,72048}

    684929

    Returns: { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22 }

  6. {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, 67108864,137108864,267108864}

    {1,2,4,10,18,31,66,129,257,510,1026, 2048,4096,8193,16385,32768,65538, 131073,262144,524289,1048576,2097154, 4194304,8388608,16777216,33554431, 67108865,137108862,267108862}

    323717290

    Returns: { 1, 3, 5, 7, 9, 10, 14, 15, 16, 17, 18, 19, 20, 22, 24, 25, 28 }

  7. {457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823,457823}

    {238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943,238943}

    8294839

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 }

  8. {594,990,4,482,838,755,630,885,908,354,598,499,264,443,220,424,504,828,426,374,55,12,916,761,113,238,608}

    {258,388,256,293,523,258,198,357,867,890,337,946,391,437,528,353,613,892,255,193,450,734,546,67,605,365,592}

    438203

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 }

  9. {1,2,6,13,22,41,108,138,345,948,1247,3780,6081,12230,18102,54453,98443,156877,373633,799402,1656183,2536634,5062479,9647951,32943749,52600632,120657967,72676974,72074439,102066710,89182880,102148663,87731842,118840594}

    {1,3,6,15,23,39,103,140,349,944,1251,3782,6080,12235,18105,54453,98447,156878,373629,799401,1656186,2536629,5062478,9647953,32943751,52600636,120657963,72676975,72074434,102066714,89182884,102148664,87731837,118840593}

    427261321

    Returns: { 0, 2, 3, 4, 5, 8, 9, 10, 11, 14, 16, 17, 18, 22, 24, 25, 27, 28, 29, 30 }

  10. {1,3,6,10,30,60,72,255,302,998,1760,4052,6616,11942,27216,32772,107074,196383,399913,797539,1532815,2923171,8240789,15251818,21358723,46999752,79569033,111299511,109136552,125678730,74659558,77304416,81039839,133420590}

    {1,1,11,10,35,55,76,260,300,1001,1755,4057,6618,11945,27217,32772,107070,196385,399912,797544,1532819,2923171,8240786,15251818,21358722,46999757,79569032,111299510,109136553,125678725,74659557,77304416,81039843,133420589}

    443716399

    Returns: { 0, 2, 4, 6, 8, 11, 12, 15, 19, 20, 21, 22, 23, 24, 25, 26, 27, 30, 32 }

  11. {1,3,6,15,28,32,80,208,357,639,1722,2984,7399,11547,16847,37058,94891,133597,375014,526365,1421546,3065525,5654896,13250168,28096680,61010926,131498274,71793876,103378305,102710477,100700023,73187632,102719806,105503247}

    {1,1,8,10,30,33,83,206,359,644,1726,2981,7399,11543,16844,37061,94887,133597,375015,526360,1421546,3065527,5654895,13250172,28096681,61010927,131498273,71793876,103378301,102710478,100700022,73187635,102719803,105503242}

    486058212

    Returns: { 0, 1, 2, 4, 5, 6, 8, 10, 13, 20, 21, 23, 24, 25, 26, 27, 31, 32 }

  12. {1,3,5,8,31,37,67,177,492,693,1465,2736,6327,15728,28921,38009,89347,149937,347724,556621,1384549,2322834,6851180,9223026,19677706,57369669,73157754,100909312,126277258,79477792,85358670,84672648,95603387,75882901}

    {1,5,10,6,34,37,65,180,489,693,1461,2731,6323,15728,28917,38007,89348,149942,347725,556623,1384551,2322837,6851183,9223026,19677707,57369664,73157753,100909312,126277253,79477797,85358672,84672653,95603386,75882902}

    300996101

    Returns: { 0, 1, 2, 3, 5, 12, 13, 15, 16, 17, 18, 19, 21, 22, 24, 27, 30, 31 }

  13. {1,3,7,14,22,46,80,215,359,942,1522,2990,7090,12351,26743,48893,85629,235492,362968,770528,1800660,3381064,6988830,13036376,33340767,51545964,104661498,71929479,103512379,95429577,106459433,125206458,120525428,72406746}

    {1,4,5,14,20,48,80,219,359,937,1522,2990,7090,12349,26748,48896,85634,235491,362969,770531,1800656,3381067,6988833,13036375,33340766,51545969,104661499,71929477,103512383,95429573,106459436,125206463,120525431,72406742}

    338585106

    Returns: { 0, 1, 2, 4, 6, 7, 10, 12, 13, 14, 15, 16, 18, 21, 22, 23, 26, 28, 30 }

  14. {1,3,7,11,19,32,64,198,415,952,1121,2092,5769,14922,29127,36787,116917,228114,340001,925009,1886225,3622471,8286707,14416147,31416453,36438342,73955749,80446505,126168837,106131652,83293021,74962573,74400592,121761141}

    {1,6,8,10,22,29,66,201,410,952,1125,2087,5772,14918,29126,36789,116919,228116,339998,925009,1886230,3622468,8286707,14416150,31416457,36438345,73955748,80446501,126168840,106131652,83293017,74962577,74400596,121761137}

    579329771

    Returns: { 0, 1, 2, 4, 5, 9, 10, 11, 12, 15, 16, 17, 19, 20, 21, 25, 26, 27, 28, 29, 31, 32 }

  15. {1,3,7,15,31,63,117,234,486,976,1918,3998,7950,16134,32157,60788,127244,238808,492078,973451,1964274,4171035,7580901,15709932,30751651,60485653,125033206,121628178,133508478,122894521,121710325,126005820,132666623,123176243}

    {1,3,8,20,33,62,119,237,485,973,1921,3999,7947,16134,32158,60787,127244,238808,492083,973454,1964276,4171038,7580898,15709933,30751647,60485653,125033201,121628174,133508478,122894516,121710325,126005820,132666621,123176245}

    469611984

    Returns: { 0, 2, 3, 4, 6, 9, 10, 13, 15, 16, 19, 20, 22, 23, 25, 28, 31, 33 }

  16. {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,67108864,67108864,67108864,67108864,67108864,67108864,67108864,67108864}

    {1,3,6,9,15,33,65,126,257,514,1025,2046,4097,8193,16384,32769,65536,131074,262144,524290,1048575,2097151,4194304,8388610,16777216,33554432,67108863,67108862,67108864,67108862,67108866,67108862,67108863,67108866}

    255396926

    Returns: { 1, 2, 3, 4, 5, 10, 11, 16, 19, 20, 21, 24, 25, 28, 30, 33 }

  17. {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,67108864,67108864,67108864,67108864,67108864,67108864,67108864,67108864}

    {1,4,6,7,16,33,65,129,256,514,1026,2050,4094,8193,16383,32770,65538,131073,262142,524288,1048575,2097153,4194302,8388606,16777216,33554434,67108865,67108864,67108863,67108862,67108864,67108864,67108864,67108866}

    394233085

    Returns: { 0, 2, 3, 4, 5, 6, 7, 10, 15, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 30, 31, 33 }

  18. {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,67108864,67108864,67108864,67108864,67108864,67108864,67108864,67108864}

    {2,2,3,9,16,34,62,130,258,510,1026,2050,4095,8194,16384,32770,65537,131074,262146,524289,1048576,2097154,4194303,8388607,16777215,33554433,67108862,67108863,67108862,67108865,67108865,67108864,67108866,67108863}

    193044525

    Returns: { 0, 2, 3, 5, 13, 15, 16, 23, 24, 25, 29, 32 }

  19. {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,67108864,67108864,67108864,67108864,67108864,67108864,67108864,67108864}

    {3,1,6,7,18,33,64,128,256,512,1022,2050,4097,8194,16385,32769,65534,131074,262146,524289,1048576,2097151,4194304,8388610,16777217,33554431,67108862,67108864,67108863,67108865,67108862,67108865,67108862,67108866}

    284853588

    Returns: { 2, 4, 6, 8, 10, 15, 17, 19, 20, 21, 22, 23, 27, 29, 31, 33 }

  20. {4,4,2,1,1,1,2,1,2,2,4,1,1,1,4,4,4,2,2,2,2,1,4,2,4,1,1,4,2,2,4}

    {8,2,8,8,1,8,8,4,8,4,4,2,1,2,4,1,2,1,4,4,1,4,8,4,8,4,1,2,1,2,8}

    36

    Returns: { 0, 2, 3, 5, 6, 7, 8, 9, 11, 18, 19, 21, 22, 23, 24, 25, 30 }

  21. {1,4,1,4,4,4,1,4,1,1,4,4,4,4,1,2,1,4,1,4,1,2,2,4,1,1,4,2,2,2,2,2,1}

    {4,8,2,1,4,8,1,8,1,8,8,8,1,4,1,2,2,8,4,4,8,2,2,4,8,1,1,4,2,2,1,4,4}

    49

    Returns: { 0, 1, 2, 4, 5, 6, 7, 9, 10, 11, 13, 16, 17, 18, 19, 20, 24, 27, 31, 32 }

  22. {10000,40000,20000,10000,20000,20000,10000,20000,10000,20000,40000,40000,40000,10000,10000,10000,10000,40000,10000,20000,10000,40000,10000,40000,20000,10000,10000,40000,40000,20000,10000,10000,20000,10000}

    {80000,40000,10000,80000,40000,10000,80000,20000,10000,40000,40000,40000,40000,80000,80000,40000,40000,40000,40000,10000,10000,10000,40000,80000,20000,80000,20000,40000,20000,20000,10000,40000,20000,20000}

    150000

    Returns: { 0, 3, 6, 13, 14, 15, 16, 18, 22, 23, 25, 31 }

  23. {20000,40000,10000,40000,20000,40000,20000,10000,20000,40000,20000,20000,10000,20000,40000,10000,20000,40000,20000,10000,20000,10000,40000,20000,20000,20000,40000,10000,40000,40000,40000,10000,10000,40000}

    {40000,40000,80000,40000,10000,20000,10000,20000,80000,10000,40000,40000,10000,10000,80000,20000,10000,10000,10000,80000,80000,80000,10000,40000,40000,20000,20000,20000,40000,40000,10000,80000,10000,10000}

    390000

    Returns: { 0, 1, 2, 3, 7, 8, 10, 11, 14, 15, 19, 20, 21, 23, 24, 25, 27, 28, 31 }

  24. {4,2,4,4,1,4,1,2,4,4,4,1,4,4,1,4,4,1,2,2,4,1,1,4,2,2,4,1,1,4,2,1,1,1}

    {2,2,8,4,1,8,8,1,2,2,4,8,8,8,8,8,2,4,8,2,2,4,1,1,4,8,4,2,2,2,2,4,2,8}

    43

    Returns: { 1, 2, 3, 4, 5, 6, 11, 12, 13, 14, 15, 17, 18, 21, 24, 25, 27, 28, 31, 32, 33 }

  25. {2,4,1,4,4,2,2,1,2,2,4,4,2,2,4,2,2,1,1,1,4,1,2,4,1,4,2,1,2,2,1,1,1}

    {8,4,4,1,1,1,1,4,2,2,4,4,8,2,8,4,4,4,1,2,8,8,1,8,8,1,2,1,1,8,2,8,4}

    33

    Returns: { 0, 2, 7, 8, 12, 14, 15, 16, 17, 19, 20, 21, 23, 24, 29, 30, 31, 32 }

  26. {1,4,4,2,2,2,1,4,1,2,4,1,4,4,1,2,2,2,1,1,1,1,1,1,4,1,2,1,2,2,4,4,1}

    {4,8,2,2,4,8,1,1,8,2,4,1,8,4,1,4,1,4,2,4,4,2,1,2,2,8,8,4,4,4,2,2,8}

    42

    Returns: { 0, 1, 3, 4, 5, 8, 10, 12, 13, 15, 17, 18, 19, 20, 21, 23, 25, 26, 27, 28, 29, 32 }

  27. {4,4,4,4,1,4,1,1,2,1,1,4,1,2,1,2,1,2,4,2,1,2,4,1,1,4,4,1,2,1,2,2,4,4}

    {4,1,2,1,8,8,8,8,8,2,2,4,1,8,2,1,8,4,4,1,2,2,2,2,1,1,8,2,1,1,2,8,2,2}

    41

    Returns: { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 21, 23, 26, 27, 31 }

  28. {1,1,4,4,2,2,1,4,4,4,1,1,1,4,4,4,1,4,4,4,2,1,2,2,1,4,1,2,4,2,1,1,2}

    {4,4,1,2,4,2,2,8,4,2,1,4,1,4,4,2,2,8,8,4,8,2,2,1,8,4,4,8,2,4,8,2,8}

    55

    Returns: { 0, 1, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 17, 18, 19, 20, 21, 24, 25, 26, 27, 29, 30, 31, 32 }

  29. {1,1,4,4,4,1,1,2,2,4,1,1,2,2,1,2,1,1,1,4,1,4,1,1,4,4,1,4,2}

    {2,1,4,2,4,8,4,8,1,8,8,8,4,1,1,8,4,4,2,2,2,2,1,8,4,1,2,8,8}

    35

    Returns: { 0, 2, 4, 5, 6, 7, 9, 10, 11, 12, 15, 16, 17, 18, 20, 23, 26, 27, 28 }

  30. {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,67108864,67108864,67108864,67108864,67108864,67108864,67108864,67108864}

    {1,3,6,9,17,34,66,130,257,514,1025,2048,4097,8190,16385,32769,65538,131072,262146,524286,1048576,2097153,4194306,8388610,16777218,33554433,67108864,67108864,67108862,67108865,67108865,67108863,67108863,67108862}

    378272717

    Returns: { 0, 2, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 19, 23, 25, 26, 27, 29, 30, 31 }

  31. {936,747,321,566,90,825,738,817,553,999,595,688,907,743,553}

    {657,822,80,695,977,417,850,912,216,924,219,264,900,928,926}

    3675

    Returns: { 3, 4, 6, 7, 13, 14 }

  32. {163,250,331,523,391,97,81,808,162,884,537,747,453,469,240,606,210,463,24}

    {785,610,192,776,286,595,982,373,39,974,244,79,138,161,560,503,184,354,136}

    4655

    Returns: { 0, 1, 3, 4, 5, 6, 8, 9, 10, 14, 15, 16, 17, 18 }

  33. {237,197,831,394,690,2,245,235,608,305,169,725,661,863,507,513,732,162,494,684,832,93,888}

    {483,948,233,997,302,500,234,387,811,86,834,558,648,968,883,235,3,782,317,900,410,957,870}

    5635

    Returns: { 0, 1, 3, 5, 7, 8, 10, 11, 12, 13, 14, 17, 19, 21 }

  34. {741,754,990,128,340,722,73,151,124,416,478,453,646,547,926,305,374,841,566,340,822,971,807,979,243}

    {561,751,305,858,594,772,466,185,214,672,917,894,24,393,547,862,953,991,766,63,221,887,480,365,283}

    6125

    Returns: { 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 15, 16, 17, 18, 24 }

  35. {960,792,331,617,341,554,409,310,702,726,801,56,870,905,774,68,901,862,965,444,933,439,439,678}

    {181,286,921,217,671,405,838,50,582,846,423,685,509,127,205,966,469,562,497,955,448,291,238,301}

    5880

    Returns: { 2, 4, 5, 6, 8, 9, 11, 12, 15, 17, 19, 21 }

  36. {245,311,501,861,342,794,253,66}

    {639,554,729,720,534,45,347,334}

    1960

    Returns: { 0, 1, 2, 4, 6, 7 }

  37. {530,830,671,106,990,34,745,470,929,683,773,658,94,910,270,831,780,531,13,548,691,907,718,25,356,375,285,680,613,707}

    {449,821,537,575,748,685,209,267,302,373,929,477,643,509,864,718,338,133,580,848,322,695,645,588,195,362,690,359,776,784}

    7350

    Returns: { 0, 1, 3, 5, 10, 12, 14, 15, 18, 19, 21, 22, 23, 26, 28, 29 }

  38. {34,386,830,840,640,106,925,385,796,146,82,386,79,946,41,975,423,210,436,204,681,785,637,221,191,825,6,293,703}

    {879,624,961,437,688,958,89,65,353,959,364,813,19,934,528,698,288,990,30,11,485,977,255,992,291,472,563,858,677}

    7105

    Returns: { 0, 1, 2, 4, 5, 9, 10, 11, 12, 13, 14, 15, 17, 21, 23, 24, 26, 27, 28 }

  39. {967,905,1,85,641,346,417,141,86,301,419,511,191,625,965,356,187,220,460,756,913,843,277,71,469,525,796}

    {689,891,418,292,903,950,599,997,389,722,941,708,262,625,533,574,722,275,395,281,422,503,458,460,107,274,855}

    6615

    Returns: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 22, 23, 26 }

  40. {253,776,171,329,641,586,261,897,23,456,405,989,303,952,537,738,302,230,483,308,792,253,917,920,747,224,937,702,96,89,210}

    {147,159,226,795,765,590,460,930,73,485,519,604,153,316,186,450,156,561,761,551,359,381,13,928,571,427,146,308,827,90,858}

    7595

    Returns: { 0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 17, 18, 19, 21, 23, 24, 25, 28, 29, 30 }

  41. {245,311,501,861,342,794,253,66}

    {639,554,729,720,534,45,347,334}

    65

    Returns: { }

  42. {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,67108864,67108864,67108864,67108864,67108864,67108864,67108864,67108864}

    {1,2,4,10,18,31,66,129,257,510,1026,2048,4096,8193,16385,32768,65538,131073,262144,524289,1048576,2097154,4194304,8388608,16777216,33554431,67108865,67108862,67108862,67108865,67108864,67108866,67108864,67108866}

    323717290

    Returns: { 1, 3, 5, 7, 11, 15, 16, 17, 19, 22, 24, 25, 26, 29, 31, 33 }

  43. {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,67108864,67108864,67108864,67108864,67108864}

    {1,2,4,8,16,34,65,126,257,513,1025,2050,4095,8192,16384,32768,65538,131074,262143,524289,1048575,2097153,4194305,8388608,16777217,33554432,67108865,67108863,67108863,67108866,67108863}

    357168976

    Returns: { 4, 6, 8, 9, 10, 12, 13, 14, 15, 16, 19, 22, 24, 26, 27, 28, 29, 30 }

  44. {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,67108864,67108864,67108864,67108864}

    {1,2,2,10,15,34,66,128,258,514,1025,2050,4096,8192,16382,32766,65537,131073,262145,524288,1048576,2097152,4194304,8388608,16777218,33554433,67108862,67108864,67108865,67108866}

    351235527

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 }

  45. {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,67108864,67108864,67108864}

    {1,4,4,9,17,34,65,130,257,511,1024,2050,4095,8194,16382,32770,65535,131073,262142,524289,1048576,2097153,4194306,8388608,16777217,33554432,67108864,67108865,67108866}

    336349200

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28 }

  46. {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,67108864,67108864}

    {1,1,5,10,17,32,62,130,258,513,1025,2050,4098,8194,16384,32769,65538,131073,262144,524288,1048578,2097152,4194304,8388607,16777216,33554432,67108865,67108865}

    287595766

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27 }

  47. {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,67108864}

    {1,3,5,10,17,32,65,129,257,514,1024,2049,4098,8191,16385,32768,65538,131074,262142,524290,1048577,2097150,4194306,8388609,16777214,33554432,67108862}

    456385333

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 }

  48. {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,67108864,67108864,67108864,67108864,67108864,67108864}

    {1,4,5,8,17,34,65,126,258,512,1022,2049,4097,8192,16383,32770,65537,131072,262146,524289,1048578,2097154,4194304,8388608,16777218,33554434,67108862,67108863,67108866,67108862,67108863,67108862}

    273660787

    Returns: { 0, 1, 4, 5, 6, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 22, 26, 27, 28, 30 }

  49. {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,67108864,134217728,268435456,536870912,813741824}

    {1,2,4,8,15,32,66,126,254,512,1025,2047,4094,8193,16384,32768,65536,131074,262144,524287,1048577,2097152,4194306,8388608,16777218,33554433,67108863,134217729,268435454,536870913,813741822}

    1276018230

    Returns: { 1, 2, 4, 5, 8, 9, 10, 14, 15, 16, 18, 19, 23, 24, 25, 27, 28, 30 }

  50. {2,4,8,16,16,4,8,32,16,16,24,24,8,16,12}

    {1,2,4,8,8,2,4,16,8,8,12,12,4,8,6}

    96

    Returns: { 3, 7, 10, 11 }

  51. {2,4,8,16,16,4,8,32,16,16,24,24,8,16,12}

    {1,2,4,8,8,2,4,16,8,8,12,12,4,8,6}

    92

    Returns: { 7, 10, 11, 14 }

  52. {2,4,8,16,16,4,8,32,16,16,24,24,8,16,12}

    {1,2,4,8,8,2,4,16,8,8,12,12,4,8,6}

    85

    Returns: { 1, 7, 10, 11 }

  53. {2,4,8,16,16,4,8,32,16,16,24,24,8,16,12}

    {1,2,4,8,8,2,4,16,8,8,12,12,4,8,6}

    110

    Returns: { 0, 3, 7, 10, 11, 14 }

  54. { 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 6, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2 }

    { 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2 }

    60

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 31 }

  55. { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    40

    Returns: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 }

  56. { 51302, 27983, 71667, 12089, 19588, 64031, 97596, 2003, 5100, 61584, 27432, 7419, 50365, 2582, 12821, 51090, 34725, 94152, 29702, 99239, 64167, 661, 40163 }

    { 61693, 84646, 83719, 51302, 88549, 5379, 92979, 2577, 79031, 72574, 21805, 63706, 55248, 36660, 68135, 25281, 57868, 35613, 96663, 78418, 84348, 92573, 72048 }

    684929

    Returns: { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 21, 22 }

  57. { 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, 67108864, 137108864, 267108864 }

    { 1, 2, 4, 10, 18, 31, 66, 129, 257, 510, 1026, 2048, 4096, 8193, 16385, 32768, 65538, 131073, 262144, 524289, 1048576, 2097154, 4194304, 8388608, 16777216, 33554431, 67108865, 137108862, 267108862 }

    323717290

    Returns: { 1, 3, 5, 7, 9, 10, 14, 15, 16, 17, 18, 19, 20, 22, 24, 25, 28 }

  58. { 1241, 1231, 1249, 5493, 3458, 1231, 1420, 1258, 5345, 3469, 3648, 7890, 3451, 5383, 5895, 8906, 2358, 2359, 2359, 9834, 9875, 8893, 5432, 5784, 9853, 7853, 9083, 8394, 3458, 9802, 8903, 3248, 9802, 2124 }

    { 1245, 4534, 3594, 3459, 2358, 2358, 1254, 8906, 53984, 4598, 2358, 2350, 4385, 7842, 5437, 2358, 2537, 5782, 2212, 1256, 9853, 2357, 2351, 4583, 3475, 6895, 5468, 6895, 3786, 4376, 3689, 3863, 9864, 3486 }

    75000

    Returns: { 0, 1, 2, 5, 6, 7, 8, 9, 12, 13, 14, 16, 17, 18, 20, 25, 28, 31, 32, 33 }

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: