When you're a princess, you get to see a lot of frogs throughout the day and have to kiss one of them. But you can see only one frog at a time, and once you reject a frog you can't return to it. However, as soon as you kiss a frog, you're stuck with that prince for the rest of your life. So, how can you know when to stop hoping for the frog prince of your dreams and settle down with the frog you hold in your hands?
Gábor Székely writes in Paradoxes in Probability Theory and Mathematical Statistics (1986):
Surprisingly, there is a method which enables you to select the most handsome frog out of the $$n$$ frogs with a probability of nearly 37% even if $$n$$ is a large number, under the condition that you can see only one frog at a time, can only kiss a single frog and have to decide immediately whether or not to kiss the frog.
This is achieved using the following strategy. When you get to see a frog, you give it a rating $$s \in \mathbb{R}$$ ($$0 \leq s \leq 1$$) that indicates how handsome you value the frog. The higher the rating, the more handsome you value the frog. Let the first $$\left\lceil \frac{n}{e} \right\rceil$$ frogs go and then select the first one that has a higher rating than all of the previous candidates. If none are better, you have to kiss the last frog no matter how ugly or beautiful it is.
This strategy will give you a $$\frac{1}{e} \approx 37\%$$ chance to kiss the frog with the highest rating, no matter how large $$n$$ is. For example, assume there are 14 frogs in a forest. In that case, you only rate the first $$\left\lceil \frac{14}{e} \right\rceil = \left\lceil 5.15 \right\rceil = 6$$ frogs without kissing them. You then kiss the first frog having a higher rating than all of the first 6 frogs.
The first line contains a number $$n \in \mathbb{N}$$ ($$8 \leq n \leq 40$$) that indicates how many frogs there are. This is followed by the ratings $$s \in \mathbb{R}$$ ($$0 \leq s \leq 1$$) that are assigned to the $$n$$ frogs, each on a separate line.
The rating $$s$$ of the frog that will be kissed by the princess, if she follows the strategy as outlined above.
Input:
14
0.0056
0.7911
0.4679
0.3439
0.5503
0.5688
0.3085
0.9156
0.5654
0.2818
0.1636
0.4068
0.9669
0.1147
Output:
0.9156
One day a young man was walking down a road when a frog called to him
Boy, if you kiss me, I will turn into a beautiful princess.
The young man picked up the frog, smiled at it and put it in his pocket. A short while later, the frog said
Boy, if you kiss me and turn me back into a beautiful princess, I'll be yours.
The young man took the frog from his pocket, smiled at it and put it back. Now the frog was upset.
Boy, what is the matter?
the frog cried.
I have told you that I am a beautiful princess, and if you kiss me, I'll be yours!
The young man took the frog from his pocket, looked at it and said
Look, I'm an engineer. I have no time for a girlfriend, but a talking frog is cool!
Gaither CC (1999). Practically speaking: a dictionary of quotations on engineering, technology and architecture. CRC Press. ^{2}
Grimm J, Grimm W (1912). Household Tales by Brothers Grimm. J.M. Dent & Sons Ltd. ^{3}
Székely GJ (1987). Paradoxes in Probability Theory and Mathematical Statistics (Mathematics and its Applications). Springer. ^{4}