Woburn Challenge 2016-17 Round 1 - Senior Division
Oh boy! It's Tricky's favourite time of year, Halloween! He can't wait to put on his awesome dinosaur costume and take a walk around his neighbourhood. Of course, what he's looking forward to the most are the loads of treats his neighbours are sure to give him!
Tricky lives at one end of a long street. There are other houses on the street, with the one being metres away from his own house. No two houses are at the same location. If Tricky visits the house and scares its residents with a fearsome dinosaur roar, he's sure to receive treats from them. Of course, he can only visit each house at most once, though.
Tricky would love to get as many treats as possible, but one thing may stand in his way - time! He absolutely must be home no later than midnight (that's when the real monsters come out). Fortunately, he may be getting quite a head start on his trick-or-treating expedition - he'll be leaving home milliseconds before midnight.
Despite his elaborate costume and the potential weight of many treats, Tricky can get around pretty quickly. He can walk down the street in either direction at a rate of 1 metre per millisecond. If he decides to stop at a house along the way to collect its treats, it'll take him milliseconds to do so before he can continue on his way.
Given that Tricky must be back in the safety of his house at the end of the street after no more than milliseconds of trick-or-treating, how many treats can he possibly end up with, and what's the probability of him developing long-lasting health issues as a result of the following excessive sugar consumption? (Just kidding, he'll be just fine!)
In test cases worth of the points, and .
In test cases worth another of the points, and .
In test cases worth another of the points, .
The first line of input consists of three space-separated integers ,
, and .
lines follow, with the of these lines consisting of two space-separated integers and (for ).
Output one line consisting of a single integer - the maximum number of treats that you can receive while still returning home by midnight.
4 2000 500 123 4 400 20 100 5 751 999
One optimal strategy is for Tricky to walk to the house, collect its treats, walk to the house, collect its treats, and then walk back home. This takes milliseconds, and yields a bounty of treats. If the house were metre closer to Tricky's house, then he would have just enough time to walk straight to it, collect its treats, and make it back home at midnight.