Unlikely events P96116
Xavier Martínez (also known as Greivax, el colló dret de la foscor,
and Xavi P.) is one of the biggest nerds of the history of the UPC
programming teams. Recently, Xavi has married, which can be considered
a rather unlikely event. But this is not the first time that something
unexpected happens to Xavi. For instance, he qualified for his first
ICPC Final when his team solved a problem at the very last second, somehow
managed to survive the travel to China (see picture to the right),
qualified for a second ICPC Final solving almost nothing at the corresponding
regional contest, later was hired by one of the world top companies
(which against all odds has not collapsed yet), etc.
Let’s solve a problem inspired by this sequence of unlikely events: Given the independent probability of each event to happen, choose any subset of elements so that the probability of all them happening is as small as possible. To make the problem interesting, you are not allowed to choose any adjacent events.
Input
Input consists of several cases, each with the number of events n, followed by n simplified fractions ni/di. Assume 1 ≤ n ≤ 200, 2 ≤ di ≤ 6, and 1 ≤ ni < di.
Output
For each case, print the minimum probability of a subset of non-adjacent events, as a fraction with no common factors.
Public test cases
Input
1 3/4 3 1/2 5/6 2/3 5 1/2 3/5 5/6 1/3 1/4 5 5/6 1/3 3/5 4/5 1/5 8 1/6 1/6 1/5 1/6 1/6 1/5 1/5 1/5 7 1/4 1/4 1/4 1/4 1/4 1/4 1/4
Output
3/4 1/3 5/48 1/15 1/900 1/256
Information
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++