Checkout

PROBLEM STATEMENT

You are writing software for a new automated cashier system.  The customer
simply has to swipe each of his or her items and coupons and you must then
display for him or her the money he or she owes.

Create a class Checkout that contains a method price which will receive a list
of strings containing each of the items and coupons being purchased or used.
This method should return a string containing the actual dollar amount owed
using the optimum (that is: resulting in the highest savings and thus the
lowest final total cost) combination of the supplied coupons.  This amount must
include the dollar sign ('$'), exactly two decimal places, and no leading zeros
- except that a total of less than one dollar should still have a zero in the
dollars place.  For example, "$25.00" would correctly represent twenty-five
dollars and zero cents, and "$0.13" would correctly represent zero dollars and
thirteen cents (in both cases, quotes are included for clarity only).


DEFINITION
Class: Checkout
Method: price
Parameters: String[]
Returns: String
Method signature (be sure your method is public):  String price(String[] items);

Each element of items will be in one of the following three forms (quotes,
angle brackets, and square brackets are for clarity only - they are never part
of the strings):
1) "Item: <item> <cost>", meaning the customer is purchasing one of the item
<item> for cost <cost>.
2) "Coupon: <item1> <savings>", meaning the customer is using a coupon that
will save him or her <savings> if at least one of <item1> are purchased.
3) "Coupon: <item1> <item2> <savings>", meaning the customer is using a coupon
that will save him or her <savings> if at least one of <item1>, as well as one
of <item2>, are purchased.


TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- There will be between 1 and 20 elements (inclusive) in the list, including
both coupons and items being purchased.
- Elements of items will be between 1 and 50 characters in length, inclusive.
- Each element of items will be in one of the following three forms (quotes and
angle brackets are for clarity only - they are never part of the strings):
- 1) "Item: <item> <cost>" - each element is separated by exactly one space,
and there will be exactly one space after the colon (':').
- 2) "Coupon: <item1> <savings>" - each element is separated by exactly one
space, and there will be exactly one space after the colon (':').
- 3) "Coupon: <item1> <item2> <savings>" - each element is separated by exactly
one space, and there will be exactly one space after the colon (':').  Note
that <item1> and <item2> may be identical - meaning you need to buy two of that
item to get the coupon's savings.
- In each of the above forms, <item>, <item1> and <item2> will contain only
letters ('A'-'Z' and 'a'-'z', inclusive).
- In each of the above forms, <cost> and <savings> will be a number between 0
and 10000, representing the cost or savings in whole cents, with no fractions,
possibly with a number of leading zeros.


NOTES
- Only a maximum of one coupon can be used for each single item - they may not
overlap.
- Each coupon is only able to grant its savings once, but multiple identical
coupons can be used on different (identical) items.  In other words, if the
customer purchases twice the number of items needed for a coupon, another
identical coupon would be needed to get these savings again.
- Items are identical only if their names match exactly.  For example, "Shoes"
is a different item than "shoes", and both are different than "shoe".
- It is valid for two identical items to cost different amounts.
- It is not valid for a coupon to reduce the total price of the order below
zero, but a coupon CAN reduce the total cost by more than the item(s) it
applies to is worth.  See the first example below.
- Items listed in a "Coupon:" entry need not be present in an "Item:" entry.
If at least one is not, the coupon can not be used.


EXAMPLES

In each of these examples, quotes ('"') and parenthesis ('(' and ')') are
included for clarity only.  They are never part of the input or output.

Example #1)
items = {"Coupon: Shoes 1000", "Item: Shoes 200", "Item: Socks 300"}
return "$0.00"
As specified above, a $10.00-off coupon for "Shoes" on an order that consists
of "Shoes" for $2.00, and "Socks" for $3.00 will result in a total of $0.00,
not a negative number, and not $3.00.

Example #2)
items = {"Item: Shoes 1000", "Item: Shoes 1000", "Item: Socks 999", "Coupon:
Shoes 005", "Coupon: Socks 009", "Coupon: Shoes Socks 99"}
return "$28.95"
You need to use the first and third coupons.

Example #3)
items = {"Coupon: HotDog 2100"}
return "$0.00"
This customer didn't buy anything.

Example #4)
items = {"Item: HotDog 399", "Item: Fries 049", "Item: Drink 099"}
return "$5.47"
This customer used no coupons.