Statistics

Problem Statement for "Planks"

Problem Statement

After a recent construction project, you have found that you have some wooden planks of various lengths left over. Knowing that wood is quite valuable, you are going to try to sell them. A local hardware store has offered to buy the planks, but in order to make a retail display they want all the planks they buy to be the same length and they want this length to be some integer value. A local workshop can cut the planks into different lengths for you, but they charge costPerCut for every cut they make. The hardware store will pay woodValue per unit length for the planks that they buy (i.e., if you bring them K planks, each L units long, then they'll pay you K * L * woodValue). Any leftover wood will be thrown away. What is the maximum amount of money that you can make?


You are given a int[] lengths, in which each element is the length of a single plank of wood. Return an int containing the maximum amount of money that you can make.

Definition

Class:
Planks
Method:
makeSimilar
Parameters:
int[], int, int
Returns:
int
Method signature:
int makeSimilar(int[] lengths, int costPerCut, int woodValue)
(be sure your method is public)

Constraints

  • lengths will contain between 1 and 50 elements, inclusive.
  • Each element of lengths will be between 1 and 10000, inclusive.
  • woodValue and costPerCut will each be between 1 and 1000, inclusive.

Examples

  1. {26,103,59}

    1

    10

    Returns: 1770

    Here, wood is very valuable, while making cuts is very cheap. We can therefore make a large number of cuts to reduce the amount of wood wasted as much as possible. It is optimal to cut the planks into smaller planks of length 6. Cut the first plank into 4 pieces of length 6 and 1 of length 2, the second into 17 pieces of length 6 and 1 of length 1 and the the third into 9 pieces of length 6 and 1 of length 5. In total we have 30 pieces of length 6 that we can sell and have made 30 cuts. The total amount of money we make is therefore: 30 * 6 * 10 - 30 * 1 = 1770

  2. {26,103,59}

    10

    10

    Returns: 1680

    These are the same three planks, but now making a cut is far more expensive. It is now optimal to cut the planks to a common length of 25.

  3. {26,103,59}

    100

    10

    Returns: 1230

    Now making a cut is really expensive. Here it is optimal to throw the smallest plank away entirely. Cut the remaining two into 51 unit lengths.

  4. {5281,5297,5303,5309,5323,5333,5347,5351,5381,5387}

    5

    20

    Returns: 1057260

  5. {31,73,127,179,181,191,283,353,359,1019}

    25

    10

    Returns: 25145

  6. {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,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    1

    1

    Returns: 500000

  7. {25,50,75,100,125,150,175}

    5

    10

    Returns: 6895

  8. {25,50,75,100,125,150,175,200}

    200

    10

    Returns: 5600

  9. {5968,7944,9894,9078,4475,2129,7201,5561,9086,6804,2813,7521,9386,3651,791,607,717,6162,9554,8808,2697,4348,3150,1800,1495,3252,4047,6393,8299,7007,8059,2437,4218,7776,4147,8601,1273,4099,7109,1786,2327,9054,1874,1116,8078,597,1884,4097,3958,8350}

    754

    671

    Returns: 165495054

  10. {2763,4724,2143,8933,3695,2511,2560,5726,8115,1732,5125,1767,355,7881,233,4654,8991,76,9157,3580,2465,4900,8354,3541,9964,9544,9454,9644,8705,1279,3633,8092,6840,9464,4384,709,7117,2651,9889,2100,4201,7790,2224,9350,5427,541,6737,8606,3414,8132}

    552

    581

    Returns: 150693498

  11. {149,3983,902,1953,7292,6404,5028,9786,7240,9071,6485,9912,1834,2206,5446,5825,5560,8766,8938,7762,7381,9206,8868,5467,179,7250,2899,2000,3637,1939,3237,846,6793,9621,9445,5387,1158,1617,4407,848,8771,7828,423,1611,9032,9424,6876,2304,6985,7937}

    498

    297

    Returns: 77792388

  12. {720,1139,1608,9726,9514,8722,7543,8254,2069,8001,3893,1294,9671,1583,4569,281,435,6759,9359,2953,3896,104,1518,844,9195,2116,7257,8123,3510,5388,7715,1464,1665,6044,2966,9990,5264,6579,4613,957,8893,5654,9472,29,8519,1622,7512,483,4538,703}

    388

    474

    Returns: 109401600

  13. {5681,7665,7124,1604,4698,7956,1140,3354,2489,6632,6083,4432,9904,1979,6964,2379,1726,2735,5940,8343,373,4299,3358,6789,10000,7936,795,8946,1732,687,7806,4814,6886,1497,5247,3595,5693,6375,6278,3556,9898,8091,8987,1008,1206,2599,6363,2343,7354,13}

    478

    284

    Returns: 67499596

  14. {3317,4470,5974,5724,4937,711,3130,1566,5287,4016,6821,1627,1661,1799,9016,5624,2877,7941,2999,2545,1407,8175,2163,9409,1882,8856,9891,5279,1999,7684,5993,3291,5078,1232,9250,314,9389,3809,5581,1646,4557,827,2448,1897,1088,2451,3911,3907,5793,6054}

    63

    698

    Returns: 150795388

  15. {5154,8970,9235,9722,1556,5606,548,5918,738,9774,5678,3285,1855,3554,8312,7832,5265,3080,6028,8827,2206,6854,2904,9793,8710,6548,532,7605,8993,1410,5733,6647,667,4550,6178,9444,3164,9465,2837,4474,2813,6754,7076,8361,2088,4930,9793,8269,2479,818}

    542

    460

    Returns: 123278296

  16. {8672,3434,6213,4347,2232,4708,135,9446,341,3073,5011,47,4400,970,1321,6247,187,8185,7232,491,4391,5544,2085,2720,5834,4458,1829,8178,9567,1305,4012,7770,477,1968,8063,78,6285,2922,8023,7869,9318,5707,7935,8811,5275,2430,880,6906,2184,9582}

    939

    698

    Returns: 156477972

  17. {8569,2280,487,738,8156,6833,4059,2367,4759,6964,1214,8620,4685,3919,1181,9763,2429,4703,158,3187,2107,4040,210,7411,6371,6185,8959,1141,956,7072,671,6687,8138,9546,4419,1430,198,6814,2093,2203,8753,3275,4044,283,1670,1886,7033,7202,1920,9}

    386

    119

    Returns: 23852474

  18. {9277,2864,7348,8574,2161,2101,9246,546,2685,6903,2644,2769,7282,4679,8369,1221,3649,299,273,9007,868,3862,8750,9439,9586,1303,5817,5521,7407,5249,2139,26,6402,8107,8061,3284,7884,329,7781,4119,8565,5387,4273,4280,5417,8693,249,8406,3507,4943}

    984

    962

    Returns: 237684544

  19. {2889,4333,3931,7407,5432,2129,3702,7803,9537,6047,1203,3676,7908,2994,5332,9086,1868,4701,1259,2732,3100,9973,784,3118,3352,1821,2019,8690,8087,9538,274,5437,6295,9512,1613,147,3985,5460,3896,3686,2046,7244,4017,8476,3227,9115,882,6244,4905,8266}

    497

    202

    Returns: 46922850

  20. {4105,9867,599,9433,1590,743,6294,720,3474,8476,9999,3896,1190,7903,3402,1029,6100,5224,5574,3835,9439,126,2140,3474,7870,5360,2399,7117,252,518,9895,2216,9940,951,879,8865,4795,4124,811,6713,4606,677,6750,2522,5678,2762,491,8058,409,5413}

    882

    169

    Returns: 35337024

  21. {2075,734,6717,664,661,8983,9075,4018,2556,170,2973,6335,2277,863,288,3615,96,7074,2890,4596,1426,6197,1320,6059,3720,3794,7495,9421,6088,1155,3770,9168,5546,3253,6780,5603,968,74,4374,8587,6162,686,7907,5831,3332,1149,1761,9674,6012,1155}

    275

    938

    Returns: 190357679

  22. {2727,5156,1541,277,4507,4381,1384,2404,3930,9338,7855,8034,6837,9386,3713,2334,1471,1551,7728,7950,6804,907,1456,311,1402,7880,5900,5755,759,5446,2294,8179,2307,3274,8445,3661,1391,5428,5940,7239,6966,7986,5793,1293,8163,4516,6787,1231,2627,6400}

    536

    30

    Returns: 6355712

  23. {5452,2727,2733,2328,5327,5495,5879,7130,2250,4402,9858,166,48,9103,104,6798,4653,8752,3908,3263,7077,7956,8744,9193,7596,3245,7628,8382,972,8740,7239,3001,7234,8955,4274,9073,4489,1268,8075,94,9788,1,6536,2156,1910,1260,5022,2989,7036,5383}

    312

    988

    Returns: 250109808

  24. {3917,2934,8299,1311,1209,9388,2978,6212,6352,7219,4245,3600,1436,6080,5431,9611,1586,5302,368,9200,5141,7898,784,8044,1628,3959,1510,2101,7140,8339,9600,4333,456,2209,5860,9942,3697,5977,4702,7321,9161,1621,9930,3282,9812,8109,676,414,7089,7765}

    606

    23

    Returns: 5335698

  25. {7005,5733,642,9135,714,9785,1081,2252,4334,4314,1804,5091,2974,9598,6025,6712,2220,2491,9783,8948,334,9026,5709,7064,5506,5497,5137,8129,3087,9961,7677,4700,8237,362,6502,1372,2296,5851,6751,2586,3841,7526,8075,8461,1061,2819,4899,5962,866,4860}

    327

    509

    Returns: 127807557

  26. {6888,4882,8968,985,4124,2382,3525,8508,9443,490,4900,8087,1388,2321,9412,5340,7279,403,272,504,3349,7566,1222,8052,2087,9658,89,8598,652,6531,789,5294,3613,7469,5825,9342,8204,2115,5673,248,1029,3552,9404,1599,3171,1362,3,1799,7109,8987}

    900

    198

    Returns: 42725430

  27. {243,1546,869,2111,2268,7961,7941,3780,3985,9096,744,3228,1384,2363,3905,222,1673,5568,6533,6685,7101,6179,5517,2140,9993,9221,9564,3380,9317,2746,9858,419,529,5794,7296,3527,58,3946,765,1692,1274,6132,4889,9186,1614,6276,2336,7202,924,1757}

    945

    258

    Returns: 52824438

  28. {1924,8235,6303,5943,5190,6850,8967,2891,6436,1191,8643,5104,8218,7550,367,5364,8299,6660,7914,9077,8782,3197,5808,3606,3497,3217,677,3186,2044,8914,2564,3584,305,5185,6329,1960,9026,6113,6972,2246,2620,1132,719,1052,5939,1574,601,2557,2070,2447}

    941

    631

    Returns: 141260898

  29. {26,25,25,50}

    30

    1

    Returns: 70

  30. {15,15,30,31,35,60,30,15,15,15,15,15,60,30,15,15,39,33,15,35,30,30,30,30,30,31,37,64,150,30,30,30,15,15,15,31,15,15}

    40

    1

    Returns: 370

  31. {100,101,200,99,100,201,200,100,100,100,100,99,101,102,103}

    450

    4

    Returns: 3100

  32. {200,200,200,400}

    1000

    1

    Returns: 600

    Throw away the plank of length 400 and just sell the three planks of length 200.

  33. {10000}

    800

    530

    Returns: 5300000

  34. {10,10,10,10,10,20,20,20,1000,1000,1000,1000,1000,1000,1000,3000,3000,5000,5001,3000,3001,2000,2001,10,10,10,10}

    1000

    1

    Returns: 15000

  35. {10,10,10,10,10,10,10,10,100,10,10,10,10,10,10,10,10,10,10,10,10,10}

    120

    10

    Returns: 2100

  36. {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,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    1000

    1000

    Returns: 500000000

  37. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    1

    1

    Returns: 90000

  38. {4, 4, 2 }

    1

    10

    Returns: 98

  39. {200, 200, 200, 400 }

    1

    1

    Returns: 999

  40. {10, 10, 11, 20 }

    100

    7

    Returns: 180

  41. {10000 }

    1

    1

    Returns: 10000

  42. {24, 103, 59 }

    1

    10

    Returns: 1771

  43. {3, 6 }

    1

    1000

    Returns: 8999

  44. {1, 2 }

    1

    100

    Returns: 299

  45. {3, 3, 3, 3, 3, 3, 3, 3, 6 }

    4

    1

    Returns: 26

  46. {200, 200, 200, 400, 300, 300, 300 }

    1000

    1

    Returns: 900

  47. {1, 1, 1 }

    2

    21

    Returns: 63

  48. {10, 5, 5, 5, 5, 5 }

    75

    10

    Returns: 275

  49. {100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 100, 4600, 100, 208, 509 }

    102

    1

    Returns: 4610

  50. {30, 10 }

    1

    40

    Returns: 1598

  51. {200, 200, 200, 400 }

    300

    1

    Returns: 700

  52. {100, 100, 100, 100 }

    1000

    1

    Returns: 400

  53. {200, 200, 200, 200, 200, 400 }

    250

    1

    Returns: 1150

  54. {5, 5, 5, 5, 5, 5, 5, 10 }

    6

    1

    Returns: 39

  55. {3, 3, 3, 3, 3, 5, 6, 9 }

    4

    1

    Returns: 18

  56. {3, 6, 9, 12, 15 }

    1

    100

    Returns: 4490

  57. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 1, 1, 1 }

    1

    1000

    Returns: 59955

  58. {10000 }

    200

    1

    Returns: 10000

  59. {400, 200, 200, 200 }

    1000

    1

    Returns: 600

  60. {24, 6, 12, 18 }

    1

    20

    Returns: 1194

  61. {11, 6, 6 }

    1000

    1

    Returns: 12

  62. {10, 11, 18 }

    1

    1

    Returns: 33

  63. {5, 10 }

    10

    3

    Returns: 35

  64. {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 10 }

    51

    10

    Returns: 549

  65. {3, 6 }

    1

    10

    Returns: 89

  66. {200, 200, 200, 400 }

    1000

    1

    Returns: 600

  67. {6, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }

    4

    1

    Returns: 35

  68. {12, 8, 16 }

    3

    2

    Returns: 58

  69. {2, 2, 3 }

    100

    1

    Returns: 4

  70. {1000 }

    102

    1

    Returns: 1000

  71. {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 169 }

    131

    10

    Returns: 5318

  72. {10000 }

    1000

    1

    Returns: 10000

  73. {10000, 10000 }

    1

    1

    Returns: 20000

  74. {400, 400, 400, 400 }

    10

    100

    Returns: 160000

  75. {10, 2 }

    1

    10

    Returns: 116

  76. {25 }

    1000

    1

    Returns: 25

  77. {5 }

    1000

    1

    Returns: 5

  78. {200, 200, 200, 400 }

    1000

    1000

    Returns: 999000

  79. {22, 10, 8 }

    40

    1

    Returns: 22

  80. {10000 }

    1

    1000

    Returns: 10000000

  81. {2, 2, 4 }

    1

    1

    Returns: 7

  82. {10000 }

    100

    10

    Returns: 100000

  83. {10000 }

    1000

    1000

    Returns: 10000000

  84. {1, 3 }

    1

    1000

    Returns: 3998

  85. {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 19, 20 }

    11

    1

    Returns: 109

  86. {4000, 4000, 4000, 2000, 2000, 2000, 2000, 2000, 2000, 2000 }

    1000

    1

    Returns: 23000

  87. {200, 200, 200, 400 }

    1000

    10

    Returns: 9000

  88. {2, 1 }

    1

    1000

    Returns: 2999

  89. {1, 1, 1, 1 }

    300

    1

    Returns: 4

  90. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 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 }

    3

    2

    Returns: 97

  91. {4, 2, 2, 2 }

    1000

    1

    Returns: 6

  92. {100, 200 }

    50

    1

    Returns: 250

  93. {10000 }

    1

    5

    Returns: 50000

  94. {200, 200, 200, 300, 600 }

    250

    1

    Returns: 700

  95. {5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    6

    5

    Returns: 51

  96. {26, 103, 59, 5 }

    1

    10

    Returns: 1814

  97. {2, 4, 6 }

    1

    10

    Returns: 117

  98. {1, 1 }

    1

    1

    Returns: 2

  99. {10000 }

    100

    1

    Returns: 10000

  100. {5000, 10000 }

    10

    100

    Returns: 1499990

  101. {4000, 4000 }

    1

    1000

    Returns: 8000000

  102. {4, 2, 1 }

    1

    1

    Returns: 5

  103. {1000, 1001 }

    1

    1

    Returns: 1999

  104. {10000, 10000, 7000, 9000, 1241, 3412, 1, 1, 1, 1, 1 }

    1000

    1

    Returns: 26000

  105. {10000, 10000, 10000, 10000 }

    1000

    100

    Returns: 4000000

  106. {100, 1000, 100 }

    1000

    1

    Returns: 1000

  107. {25, 50 }

    1

    1

    Returns: 74

  108. {12, 4, 4, 4, 4, 4, 4, 4 }

    5

    1

    Returns: 30

  109. {1, 2, 3 }

    75

    10

    Returns: 30

  110. {200, 200, 200, 400 }

    10

    1

    Returns: 990

  111. {10000 }

    102

    1

    Returns: 10000

  112. {10000, 5000 }

    1000

    50

    Returns: 749000

  113. {10, 20, 10, 10 }

    15

    1

    Returns: 35

  114. {10, 10, 20 }

    9

    1

    Returns: 31

  115. {200, 200, 200, 400, 200, 200, 200, 200, 200, 200, 400 }

    1000

    1

    Returns: 1800

  116. {2, 2, 4, 4, 5 }

    10

    3

    Returns: 26

  117. {200, 200, 200, 400 }

    100

    10

    Returns: 9900

  118. {3, 3, 3, 3, 3, 3, 6, 6, 6, 9, 9 }

    7

    2

    Returns: 59

  119. {4, 4, 4, 8, 8, 8, 8, 8, 8, 8 }

    1

    18

    Returns: 1217

  120. {10, 10, 12, 20 }

    11

    1

    Returns: 29

  121. {200, 200, 200, 300, 400 }

    201

    1

    Returns: 799

  122. {200, 200, 200, 401 }

    1000

    1

    Returns: 600

  123. {1 }

    1

    10

    Returns: 10

  124. {200, 200 }

    1

    100

    Returns: 40000

  125. {10, 15 }

    1

    100

    Returns: 2497

  126. {4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    100

    49

    Returns: 1174

  127. {3, 6 }

    2

    1

    Returns: 7

  128. {200, 200, 200, 200, 200, 200, 600, 500 }

    280

    1

    Returns: 1240

  129. {200, 200, 200, 398, 400 }

    399

    1

    Returns: 601

  130. {13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 169, 26 }

    150

    10

    Returns: 5310

  131. {1, 1, 1, 2 }

    6

    5

    Returns: 19

  132. {200, 200, 200, 400, 400, 300, 300, 300 }

    1000

    1

    Returns: 900

  133. {200, 200, 200, 400, 200, 200, 200, 200, 200, 200, 200 }

    1000

    1

    Returns: 2000

  134. {200, 200, 200, 600, 200 }

    600

    1

    Returns: 800

  135. {2000, 4000 }

    1

    1000

    Returns: 5999999

  136. {10, 20 }

    1

    1

    Returns: 29

  137. {3, 3, 3, 3, 3, 3, 4, 4, 4, 6, 6, 6, 9, 9 }

    7

    2

    Returns: 59

  138. {100, 100, 100, 101, 200 }

    150

    1

    Returns: 350

  139. {200, 200, 200, 400 }

    201

    1

    Returns: 799

  140. {10000 }

    1

    42

    Returns: 420000

  141. {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, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    1000

    1

    Returns: 500000

  142. {6, 8, 10 }

    10

    10

    Returns: 170

  143. {20, 40, 21, 20, 20, 20, 20, 20, 20 }

    25

    1

    Returns: 155

  144. {10, 10, 10, 11, 20, 11 }

    13

    1

    Returns: 37

  145. {1, 1, 1, 1, 2 }

    1

    1

    Returns: 5

  146. {2, 3, 4, 2, 2, 2 }

    11

    5

    Returns: 49

  147. {2, 2, 3, 4 }

    3

    1

    Returns: 5

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: