Statistics

Problem Statement for "Hotel"

Problem Statement

The hotel industry is difficult to thrive in, especially when competing at a resort city like Las Vegas. Marketing is essential and often gets a large part of total revenues. You have a list of cities you can market at, and a good estimate of how many customers you will get for a certain amount of money spent at each city.

You are given int[]s customers and cost. cost[i] is the amount of money required to get customers[i] customers from the i-th city. You are only allowed to spend integer multiples of the cost for any city. For example, if it costs 9 to get 3 customers from a certain city, you can spend 9 to get 3 customer, 18 to get 6 customers, 27 to get 9 customers, but not 3 to get 1 customer, or 12 to get 4 customers. Each city has an unlimited number of potential customers. Return the minimum amount of money required to get at least minCustomers customers.

Definition

Class:
Hotel
Method:
marketCost
Parameters:
int, int[], int[]
Returns:
int
Method signature:
int marketCost(int minCustomers, int[] customers, int[] cost)
(be sure your method is public)

Constraints

  • minCustomers will be between 1 and 1000, inclusive.
  • customers will contain between 1 and 20 elements, inclusive.
  • cost will have the same number of elements as customers.
  • Each element of cost and customers will be between 1 and 100, inclusive.

Examples

  1. 10

    {1,2,3}

    {3,2,1}

    Returns: 4

    Just get 12 customers from the third city.

  2. 10

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

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

    Returns: 10

    It does not matter from which city you get your customers.

  3. 12

    {5, 1}

    {3, 1}

    Returns: 8

    Get 10 customers from the first city, and 2 from the second city.

  4. 100

    {9, 11, 4, 7, 2, 8}

    {4, 9, 3, 8, 1, 9}

    Returns: 45

  5. 99

    {3,5,7,9,13,17}

    {17,13,9,7,5,3}

    Returns: 18

  6. 1000

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

    Returns: 1000

    Worst case.

  7. 999

    {2,3,5,7,11,13,17,19}

    {2,3,5,7,11,13,17,19}

    Returns: 999

  8. 1

    {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: 100

  9. 99

    {100}

    {100}

    Returns: 100

  10. 1000

    {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: 1000

  11. 1000

    {99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99}

    {99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99,99}

    Returns: 1089

  12. 1000

    {99}

    {100}

    Returns: 1100

    Largest return value.

  13. 1000

    {99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80}

    {100,99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81}

    Returns: 1011

  14. 1000

    {1}

    {100}

    Returns: 100000

    Largestest return value :)

  15. 18

    { 29, 81, 93, 62, 2, 68, 28, 57, 97, 23, 40, 56, 75, 79, 85, 11, 88, 69 }

    { 89, 4, 90, 37, 30, 87, 93, 92, 28, 39, 23, 74, 66, 61, 76, 36, 4, 48 }

    Returns: 4

  16. 11

    { 11, 31, 26, 42, 79, 70, 65, 17, 95, 94, 30 }

    { 7, 29, 12, 88, 22, 61, 59, 80, 8, 39, 89 }

    Returns: 7

  17. 13

    { 31, 90, 100, 54, 52, 51, 50, 41, 98, 19, 76, 8, 13 }

    { 12, 21, 50, 23, 5, 81, 24, 11, 35, 22, 76, 18, 24 }

    Returns: 5

  18. 20

    { 93, 62, 36, 18, 81, 18, 100, 79, 63, 13, 63, 86, 33, 88, 56, 37, 95, 65, 49, 63 }

    { 98, 58, 82, 28, 33, 3, 36, 39, 12, 67, 32, 61, 11, 61, 68, 33, 66, 31, 36, 36 }

    Returns: 6

  19. 18

    { 5, 49, 29, 68, 78, 55, 46, 85, 51, 44, 77, 8, 61, 95, 94, 30, 3, 27 }

    { 48, 15, 92, 72, 28, 81, 90, 50, 40, 61, 94, 56, 81, 24, 61, 10, 95, 99 }

    Returns: 10

  20. 4

    { 49, 56, 93, 73 }

    { 69, 30, 65, 17 }

    Returns: 17

  21. 8

    { 30, 10, 48, 10, 36, 38, 84, 86 }

    { 42, 17, 75, 25, 70, 10, 85, 76 }

    Returns: 10

  22. 16

    { 93, 33, 85, 2, 79, 91, 32, 37, 71, 35, 61, 27, 72, 37, 14, 17 }

    { 22, 30, 11, 90, 48, 37, 42, 85, 14, 28, 23, 79, 62, 37, 22, 74 }

    Returns: 11

  23. 50

    {1, 20, 25}

    {5, 40, 55}

    Returns: 110

  24. 500

    {1, 20, 25}

    {5, 40, 55}

    Returns: 1000

  25. 26

    {5, 7, 2}

    {25, 35, 10}

    Returns: 130

  26. 26

    {5, 7, 3}

    {26, 36, 15}

    Returns: 131

  27. 261

    {50, 70, 30, 30, 1}

    {26, 36, 15, 15, 1}

    Returns: 132

  28. 12

    {5, 1 }

    {3, 1 }

    Returns: 8

  29. 10

    {1, 2, 3 }

    {3, 2, 1 }

    Returns: 4

  30. 100

    {9, 11, 4, 7, 2, 8 }

    {4, 9, 3, 8, 1, 9 }

    Returns: 45

  31. 1000

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

    {20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20 }

    Returns: 1000

  32. 993

    {62, 1 }

    {1, 2 }

    Returns: 17

  33. 1000

    {1, 9, 5 }

    {33, 10, 6 }

    Returns: 1112

  34. 1000

    {99 }

    {100 }

    Returns: 1100

  35. 1000

    {99 }

    {1 }

    Returns: 11

  36. 999

    {1, 2, 3 }

    {25, 50, 100 }

    Returns: 24975

  37. 50

    {8, 9 }

    {7, 8 }

    Returns: 44

  38. 14

    {2, 4, 8 }

    {3, 4, 8 }

    Returns: 15

  39. 1000

    {99 }

    {99 }

    Returns: 1089

  40. 14

    {9, 6, 2 }

    {12, 8, 3 }

    Returns: 19

  41. 14

    {6, 8, 10 }

    {6, 8, 9 }

    Returns: 14

  42. 33

    {30, 16, 1, 33, 40, 50, 60, 70, 80, 90, 100, 100, 100, 6, 7, 8, 9, 10, 11, 12 }

    {10, 6, 3, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 8, 9, 10, 11, 12 }

    Returns: 15

  43. 5

    {5, 100 }

    {2, 1 }

    Returns: 1

  44. 6

    {5, 3 }

    {3, 2 }

    Returns: 4

  45. 999

    {3, 98, 98, 98, 98, 78, 7, 78, 78, 78, 78, 78, 78, 78, 2, 32, 3, 32, 32 }

    {32, 32, 1, 3, 3, 4, 75, 32, 32, 1, 3, 3, 32, 32, 32, 1, 3, 2, 3 }

    Returns: 11

  46. 100

    {9, 10, 1 }

    {4, 5, 2 }

    Returns: 45

  47. 5

    {4, 5 }

    {2, 3 }

    Returns: 3

  48. 55

    {50, 4, 1 }

    {10, 2, 1 }

    Returns: 13

  49. 23

    {5, 7, 11 }

    {5, 6, 7 }

    Returns: 18

  50. 1000

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

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

    Returns: 1000

  51. 100

    {98, 99 }

    {100, 100 }

    Returns: 200

  52. 5

    {10, 20, 30 }

    {30, 20, 10 }

    Returns: 10

  53. 192

    {100, 96 }

    {100, 98 }

    Returns: 196

  54. 3

    {95, 92, 100, 86 }

    {94, 91, 99, 92 }

    Returns: 91

  55. 1

    {100 }

    {1 }

    Returns: 1

  56. 12

    {1, 2, 3, 4, 5 }

    {2, 2, 2, 2, 2 }

    Returns: 6

  57. 1

    {1, 100 }

    {100, 1 }

    Returns: 1

  58. 401

    {20, 21 }

    {19, 21 }

    Returns: 382

  59. 999

    {99, 50 }

    {100, 51 }

    Returns: 1018

  60. 997

    {97, 95, 91, 70, 25, 91, 94, 99, 100, 5, 1, 25, 92, 96, 94, 99, 99, 97, 91, 31 }

    {81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 2, 25, 4 }

    Returns: 22

  61. 1

    {99, 1, 2, 3 }

    {1, 50, 50, 50 }

    Returns: 1

  62. 1000

    {39, 1 }

    {1, 100 }

    Returns: 26

  63. 9

    {5, 1, 3 }

    {12, 3, 8 }

    Returns: 23

  64. 10

    {6, 5 }

    {12, 11 }

    Returns: 22

  65. 110

    {70, 30, 10 }

    {6, 3, 2 }

    Returns: 11

  66. 1000

    {99, 100, 78 }

    {91, 99, 79 }

    Returns: 953

  67. 4

    {3, 2 }

    {3, 2 }

    Returns: 4

  68. 19

    {9, 5 }

    {3, 2 }

    Returns: 7

  69. 102

    {7, 9 }

    {7, 2 }

    Returns: 24

  70. 1000

    {83, 17, 15, 27, 21, 63, 62, 59, 49, 48, 8, 19, 95, 2, 10, 89, 92, 34, 52, 66 }

    {14, 86, 44, 81, 34, 16, 18, 57, 25, 64, 36, 27, 35, 90, 31, 24, 21, 86, 39, 69 }

    Returns: 175

  71. 1000

    {21, 27, 24, 20, 29, 24, 28, 28, 22, 24, 25, 25, 21, 27, 21, 21, 25, 22, 27, 26 }

    {21, 24, 22, 23, 22, 22, 21, 26, 28, 25, 27, 26, 21, 28, 29, 22, 27, 29, 25, 24 }

    Returns: 755

  72. 20

    {12, 15, 5 }

    {3, 3, 2 }

    Returns: 5

  73. 62

    {61, 31 }

    {30, 20 }

    Returns: 40

  74. 18

    {11, 1, 6 }

    {5, 1, 3 }

    Returns: 9

  75. 20

    {10 }

    {100 }

    Returns: 200

  76. 2

    {1, 5 }

    {100, 1 }

    Returns: 1

  77. 10

    {9, 5 }

    {6, 5 }

    Returns: 10

  78. 10

    {100 }

    {100 }

    Returns: 100

  79. 1000

    {1 }

    {100 }

    Returns: 100000

  80. 1

    {1 }

    {1 }

    Returns: 1

  81. 5

    {50, 4, 1 }

    {4, 2, 1 }

    Returns: 3

  82. 20

    {4, 6, 7 }

    {5, 6, 8 }

    Returns: 22

  83. 100

    {9, 11, 4, 7, 2, 8 }

    {4, 9, 3, 8, 2, 9 }

    Returns: 46

  84. 8

    {6, 4 }

    {6, 5 }

    Returns: 10

  85. 41

    {5, 7 }

    {50, 69 }

    Returns: 407

  86. 1000

    {80, 99, 98 }

    {100, 100, 100 }

    Returns: 1100

  87. 1

    {3, 1, 10 }

    {1, 2, 3 }

    Returns: 1

  88. 90

    {60, 90, 1 }

    {50, 90, 2 }

    Returns: 90

  89. 10

    {5, 4 }

    {20, 15 }

    Returns: 40

  90. 15

    {6, 1, 50, 49, 48 }

    {5, 1, 50, 49, 48 }

    Returns: 13

  91. 100

    {12, 10, 1 }

    {12, 11, 100 }

    Returns: 104

  92. 180

    {50, 20, 10 }

    {30, 17, 9 }

    Returns: 116

  93. 743

    {5, 1, 1, 2, 3, 1, 2, 3, 1, 2, 3, 3 }

    {3, 1, 3, 3, 2, 1, 1, 2, 3, 2, 3, 2 }

    Returns: 372

  94. 1000

    {1, 99 }

    {100, 1 }

    Returns: 11

  95. 1000

    {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, 1, 1, 1, 1, 11, 1 }

    Returns: 1000

  96. 5

    {2, 3 }

    {90, 100 }

    Returns: 190

  97. 11

    {3, 5 }

    {3, 5 }

    Returns: 11

  98. 999

    {97, 98, 97, 98, 99, 97, 98, 97, 98, 99, 97, 98, 97, 98, 99, 97, 98, 97, 98, 99 }

    {93, 97, 98, 97, 98, 99, 97, 98, 97, 98, 99, 97, 98, 97, 98, 99, 97, 98, 97, 98 }

    Returns: 1023

  99. 1000

    {9 }

    {9 }

    Returns: 1008

  100. 999

    {99, 1 }

    {1, 100 }

    Returns: 11

  101. 1000

    {100, 99 }

    {2, 1 }

    Returns: 11

  102. 1000

    {1, 100, 50 }

    {1, 100, 50 }

    Returns: 1000

  103. 1000

    {99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 }

    {99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 }

    Returns: 1089

  104. 111

    {10, 7 }

    {30, 28 }

    Returns: 354

  105. 1000

    {99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 }

    {55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55 }

    Returns: 605

  106. 1

    {10, 2, 3 }

    {3, 2, 1 }

    Returns: 1

  107. 4

    {2, 3 }

    {3, 4 }

    Returns: 6

  108. 9

    {5, 7, 4 }

    {4, 3, 2 }

    Returns: 5

  109. 5

    {100 }

    {100 }

    Returns: 100

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: