PROG0322 - Hitchhikers problem
You are driving your car to the south of France, and you know that you will encounter $n$ hitchhikers along the way. Because you would rather have some company on this long and boring trip, you decide to take one of these hitchhikers with you. As the choice is completely yours, you prefer to take the most handsome (or the most sympathetic, the smartest, the richest, …). Since turning back is no option, for each of the hitchhikers you meet you will have to decide immediately whether you will take him or her, or test your luck hoping that you'll meet a more handsome hitchhiker further down the road.
You chose the following strategy before leaving in order to maximize your chance for picking the most handsome hitchhiker. Each time you encounter a hitchhiker, you immediately rate him or her with a score $s \in \mathbb{R}$ ($0 \leq s \leq 1$) that indicates how handsome the hitchhiker is. You skip the first $n / 2$ (integer division) hitchhikers, but you remember the highest score that you assigned to each of these hitchhikers. Then you stop for the first hitchhiker that is given a higher score than the highest score from the first $n / 2$ hitchhikers. You stop for the last hitchhiker, if you hadn't stopped for any of the other hitchhikers before.
For your information: It is easy to see that the above strategy yields at least 25% chance of picking the most handsome hitchhiker. The latter will be the case if the second most handsome hitchhiker is among the first half of the hitchhikers, and the most handsome hitchhiker is in the second half. This can even be improved slightly to $1/e = 0.36788$ by using essentially the same strategy, but switching to hitchhiker $n / e$ to start deciding whether you'll take him or her, or not.
Input
The first line of the input contains an integer $n \in \mathbb{N}$ ($1 \leq n \leq 1000$) that indicates the number of hitchhikers. This is followed by the scores $s \in \mathbb{R}$ ($0 \leq s \leq 1$) assigned to the $n$ hitchhikers, each on a separate line.
Output
The score $s$ of the hitchhiker that will finally be chosen if the above procedure is followed.
Example
Input:
19 0.2583 0.1580 0.4293 0.2299 0.2443 0.1043 0.0632 0.0363 0.1381 0.9899 0.3766 0.7932 0.7567 0.1048 0.9148 0.3787 0.7712 0.1390 0.4001
Output:
0.9899
Je vertrekt met de auto naar het zuiden van Frankrijk, en je weet dat je onderweg $n$ lifters zal tegenkomen. Omdat je graag wat gezelschap wil tijdens de lange autorit, beslis je om één van deze lifters mee te nemen. Als je dan toch mag kiezen, dan zou je er liefst ook de knapste (of sympatiekste, slimste, rijkste, …) uitpikken. Terugkeren is echter uitgesloten, dus moet je bij elke lifter onmiddellijk beslissen of je hem/haar zult meenemen dan wel of je het erop zult wagen om verder nog een knappere lifter tegen te komen.
Voor je vertrek heb je de volgende strategie uitgedokterd om met grote kans de knapste lifter op te pikken. Telkens je een lifter tegenkomt, geef je hem/haar ogenblikkelijk een score $s \in \mathbb{R}$ ($0 \leq s \leq 1$) die aangeeft hoe knap de lifter is. Hoe hoger de score, hoe knapper. De eerste $n / 2$ (gehele deling) lifters neem je niet mee, maar je onthoudt wel de hoogste score die je aan die lifters hebt gegeven. Daarna neem je de eerste lifter mee die een hogere score heeft dan de hoogste score van de eerste $n / 2$ lifters. Je neemt de laatste lifter mee, als je daarvoor nog geen lifter hebt meegenomen.
Ter info: Het is makkelijk in te zien dat bovenstaande strategie je 25% kans geeft om de knapste lifter mee te nemen. Dat laatste zal immers het geval zijn als de tweede beste lifter zich in de eerste helft van de lifters bevindt, en de beste lifter in de tweede helft. Het is zelfs mogelijk om de kans nog lichtjes te verbeteren tot $1/e = 0.36788$ door in grote lijnen dezelfde strategie te volgen, maar door vanaf lifter $n / e$ te beginnen beslissen of je hem/haar meeneemt of niet.
Invoer
De eerste regel van de invoer bevat een getal $n \in \mathbb{N}$ ($1 \leq n \leq 1000$) dat aangeeft hoeveel lifters er zijn. Daarna volgen de scores $s \in \mathbb{R}$ ($0 \leq s \leq 1$) die aan de $n$ lifters gegeven worden, elk op een afzonderlijke regel.
Uitvoer
De score $s$ van de lifter die uiteindelijk wordt meegenomen als de hierboven omschreven procedure gevolgd wordt.
Voorbeeld
Invoer:
19 0.2583 0.1580 0.4293 0.2299 0.2443 0.1043 0.0632 0.0363 0.1381 0.9899 0.3766 0.7932 0.7567 0.1048 0.9148 0.3787 0.7712 0.1390 0.4001
Uitvoer:
0.9899
| Added by: | Peter Dawyndt |
| Date: | 2013-02-05 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS