Statistics

Problem Statement for "ThirdBuyDiscount"

Problem Statement

You want to buy a certain set of items. The shop offers you a discount percent discount on every third item you buy. Therefore, you want to purchase the items in an order that will minimize the total cost.

Given a int[] prices containing the prices of the desired items and an int discount, return the minimal amount of money you must have in order to buy all the items.

Definition

Class:
ThirdBuyDiscount
Method:
minCost
Parameters:
int[], int
Returns:
double
Method signature:
double minCost(int[] prices, int discount)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • discount will be between 0 and 100, inclusive.
  • prices will contain between 0 and 50 elements, inclusive.
  • Each element of prices will be between 0 and 2147483647, inclusive.

Examples

  1. {50, 20, 30, 17, 100}

    10

    Returns: 207.0

    One of the possible optimal sequences is {20, 30, 100, 17, 50}. So, the total cost is 20 + 30 + 0.9 * 100 + 17 + 50 = 207.

  2. {1,2,3,4,5,6,7}

    100

    Returns: 15.0

    The discount is 100%, a fantastic bargain for the consumer. Make the item with price 6 the third item you buy, and the item with price 7 the sixth.

  3. {100,40,23,592,582,19435739,204857,0}

    0

    Returns: 1.9641933E7

    There is no discount, so the total cost is always equal to the sum of all the original prices.

  4. {999,111,888,1238,52009,419,0,0,43,0,11,4,2,348,10039586,1000000,203985157}

    37

    Returns: 1.355019587E8

  5. {100,304,50607,2024,6046,708}

    75

    Returns: 17299.25

  6. {1}

    50

    Returns: 1.0

  7. {}

    100

    Returns: 0.0

  8. {}

    8

    Returns: 0.0

  9. {}

    60

    Returns: 0.0

  10. {100,200}

    100

    Returns: 300.0

  11. {11419,12091,18675,9773,8651,32194,9049,21580,12734,2100,14688,17763,19252,25315,27743,14975,15315,12910,26061,12619,23659,14063,17831,26849,21118,6006,4114,10464,2816,439,7746,32447,21083,29183,5786,25953,11702,14189,12309,2793,22903,2142,17636,10447,4358,15145,30809,8756,980,30477}

    5

    Returns: 738278.7

  12. {23666,7069,29031,27,1528,30698,2856,31518,16213,17113,25223,29884,23186,17184,11507,28657,9413,20304,27980,4210,28131,1623,23122,14154,17110,29001,2398,21189,3535,29280,12624,25997,4318,9537,6600,2323,28352,5248,2713,28464,13816,26727,20346,9997,8737,29427,9215,10560,1922}

    94

    Returns: 358819.16000000003

  13. {7112,28471,7395,31078,23289,6618,6047,32644,13033,27500,19963,13692,30495,6322,21430,2527,7802,13656,17633,25418,1199,16272,13041,10545,24569,3836,26643,18907,16139,10958,29887,25006,9034,19246,15248,26541,2873,2524,28499,831,308,1558,14174,28466,610,32700,28195,3583}

    58

    Returns: 492864.42

  14. {11698,11780,4944,3155,21382,8297,26303,3946,23122,17168,9185,2559,28900,6053,23427,18488,30493,29075,31283,4091,14487,22041,30723,8614,14986,8864,13705,12545,8433,27980,10794,27249,28392,21457,18329,22638,9817,11400,13978,15670,2775,19906,20748,13507,3018,24412,32038}

    22

    Returns: 684078.28

  15. {6605,27283,19969,12840,27476,7194,3414,9639,29842,27754,4746,1252,5786,8794,2791,646,18884,25583,5933,17382,18258,18805,25161,11462,30291,9934,5476,4928,8136,32523,19743,28668,11782,22073,29725,24230,31579,21885,9923,671,29684,30052,1083,9203,3838,8820}

    45

    Returns: 521880.19999999995

  16. {6284,25356,4103,3348,19877,22969,11609,26452,1409,18062,28895,10481,7516,25894,28122,1527,28578,655,26669,29073,9823,22004,23147,23503,4598,19577,8757,31910,22551,19559,18115,20537,3819,13193,3520,10326,6289,5334,21083,30532,21198,31055,21147,14268,28416}

    82

    Returns: 424471.78

  17. {26354,5685,1620,14898,22550,16229,15929,31847,18188,30724,4373,26089,23429,25043,3894,9499,11374,4573,11275,2051,5827,23548,27540,17392,30372,30624,1047,24672,30378,25036,18453,18720,27003,8289,27772,19381,24988,19103,32542,1019,31623,31465,8546,31756}

    47

    Returns: 627158.17

  18. {3528,23353,867,13470,21043,6740,322,26807,3854,12693,18000,7259,496,27843,8583,2997,15145,3201,15437,14492,31492,16001,481,17512,29769,26101,5625,7173,6150,18502,7850,10822,20111,29193,25991,1147,16836,26671,5133,17733,7314,31099,3903}

    49

    Returns: 414311.25

  19. {25533,17466,13965,17508,19420,17454,2554,23422,12453,31947,31614,17442,4458,5030,28585,4269,14052,28458,12682,9477,26160,11660,24015,1324,17687,2050,2349,29205,21394,30256,9731,18614,7821,9699,27962,22366,4076,6914,20079,7497,32716,3010}

    83

    Returns: 355958.61

  20. {10354,27403,19736,25171,1448,29450,25460,27765,30436,2737,2988,4739,25562,29876,20534,32107,14542,30485,32411,9700,10153,26603,4392,26453,32588,30561,24807,14835,3364,23297,13262,22570,15614,15923,31541,21311,27421,7168,22158,23347,7306}

    82

    Returns: 488887.45999999996

  21. {11419}

    72

    Returns: 11419.0

  22. {18675,9773}

    66

    Returns: 28448.0

  23. {32194,9049,21580}

    8

    Returns: 60247.479999999996

  24. {2100,14688,17763,19252}

    65

    Returns: 41289.2

  25. {27743,14975,15315,12910,26061}

    95

    Returns: 70648.15

  26. {23659,14063,17831,26849,21118,6006}

    74

    Returns: 72150.08

  27. {10464,2816,439,7746,32447,21083,29183}

    29

    Returns: 86305.3

  28. {25953,11702,14189,12309,2793,22903,2142,17636}

    44

    Returns: 88130.36

  29. {4358,15145,30809,8756,980,30477,29699,23666,7069}

    44

    Returns: 110925.6

  30. {27,1528,30698,2856,31518,16213,17113,25223,29884,23186}

    14

    Returns: 165352.0

  31. {12091,18675,9773,8651,32194,9049,21580,12734,2100,14688,17763,19252,25315,27743,14975,15315,12910,26061,12619,23659,14063,17831,26849,21118,6006,4114,10464,2816,439,7746,32447,21083,29183,5786,25953,11702,14189,12309,2793,22903,2142,17636,10447,4358,15145,30809}

    70

    Returns: 437173.69999999995

  32. {30477,29699,23666,7069,29031,27,1528,30698,2856,31518,16213}

    44

    Returns: 161997.08000000002

  33. {29884,23186,17184,11507,28657,9413,20304,27980,4210,28131,1623,23122,14154,17110,29001,2398,21189,3535,29280,12624,25997,4318,9537,6600,2323,28352,5248,2713,28464}

    80

    Returns: 263447.2

  34. {20346,9997,8737}

    36

    Returns: 31755.440000000002

  35. {10560,1922,15648,7112,28471,7395,31078,23289,6618,6047,32644,13033,27500,19963,13692,30495,6322,21430,2527,7802,13656,17633,25418,1199,16272,13041,10545,24569,3836,26643,18907,16139,10958,29887,25006}

    45

    Returns: 430007.0

  36. {15248,26541,2873,2524,28499,831,308,1558,14174,28466,610,32700,28195,3583,20965,11698,11780,4944,3155}

    71

    Returns: 121242.13999999998

  37. {26303,3946,23122,17168,9185,2559,28900,6053,23427,18488,30493,29075,31283,4091,14487,22041,30723,8614,14986,8864,13705,12545,8433,27980,10794,27249,28392,21457,18329,22638,9817,11400,13978,15670,2775}

    9

    Returns: 571344.77

  38. {13507,3018,24412,32038,13051,6605,27283,19969,12840,27476,7194,3414,9639,29842,27754,4746,1252,5786,8794,2791,646,18884,25583,5933,17382,18258,18805,25161,11462,30291,9934,5476,4928,8136,32523,19743,28668,11782,22073,29725,24230,31579}

    69

    Returns: 408983.15

  39. {671,29684,30052,1083,9203,3838,8820,4287,6284,25356,4103,3348,19877,22969,11609,26452,1409,18062,28895,10481,7516,25894,28122,1527,28578,655,26669,29073,9823}

    87

    Returns: 203865.47

  40. {23503,4598,19577,8757,31910,22551,19559,18115,20537,3819,13193,3520,10326,6289,5334,21083,30532,21198,31055,21147,14268,28416,10283,26354,5685,1620,14898,22550,16229,15929,31847,18188,30724,4373,26089,23429,25043,3894,9499,11374,4573,11275,2051,5827}

    15

    Returns: 644740.8499999999

  41. {792414451,640491979,2109875033,1414279614,137640288,1164135220,1659071583,981416915,846095821,827022443,921650599,1759597182,393613330,685771520,28778050,2126467675,1912542874,1700867510,929902613,183064951,140395748,684658950,992573529,573834196,1997370371,1550982045,1902575643,100169706,187202334,1062552281,1653044412,1519534880,754151409,616910672,1833701490,1843594839,1515337546,1121349961,157176517,231699040,827352461,282993985,432539923,1858081920,177827632,905472103}

    45

    Returns: 3.401359299265E10

  42. {572617459}

    24

    Returns: 5.72617459E8

  43. {125975840,466120503,484669798}

    59

    Returns: 7.908109601800001E8

  44. {396328836,854158188,1308308860,1998526642,1404439007,511325528,1155621706,78593936,854665521,1610157820,1746094555,1057696462,1958699438,592071470,999319469,188287452,1867711295,20186646,928935730,40009660,1847791103,1373973938,772019024,206787462,543778495,258628178,1125131233,167735524,396712835,1211660061,1905490483,268122263,1444509699,564542090,580924809,822157553,1833708074,1785818856,1406224281}

    14

    Returns: 3.4981213855259995E10

  45. {747124378,1026951895,1304580364,885197770,1599896870,855316941,1788038657,841509716,471469398,631731346,1818890890,82056858,576326375,42355140,1676613421,1139165010,1232429641,751203923,651040100,322969544,2131447071,1878797830,1446605853,1587968859,1434265283}

    65

    Returns: 1.787058448985E10

  46. {1969488955,603131646}

    33

    Returns: 2.572620601E9

  47. {411853580,268897556,1302682041}

    95

    Returns: 7.4588523805E8

  48. {92358286,1893673201,492594470,1843004919,1872888463,1747808657,643782132,1516985295,301354105,573930662,1477921895,1187205177,250295177,230697046,412161238,1381726020,1389263183,1385904060,1862281259,1727141429,106183218,1477853029,1043954791,1191999492,286615017,1535467987,255206683,745411037,738920451,381901820,1804878832,1990490016,68640864,1990877644}

    71

    Returns: 2.1853674186579998E10

  49. {1769676897,1820085173,1637632671}

    20

    Returns: 4.8633777064E9

  50. {2072476393,560102412,234753480,1530463075,882790963,441712962,1756827406,831866448,475726320,1824727431,196426537,209796173,949779204,1048642017,1147696201,1710560761,470095878,1212554922,709250703,1913218439,75186628,1747915789,1162157202,2038107967,162096061,1144665741,1147423708,1143867898,1534996645,2093710206,1143083370,329674665,279787236,1865036170,621110832,764173775,86787351,134351149,1914000274,1982866947,1219894925,635661626,1465782252,453135983,491356108,197274452,678587147,1293443667,94925578,1668574325}

    35

    Returns: 3.980465569055E10

  51. {5, 5, 5 }

    50

    Returns: 12.5

  52. {50 }

    10

    Returns: 50.0

  53. {2147483647, 2147483647, 2147483647, 2147483647, 2147483647 }

    98

    Returns: 8.63288426094E9

  54. {1, 100, 10000, 1000000, 2147483647, 1000000000, 2147483647, 2147483646, 2147483645 }

    2

    Returns: 9.4620956672E9

  55. {50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50 }

    50

    Returns: 1100.0

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

    1

    Returns: 44.76

  57. {0, 0, 0, 0, 0, 0, 0 }

    5

    Returns: 0.0

  58. {1, 5, 8, 4, 9, 4, 9, 28, 587, 2 }

    15

    Returns: 563.4

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: