Description

Life can be simple. You can explore the mysteries of the underwater world, discover strange new organisms, or embark on a fresh journey. Before you must face challenges or compete with nearby creatures for survival, enjoy the freedom of flight. At such moments, life feels wonderful.

Like how snakes enjoy eating plankton (oh, I seem to have forgotten to tell you this common fact), each day you can eat some basic organisms around you and then gain an energy ring on your tail. You will have many different kinds of energy rings, each assigned an energy value. You can possess multiple rings of the same kind, but for a newly obtained ring of the same kind, its energy cannot be greater than that of any energy ring you already possess. Apart from the above rule, the probability of obtaining a new ring’s kind is uniform. Day by day, you accumulate more energy and begin to evolve.

But you have your own problems. Sometimes you face the evil jellyfish. It chases and bites you, so you must throw away the energy ring with the smallest energy value and then hurriedly escape. On such a day, you will have no appetite and thus will not gain any energy ring. Fortunately, when you have no energy rings, the jellyfish will not chase you even if it sees you, and you can then enjoy your meal.

You have heard that when your total energy exceeds a certain threshold, you can evolve into a powerful mode and even eat the jellyfish. It is time to fight back! Here is the question: how many days are expected to pass before you evolve into the powerful mode? (On the first day, you are assumed to have no energy rings.)

Input Format

The input contains multiple test cases. Each test case consists of two lines.

• The first line contains a floating-point number P, an integer T, and an integer N. P is the probability of encountering the jellyfish on a given day, and T is the threshold.
• The second line contains N distinct positive integers, representing the energy value of each kind of energy ring.

Each day proceeds independently. If you encounter the jellyfish and you currently have at least one ring, you discard the ring with the smallest energy and do not gain any ring that day. If you have no rings, the jellyfish will not chase you, and you proceed to gain one ring that day. When you gain a ring, its kind is chosen uniformly at random among the N kinds. You may obtain duplicates of the same kind.

Output Format

For each test case, output one line with the expected number of days until your total energy strictly exceeds the threshold, rounded to three decimal places.

0.5 0 1
1
0.5 1 2
1 2

1.000
2.000

Hint

Constraints: For all testdata, $0.1 \le P \le 0.9$, $1 \le T \le 50$, $1 \le N \le 50$.

Translated by ChatGPT 5