Wedding Planner

Julia is a wedding planner who puts together phantasmagorical

extravaganza packages for new couples and their guests from 2 to

2,000. Hundreds of items are needed for each event, and Julia has a list

of supplier offers for all these items in various quantities. The price per

unit of every item is highly variable, depending on the supplier, the

number ordered, and the client/buyer who places the order. With her

years of record-keeping, Julia knows the best unit price she can get for

any item in any of a limited number of order sizes. Some items cost less

per unit when the number ordered goes up, some cost less per unit

when the number ordered goes down, and others have no rhyme or

reason for the unit prices available.

To price a new event, Julia consults her database of past offers.

If the amount needed for the new event is exactly the same as the

amount in a past offer, the unit price is also the same.

If she has a price for a higher amount and a price for a smaller

amount, her best guess will be that the unit cost will be linearly

interpolated from the unit costs for the closest lower amount and

the closest higher amount.

If the database only has one amount, then her best guess is that this

will be her unit cost.

And, if the amounts for which she has offers are all smaller or all

larger than the amount she needs, then she finds it most accurate to

linearly extrapolate from the closest two points to the amount

needed.

Finally, sometimes price offers lapse. When this happens, Julia, who

is not very database savvy, just overwrites the old unit price with a

zero or negative number. The amounts associated with zero or

negative unit price need to be disregarded.

automated so she can do it for hundreds of items with thousands of

individual prices.

Complete the function extrapolate , which takes a new amount n, an

array amount of old offer amounts in increasing order, and an array

ucost of corresponding unit prices. Your completed function should give

the expected unit price p for the new amount. The unit prices may

increase, decrease or oscillate, and may also contain invalid values like

0 or negative numbers. Your answer, as well as the unit prices in the

second array, should all be real numbers with exactly two decimal

places, representing dollars and cents. Use standard rounding to arrive

at two decimal places.

Input

A positive integer n, denoting the number if items for which a unit

price is needed.

1.

An array amount of l positive integers denoting the different order

amounts for which historical unit costs exist.

2.

An array ucost of l strings of real numbers denoting the different

unit costs for the corresponding amounts in array a.

3.

Output

A single positive number p with exactly two decimal places.

Note that the code for processing input and output is already present in

the system and designed to be compatible with the test case files used

to score your solution. There is no need to change only of the code other

than the body of the function extrapolate.

Constraints

1 ≤ l ≤ 100

2 ≤ n <= 2000

size(a) = l = size(u)

a(i) < a(j) ⇔ i < j

1

2

3

4

5

n = 25

a = {10, 25, 50, 100, 500 }

u = {"2.46","2.58", "2", "2.25", "3" }

Sample Output #1:

p = 2.58

Explanation #1:

The amount 25 is one of the values in the database. Its corresponding

unit price is 2.58.

Sample Input #2:

n = 2000

a = {10, 25, 50, 100, 500 }

u = {"27.32", "23.13", "21.25", "18.00", "15.50"}

Sample Output #2:

6.13

Explanation #2:

The item count 2,000 is not in the database. It is larger than any amount

in the database. The closest two price points to it are 15.5 for 500 and

18.00 for 100. Linear extrapolation from these two points means

reducing the price by 2.5 for every increase in amount of 400. There 3.75

jumps of 400 from 500 to 2,000, or 4.75 jumps of 400 from 100 to

2,000. The unit price for 2,000 is therefore 15.5 - 2.5 × 3.75 or 18 - 2.5 ×

4.75. Both expressions evaluate to 6.125. This rounds up to 6.13.

#include

- Anonymous September 13, 2016