Hotel
SRM 357 · 2007-07-12 · by ValD
SRM 357 · 2007-07-12 · by ValD · Simple Search, Iteration
Problem Statement
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.
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.
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
0)
10
{1,2,3}
{3,2,1}
Returns: 4
Just get 12 customers from the third city.
1)
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.
2)
12
{5, 1}
{3, 1}
Returns: 8
Get 10 customers from the first city, and 2 from the second city.
3)
100
{9, 11, 4, 7, 2, 8}
{4, 9, 3, 8, 1, 9}
Returns: 45
4)
99
{3,5,7,9,13,17}
{17,13,9,7,5,3}
Returns: 18
5)
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.
11)
1000
{99}
{100}
Returns: 1100
Largest return value.
13)
1000
{1}
{100}
Returns: 100000
Largestest return value :)
Submissions are judged against all 109 archived test cases, of which 8 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Hotel with a public method int marketCost(int minCustomers, vector<int> customers, vector<int> cost) · 109 test cases · 2 s / 256 MB per case