Unlikely events P96116


Statement
 

pdf   zip

thehtml
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++