EllysTicketPrices
TCO19 Round 1A · 2019-04-15 · by espr1t
Problem Statement
An airline is selling tickets for one of its flights. The ticket can be purchased during N consecutive days. On each day the price of the ticket is a constant, but it may change between days.
You are given the
Of course, since we are talking about real money, all prices are immediately rounded to two decimal places (i.e., cents). The usual rounding "to the nearest cent" is applied, with half a cent always being rounded up. Thus, X.424999 is rounded to X.42, while X.425 becomes X.43. Note that the rounding is applied after computing each price. For example, the price P3 is computed from the rounded value of the price P2.
The company wants to estimate the amount of money they will get for one ticket. For simplicity, they made the assumption that the ticket will sell on one of the N days, chosen uniformly at random. Thus, the expected price it will be sold for is (P1 + P2 + ... + PN) / N. Note that the calculated expected price is also rounded to cents.
Let's take a look at the following example. The airline is selling a ticket for 5 days with the changes in price between days being -10%, +15%, +5%, -20%. If the airline sets the initial price P1 to 200 euro, then the prices in each of the 5 days will be (200.00, 180.00, 207.00, 217.35, 173.88). The expected selling price will then be (200.00 + 180.00 + 207.00 + 217.35 + 173.88) / 5 = 195.65 euro. (Note that the actual expected price is 195.646, but it is also rounded to cents.)
In order to be profitable, the airline wants the expected price of the ticket to be target euro. (That is, exactly target.00 euro after the last rounding.) Now they wonder what initial price P1 they should set in order to achieve this goal. In the example above, if target is 180 euro, then the initial price P1 must be 184.01 euro. This way the price of the ticket in each of the days would be (184.01, 165.61, 190.45, 199.97, 159.98), whose average is 180.004 which rounds to the desired 180.00.
Elly recently started working at the airline. Now her task is to determine the initial price of the ticket P1 given N, C, and target. Return a floating point number rounded to exactly two decimal places - the initial price P1, that the company must use.
Notes
- Even though the return value is exact, due to the way floating point numbers work return values with an absolute or a relative error up to 10^(-9) will be accepted.
Constraints
- N will be between 2 and 100, inclusive.
- C will contain exactly N - 1 elements.
- Each element of C will be between -99 and +99, inclusive.
- target will be between 10 and 10,000, inclusive.
- It is guaranteed that the input will be such that there will exist a unique price P1 which gives the expected selling price target.
5
{-10, 15, 5, -20}
180
Returns: 184.01
The example from the problem statement.
11
{5, 16, 17, -3, -10, 20, 20, 14, 2, 0}
1337
Returns: 874.77
2
{0}
42
Returns: 42.0
With no change in the price, the answer should be obvious.
20
{30, -26, 87, 47, -39, 25, -67, 62, -38, 68, -84, 5, 28, -20, 50, -61, 10, 63, -71}
392
Returns: 476.28
50
{-60, 61, 17, 86, 56, 27, 9, 41, -27, -36, 57, -16, 1, 50, -55, -36, 14, 13, -93, 14, 18, 25, 62, -18, 40,
79, 56, 19, 10, -55, -43, 45, -43, -84, 61, -64, 41, -55, 38, 18, 36, -43, 79, 33, 87, 19, -47, 38, -56}
8887
Returns: 9451.93
Submissions are judged against all 123 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysTicketPrices with a public method double getPrice(int N, vector<int> C, int target) · 123 test cases · 2 s / 256 MB per case