Statistics

Problem Statement for "TheShuttles"

Problem Statement

Note that the memory limit for all tasks in this SRM is 256 MB.


The company Manao Inc. cares for its employees and tries to provide them with as much comfort as possible. One of the services Manao Inc. provides is transportation of employees from N distant locations to the office. The locations are numbered from 0 to N-1. You are given a int[] cnt containing N elements. The i-th (0-based index) element of cnt is the number of employees who live near location i.

The company wants to purchase several shuttles of the same size. These shuttles will then be used for employee transportation. Each of the shuttles will only serve one particular location. Each location will be assigned the smallest number of shuttles sufficient to transport all of the employees living close to it.

The cost of a shuttle consists of the cost baseCost of its frame and some additional cost seatCost per each seat. That is, a shuttle with X seats will cost baseCost + X * seatCost. For its shuttles, Manao Inc. can choose X to be any positive integer. (But remember that all the shuttles must have the same X.) Compute and return the least amount of money the company needs to spend on the shuttles in order to provide transportation for all employees.

Definition

Class:
TheShuttles
Method:
getLeastCost
Parameters:
int[], int, int
Returns:
int
Method signature:
int getLeastCost(int[] cnt, int baseCost, int seatCost)
(be sure your method is public)

Constraints

  • cnt will contain between 1 and 50 elements, inclusive.
  • Each element of cnt will be between 1 and 100, inclusive.
  • baseCost will be between 1 and 100, inclusive.
  • seatCost will be between 1 and 100, inclusive.

Examples

  1. {9}

    30

    5

    Returns: 75

    Manao Inc. provides transportation for its employees from a single location. There are 9 employees living near it. A shuttle with X seats will cost the company 30 + 5X. It is optimal to buy a single shuttle with 9 seats.

  2. {9, 4}

    30

    5

    Returns: 150

    Manao Inc. provides transportation from two locations. There are 9 employees living near location 0 and 4 employees living near location 1. It is optimal to buy two shuttles with 9 seats each and send a single shuttle to each location. (Note that the shuttles we buy must all be of the same size. It is not allowed to buy one shuttle with 9 and another with 4 seats.)

  3. {9, 4}

    10

    5

    Returns: 105

    This is the same test as the previous example, but baseCost is lower. It is optimal to buy three shuttles with 5 seats each and send two shuttles to location 0 and one shuttle to location 1.

  4. {51, 1, 77, 14, 17, 10, 80}

    32

    40

    Returns: 12096

  5. {86,93,26,4,48,37,36,1,72,10,79,87,88,85,4,95,54,23,31,51}

    82

    49

    Returns: 62553

  6. {51,71,54,58,50,65,27,52,39,28,10,38,30,97,26,24,58,57,20,28,2,8,2,58,39,32}

    83

    58

    Returns: 74256

  7. {66,98,52,56,3,10,87,34,51,2,77,9,97,82,59,14,59,20,71,85,90,36,5,54}

    7

    12

    Returns: 16675

  8. {21,19,43,80,16,25,13,63,26,82,9,75,96,62,76,4,57,35,57,2,38,90,51,26,62,4,61,51,1,78,48,66,35,99,6,87,71,66,60,21,3}

    95

    87

    Returns: 198428

  9. {97,26,94,25,82,26,56,100,75,66,36,2,47,2,75,15,25,32,71,33,83}

    45

    82

    Returns: 100278

  10. {10,17,63,49,27,8,24,61,54,42,14,14,76,50,82}

    51

    41

    Returns: 29375

  11. {73,71,100,99,11,83,50,69,4,2,94,57}

    86

    15

    Returns: 15213

  12. {9,19,92,10,65,74,83,57,69,78,53,18,51,23,60,46,85}

    75

    75

    Returns: 78975

  13. {74,79,94,99,23,96,55,68,32,84,12,24,10,85,23,68,66}

    42

    69

    Returns: 76560

  14. {78,51,13,55,29,46,5}

    73

    25

    Returns: 9460

  15. {90,17,37,92,40,59,35,66,20,52,26,54,1}

    98

    71

    Returns: 51612

  16. {77,40,88,33,50,82,50,88,50,74,27,89,79,89,60,40,63,3,99,92,35,97,90,55,50,62,42,69,90,93,50,30,45,50,18,75,4,34,52,11,40,62,90,42,20}

    19

    75

    Returns: 207638

  17. {3,62,66,70,10,11,79,80,96,98,18,38,43,44,15,97,3,66,31,3,48,1,10,53,39,76,11,63,63,70,61,63,6,1,64,32,15,87,66,92,23,9,46,22,3,22,20,92,2}

    48

    65

    Returns: 159467

  18. {22,49,54,93,39,15,58,67,92,47,45,17,99,94,69,58,27,21,66,52,83,48,39,19,10,60,40,31,15,58,24,36,55,75,19,74,53,30,11,17,59,96}

    78

    78

    Returns: 188604

  19. {94,40,76,95,29,5,5}

    37

    47

    Returns: 18585

  20. {90,72,70,75,24,52,63,51,56,56,15,88,19,44,18,4,18,45,96,75,31,93,3,23,32,85,57,28,93,23,24,69,64}

    28

    42

    Returns: 79352

  21. {45,13,95,31,58,72,9,94,64,92,64,53,24,97,9,56,56,35,34,39,80}

    93

    86

    Returns: 113625

  22. {10,61,6,78,71,71,2,94,82,51,97,69,3,1,1,70,99,75,59}

    12

    100

    Returns: 106080

  23. {36,98,15,80,85,90,29,5,58,96,10,10,62,72,20,59,62,64,37,14,91,58,21,31,75,90,5,25}

    83

    25

    Returns: 47334

  24. {33,84,93,94,10,29,88,28,10,78,32,70,58,73,1,15,86,20,17,39,2,6,72,53,62,79,5,11,69,13,88,1,100,99,27,45,38,26,63,17,17,64,34,30,77,46}

    56

    100

    Returns: 241824

  25. {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,100,100,100,100,100}

    100

    100

    Returns: 505000

  26. {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,100,100,100,100,100}

    44

    48

    Returns: 242200

  27. {32,70,98,72,51,87,49,41,85,75,52,40,72,23,15,15,94,60,70,54,20,98,84,87,65,54,53,98,98,99,68,3,49,54,12,69,19,9,45,55,36,43,1,20,62,54,32,21}

    78

    68

    Returns: 206500

  28. {91,69,33,83,74,20,40,62,17,63,17,34,28,93,20,99,89,44,50,26,57,11,69,41,40,28,83,7,8,52,61,1,24,69,61,62,14,18,60,60}

    27

    56

    Returns: 118158

  29. {96,13,79,49,25,77,17,94,97,38,65,12,33,50,70,83,93,22,57,19,66,58,13,81,34,28,59,49,1,54,86,52,88,17,40,50,14,6,11,58,12,63}

    60

    47

    Returns: 116316

  30. {36,67,65,42,63,74,37,89,89,1,32,39,96,18,59,57,40,100,28,49,54,29,28,7,53,74,3,71,46,26,22,59,56,93,66,7,38,92,2,83,88,10,100}

    32

    20

    Returns: 54752

  31. {70,96,35,31,84,1,89,99,27,67,92,70,90,26,76,89,13,49,46,64,47,71,27,64,41,84,60,95,88,66,54,14,18,45,30,28,35,46,10,32,98,70,12,1,12,23}

    78

    13

    Returns: 46371

  32. {31,95,47,45,67,86,63,14,40,37,18,78,21,37,76,20,64,27,100,13,74,30,81,77,58,80,33,15,7,39,35,18,51,28,6,33,79,28,10,4,64,31,22,58,33,67}

    34

    64

    Returns: 149604

  33. {19,100,22,56,30,35,91,20,28,98,85,93,53,35,27,58,4,10,71,23,80,12,96,13,72,43,5,35,81,40,16,5,66,100,30,9,86,80,36,25,41,70}

    65

    21

    Returns: 57230

  34. {28,17,9,1,83,65,12,98,85,25,17,97,83,43,11,54,39,86,58,58,7,34,94,22,36,70,7,46,44,52,62,80,36,18,100,45,5,34,13,21,40,8,13,41,69}

    42

    65

    Returns: 147972

  35. {51,99,54,29,55,40,50,36,18,97,89,91,81,22,25,35,22,22,86,12,32,18,59,18,26,88,97,67,28,87,62,5,43,41,4,88,24,23,65,88}

    47

    87

    Returns: 194220

  36. {89,89,80,18,25,53,95,30,61,61,53,47,12,15,63,53,72,10,73,20,16,69,92,69,12,42,42,78,15,52,71,23,74,70,33,27,76,16,8,31,10,86,80,63,43,25,14,69}

    66

    67

    Returns: 183975

  37. {73,21,24,56,5,15,8,87,38,86,63,77,16,31,72,13,17,98,95,40,74,71,46,84,31,37,20,50,2,25,79,86,13,20,8,53,46,21,53,67,8,47,75,79,67,56,43,27}

    50

    100

    Returns: 249900

  38. {3,87,7,99,53,16,1,66,67,47,93,39,12,42,56,43,83,65,61,50,21,28,36,52,59,8,47,24,27,17,20,39,65,71,16,89,90,54,94,91,74,74,76,62,26}

    2

    21

    Returns: 49660

  39. {69,70,74,38,47,68,25,45,37,48,9,62,38,23,51,46,34,90,67,4,79,59,8,7,42,37,53,18,67,43,3,95,92,52,45,70,73,96,35,60,93,14,91,81,71,38}

    22

    61

    Returns: 160557

  40. {47,33,83,94,18,100,8,94,56,12,97,36,40,65,65,25,11,89,64,83,63,10,84,80,74,77,91,90,62,6,11,35,41,14,85,91,98,33,18,49,64,71,6,87,86,9,65,80,73}

    59

    42

    Returns: 140360

  41. {84,39,42,69,7,22,65,54,21,99,58,70,31,9,5,63,61,88,92,38,100,50,91,67,37,2,47,12,99,86,70,5,89,14,63,28,8,34,52,41,86,98,63,14,82,92,56,67,62,17}

    24

    63

    Returns: 184605

  42. {1,23,31,37,70,45,63,50,62,57,18,8,22,10,35,68,15,43,41,22,31,74,82,17,48,26,14,18,10,16,100,93,13,39,73,20,20,9,56,9,47,49,33,16,67,62,27,89}

    81

    99

    Returns: 222768

  43. {57,71,81,69,21,57,91,83,60,71,72,67,64,95,6,65,23,60,61,29,94,65,79,98,15,38,99,62,59,26,56,78,91,58,14,18,24,56,94,68,25,18}

    100

    78

    Returns: 227920

  44. {11,30,26,12,7,61,55,60,22,79,59,28,59,53,80,14,9,87,17,68,70,25,13,91,96,97,23,15,26,98,73,21,19,44,71,84,43,59,73,72,11,73,9,27,43,51,69}

    39

    47

    Returns: 122760

  45. {80,91,77,75,25,19,7,98,63,76,100,25,52,37,42,9,86,57,31,15,49,67,24,58,18,90,25,34,3,60,94,14,12,92,39,75,60,34,98,90}

    5

    43

    Returns: 95260

  46. {27,5,35,31,24,7,98,38,15,94,88,69,82,22,95,82,100,37,85,81,39,11,42,33,9,87,28,37,48,88,28,90,68,81,98,23,28,77,98,73,48}

    16

    25

    Returns: 64176

  47. {51, 1, 77, 14, 17, 10, 80, 20, 11 }

    32

    40

    Returns: 13688

  48. {51, 1, 77, 14, 17, 10, 80 }

    32

    40

    Returns: 12096

  49. {1 }

    1

    1

    Returns: 2

  50. {5, 6 }

    1

    100

    Returns: 1111

  51. {9 }

    30

    5

    Returns: 75

  52. {100, 100 }

    23

    26

    Returns: 5246

  53. {9, 4 }

    15

    100

    Returns: 1495

  54. {100 }

    100

    1

    Returns: 200

  55. {9, 4 }

    10

    5

    Returns: 105

  56. {100 }

    100

    100

    Returns: 10100

  57. {1, 1, 1 }

    1

    1

    Returns: 6

  58. {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, 100, 100, 100, 100, 100 }

    100

    100

    Returns: 505000

  59. {99, 99, 99, 99, 99 }

    40

    40

    Returns: 20000

  60. {1, 1, 1, 1, 99 }

    50

    5

    Returns: 1350

  61. {6, 9 }

    1

    50

    Returns: 755

  62. {100, 99 }

    100

    100

    Returns: 20200

  63. {9, 4 }

    30

    5

    Returns: 150

  64. {11, 4 }

    1

    100

    Returns: 1515

  65. {98, 99, 100 }

    1

    100

    Returns: 29949

  66. {12, 20 }

    1

    10

    Returns: 328

  67. {5, 1, 1, 1 }

    1

    2

    Returns: 24

  68. {9, 3 }

    1

    20

    Returns: 244

  69. {99 }

    100

    1

    Returns: 199

  70. {9, 4 }

    1

    5

    Returns: 77

  71. {100 }

    1

    1

    Returns: 101

  72. {51 }

    30

    5

    Returns: 285

  73. {40, 50 }

    1

    100

    Returns: 9009

  74. {9, 6 }

    1

    5

    Returns: 80

  75. {100 }

    50

    5

    Returns: 550

  76. {51 }

    1

    3

    Returns: 154

  77. {1, 1, 1, 1, 1, 1, 1, 1, 1, 100 }

    50

    50

    Returns: 8500

  78. {6, 9 }

    1

    100

    Returns: 1505

  79. {1, 2, 3, 5, 7, 11, 13, 15, 17, 23, 27, 31, 37 }

    90

    10

    Returns: 4680

  80. {1, 1 }

    1

    1

    Returns: 4

  81. {100 }

    1

    3

    Returns: 301

  82. {9, 4, 27, 30, 10, 15 }

    1

    5

    Returns: 520

  83. {99 }

    10

    1

    Returns: 109

  84. {2, 3, 4 }

    2

    9

    Returns: 99

  85. {100 }

    100

    5

    Returns: 600

  86. {21, 22, 87, 12, 24 }

    5

    10

    Returns: 1870

  87. {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

    Returns: 404000

  88. {100, 100, 100, 100 }

    30

    5

    Returns: 2120

  89. {49, 2, 77, 15, 17, 11, 79 }

    1

    40

    Returns: 10250

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: