TopCoder problem "TeleportAndLoader" used in SRM 217 (Division I Level Three)



Problem Statement

    The year 2100. Your company is located in a huge skyscraper. The company purchased new equipment that has been dropped off at the entrance to your building at level 0. It is a number of boxes. Each box has been assigned to a floor in the building (several boxes may be assigned to one floor). You have to deliver the boxes to their respective floors. To facilitate this, you may use a teleporter. A teleporter can move any number of boxes to any floor for a fixed price, regardless of the number of items or their destination. To help you move the boxes, you can use loaders along with teleporters. Loaders can move boxes from any level to any other level (up or down), but the cost is proportional to the number of boxes moved and the difference between the current and destination levels (so, moving 2 boxes from level 10 to level 20 will cost you the same price as moving one box from level 10 to level 30, and half as much as moving 2 boxes from level 30 to level 50).

You will be given a int[] boxes, an int teleport_cost and an int loader_cost. The ith element of boxes gives you the level to which the ith box must be delivered. teleport_cost gives you the cost of one teleportation, and loader_cost gives you the cost for moving one box one level up or down using a loader. You must return the cheapest cost for delivering all the boxes.

For example: boxes = {1000, 40, 50, 10}

teleport_cost = 200

loader_cost = 10

One optimal way (there are many) to deliver these boxes is:

1. Teleport box number 0 to level 1000 - 200 units.

2. Teleport boxes 1 and 2 to level 40 - 200 units.

3. Move box number 2 from level 40 to level 50 - 10*10 = 100 units.

4. Move box number 3 from level 0 to level 10 - 10*10 = 100 units.

The total cost is 600 units, so your method should return 600.
 

Definition

    
Class:TeleportAndLoader
Method:cheapTransportation
Parameters:int[], int, int
Returns:int
Method signature:int cheapTransportation(int[] boxes, int teleport_cost, int loader_cost)
(be sure your method is public)
    
 

Constraints

-boxes will contain between 1 and 50 elements, inclusive.
-Each element of boxes will be between 1 and 1000000 (106), inclusive.
-loader_cost and teleport_cost will be between 1 and 1000000 (106), inclusive.
 

Examples

0)
    
{1, 2, 3, 4, 5}
10000
1
Returns: 15
Teleporting is too expensive. Use a loader.
1)
    
{1000, 40, 50, 10}
200
10
Returns: 600
The example from the problem statement.
2)
    
{1, 10, 254, 987, 1000000}
1
1000
Returns: 5
A loader is too expensive. Use a teleport.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5863&pm=3004

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming