EllysTickets
TCO17 Round 1C · 2017-03-31 · by espr1t
Problem Statement
The public transportation system in her town has ticket prices which depend on how close to the last station you buy the ticket. A ticket can be bought at any of the stations. We assume the girl has enough time to buy the ticket while the train has stopped at any of the stations.
You are given a
Elly knows that her train is always checked by a single conductor. Every day the conductor boards the train at some station i and checks everyone's tickets while the train rides between stations i and i+1. The conductor chooses the number i uniformly at random from the set {0, 1, ..., n-1}. In other words, the conductor randomly chooses one of the n segments of the railroad.
You are given an
Elly wants to minimize the expected cost of her trip. Find out which ticket she should purchase (if any), and return the optimal expected cost of her trip.
Notes
- Your return value must have an absolute or a relative error smaller than 1e-9.
- Please note that if the girl buys a ticket at station X and the conductor boards at the same station, she will not be fined, since she will have a ticket when he checks her before the next station.
Constraints
- ticketPrice will contain between 1 and 50 elements, inclusive.
- Each element of ticketPrice will be between 1 and 1000, inclusive.
- The ticket prices in ticketPrice will be non-increasing.
- fine will be between 1 and 1000, inclusive.
{8, 5, 3}
10
Returns: 6.666666666666667
One possible strategy for Elly is to buy the ticket from her home (station 0) to the center of the city (station 3). This ticket costs 8 dollars. As she is guaranteed not to be fined, this is also the expected cost of her trip. However, the optimal strategy is to ride the first segment without a ticket and then to buy the ticket from station 1 to station 3. With this strategy the probability that she will be fined is 1/3: she will get a fine if and only if the conductor boards the train at station 0. Thus, with probability 1/3 she will pay the 10 dollar fine and with probability 2/3 she will pay 5 dollars for the ticket. This means that the expected cost of this strategy is 1/3 * 10 + 2/3 * 5 = 20/3 = approximately 6.667 dollars.
{50, 40, 30, 20, 10}
42
Returns: 33.2
It is obvious that Elly should not buy the ticket at station 0: the fine is cheaper than this ticket. The optimal strategy for this test case is to buy the ticket at station 3. If Elly does so, she will be fined with probability 60%, but she will only pay $20 if she isn't fined.
{999, 888, 777, 666, 555, 444, 333, 222, 111}
42
Returns: 42.0
Here the fine is so low, it is best to not buy a ticket at all.
{13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13}
17
Returns: 13.0
In this case apparently it doesn't matter where you buy the ticket. Thus, it is optimal to buy it at station 0 and avoid the chance of being fined.
{951, 924, 908, 907, 889, 880, 870, 810, 770, 731, 716, 713, 687, 677,
650, 645, 608, 598, 556, 472, 470, 446, 446, 410, 401, 352, 337, 337,
226, 191, 189, 183, 176, 173, 168, 148, 100, 92, 84, 57, 41, 17}
344
Returns: 296.6428571428571
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysTickets with a public method double getPrice(vector<int> ticketPrice, int fine) · 136 test cases · 2 s / 256 MB per case