CellPhoneService
SRM 833 · 2022-07-08 · by misof
Problem Statement
You have decided to change your cell phone service provider.
In order to pick the best new one, you took your call log for the past month and the offers of all providers, and you decided to choose the one with whom you would have paid the least.
There are P service providers. In your data they are numbered from 0 to P-1.
You are given the following data:
int[] calls: for each call you made last month, its length in seconds.int P: the number of providers.int[] perMonth: for each provider p, perMonth[p] is the amount (in cents) you have to pay them once per month for their service.int[] perCall: for each provider p, perCall[p] is the amount (in cents) you have to pay them once each time you start a new call.int[] perMinute: for each provider p, perMinute[p] is the amount (in cents) you have to pay them during a call each time a new minute starts. (See the Examples for a more detailed explanation.)
For each provider, calculate the total amount you would pay them last month if they were your service provider. Return the minimum of the values you calculated.
Constraints
- calls will have between 0 and 50 elements, inclusive.
- Each element of calls will be between 1 and 3600, inclusive.
- P will be between 1 and 50, inclusive.
- perMonth, perCall and perMinute will have exactly P elements each.
- Each element of perMonth, perCall and perMinute will be between 0 and 10,000, inclusive.
{120, 121, 179}
1
{500}
{200}
{7}
Returns: 1156
You made three calls. The first was 120 seconds (i.e., exactly two minutes), the second was 121 seconds (2:01 in minutes) and the third was 179 seconds (2:59 in minutes). The only offer you have requires you to pay 500 cents per month, 200 cents per call, and 7 cents per each (possibly incomplete) minute of a call. Thus, the whole month would cost you: 500 cents for the monthly fee 200 + 7 + 7 cents for the first call (two full minutes) 200 + 7 + 7 + 7 cents for the second call (we started the third minute so we have to pay the third 7 cents) 200 + 7 + 7 + 7 cents for the third call (still within three minutes)
{234, 23, 65, 63, 164, 243, 45}
3
{400, 0, 700}
{100, 0, 300}
{20, 0, 40}
Returns: 0
The middle company (company #1) offers a free service.
{30, 47, 22, 118, 15, 3120, 180, 13, 212, 3180, 990, 42}
3
{1700, 0, 0}
{0, 200, 0}
{0, 0, 20}
Returns: 1700
Three companies. Company 0 expects a large monthly fee but then everything is free. Company 1 has no monthly fee, just a $2 payment for each call. Company 2 has no monthly fee and no fee per call, only $0.20 per each started minute of a call. The caller in this example made a lot of calls, some of them quite long. The cheapest option for them is to pay the monthly fee to company 0.
{3200, 1860, 2423}
3
{1700, 0, 0}
{0, 200, 0}
{0, 0, 20}
Returns: 600
The same three companies as in the previous example. This caller only makes a few calls per month but they tend to be long. Paying a fee per call is clearly the best option for them.
{30, 47, 22, 118, 15, 120, 180, 13, 212, 2}
3
{1700, 0, 0}
{0, 200, 0}
{0, 0, 20}
Returns: 340
The same three companies as in the previous two examples. This caller makes a lot of short calls. For this caller paying the monthly fee would be better than paying a fee per call, but an even better solution is to take the deal offered by company 2 and pay per minute.
{}
3
{123, 456, 789}
{9876, 5432, 1098}
{9876, 5432, 1098}
Returns: 123
We always have to choose one of the providers. With no calls made at all, the cheapest option is the one with the smallest monthly fee.
Submissions are judged against all 130 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CellPhoneService with a public method int payLeast(vector<int> calls, int P, vector<int> perMonth, vector<int> perCall, vector<int> perMinute) · 130 test cases · 2 s / 256 MB per case