PROBLEM STATEMENT
A radio station sells spots for advertisements. All spots are categorized by
their desirability, and each category is assigned a price. Customers buy
advertisement time by requesting a certain number of spots in a particular
category. Given the pricing information and the demand for spots in each
category, determine the amount of advertisement sales.
DEFINITION
Class name: RadioStation
Method name: sales
Parameters: String[]
Return type: int
Method signature: int sales(String[] categories) (make sure your method is
public)
Each String is formatted as follows (quotation marks are included for clarity
only)
"price count demand"
Each entry contains the data about a particular category of spots; price,
count, and demand are three integer values, separated by spaces. price
represents the price of one spot in this category. count represents the number
of spots in this category available during the day. demand is the number of
requests for this particular kind of a spot.
TopCoder will check that
- categories will contain 0 to 50 elements, inclusive
- price will be in the range from 100 to 10000, inclusive
- categories will be sorted on price in strictly descending order (all prices
will be different)
- count will be in the range from 1 to 100, inclusive
- demand will be in the range from 0 to 5000, inclusive
NOTES
* When the demand for a spot is higher than the number of available spots, the
difference between the demand and the number of available spots is called
excessive demand. It may be fulfilled by using spots from more expensive
categories. The excessive demand cannot be fulfilled by using spots from less
expensive categories.
* When the demand for a spot is lower than the number of available spots, the
remaining spots in the category become carry-over. The radio station uses
available carry-over to fulfill any excessive demand for cheaper spots.
Carry-over cannot be used to fulfill any excessive demand for more expensive
spots.
* When applying carry-over, the radio station considers excessive demand in the
order of decreasing price. For example, if there is a carry-over of 3 spots at
$1000, and excessive demand for 2 spots at $500, and 2 spots at $200, the
excessive demand for $500 spots is satisfied before excessive demand for $200
spots.
* When excessive demand exists after applying any carry-over from more
expensive spots, the radio station drops the remaining orders.
Your method should return the amount of money the radio station will get after
applying all the above rules.
EXAMPLES
- If categories={"1000 10 20", "500 20 25", "100 60 900"}, sales should return
10000+10000+6000=26000 (all excessive orders are dropped).
- If categories={"1000 10 5", "500 20 30"}, sales should return
5000+12500=17500 (five excessive orders from the $500 category aired during the
five vacant spots from the $1000 category).
- If categories={"1000 10 0", "500 20 0", "100 60 90"}, sales should return
9000 (all 90 spots are sold at $100, because there is no demand for $1000 and
$500 spots).
- If categories={"1000 10 0", "500 20 30", "100 60 90"}, sales should return
21000 (all 30 requests for $500 spots are satisfied, while the remaining 30
requests for $100 are dropped. This is because more expensive slots are
considered first for carry-over allocations).