TopCoder problem "MonthlyPayment" used in SRM 314 (Division I Level Three)



Problem Statement

    

Byterland Mobile, a mobile phone service provider, normally charges 10 cents per SMS (text message). In addition, it also offers monthly packs, which let you purchase a certain number of SMSs each month at a special price. You may purchase any number of these packs. If you exceed the number of SMSs covered by your monthly packs, the excess messages are charged at the normal rate.

You expect to send totalSMS SMSs each month, and you would like to minimize your monthly payment. There are two monthly packs available. The first pack costs pay1 cents and includes pack1 messages, and the second pack costs pay2 cents and includes pack2 messages. You may purchase any combination of these packs. Remember that it is sometimes cheaper to buy more SMSs than you actually need (see example #2). Return the minimal monthly payment in cents.

 

Definition

    
Class:MonthlyPayment
Method:minimalPayment
Parameters:String, String, String, String, String
Returns:long
Method signature:long minimalPayment(String totalSMS, String pack1, String pay1, String pack2, String pay2)
(be sure your method is public)
    
 

Notes

-For technical reasons, we cannot use long parameters, so we are using Strings instead.
 

Constraints

-totalSMS will be an integer between 0 and 1012, inclusive, with no extra leading zeroes.
-pack1, and pack2 will each be an integer between 1 and 1012, inclusive, with no extra leading zeroes.
-pay1 and pay2 will each be an integer between 1 and 1013, inclusive, with no extra leading zeroes.
-pay1 will be less than or equal to 20 * pack1.
-pay2 will be less than or equal to 20 * pack2.
 

Examples

0)
    
"92"
"10"
"90"
"20"
"170"
Returns: 790
The first pack offers 10 messages for 90 cents, and the second pack offers 20 messages for 170 cents. You want to buy 92 messages, so you choose one of the first pack and four of the second pack. You will pay for the remaining 2 messages at the normal rate of 10 cents each. The total price is 90 + 170*4 + 10*2 = 790 cents.
1)
    
"90"
"10"
"90"
"20"
"170"
Returns: 770
2)
    
"99"
"10"
"90"
"20"
"170"
Returns: 850
We can buy five of the second pack. The total number of SMSs covered by the purchased packs exceeds 99, but this is the cheapest way.
3)
    
"10"
"1"
"11"
"20"
"300"
Returns: 100
Packs do not lead to a cheaper way in this case.
4)
    
"0"
"10"
"80"
"50"
"400"
Returns: 0
5)
    
"28"
"1"
"10"
"1"
"8"
Returns: 224
6)
    
"450702146848"
"63791"
"433956"
"115281"
"666125"
Returns: 2604279739220
7)
    
"45"
"6"
"12"
"7"
"14"
Returns: 90

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6464

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9994&pm=6464

Writer:

zhuzeyuan

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev

Problem categories:

Greedy, Simple Math