Product trees P30012


Statement
 

pdf   zip

html

Let a product tree be a binary tree such that every internal node is the product of its two children. For instance, these are some product trees with external nodes 1, 2, 3, 4 and 5:

[levelsep=25pt,treesep=12pt] 120 24 6 2 1 2 3 4 5           [levelsep=25pt,treesep=12pt] 120 1 120 60 3 20 5 4 2         [levelsep=25pt,treesep=12pt] 120 20 4 5 6 3 2 1 2

Let us define the cost of a tree as the product of all its nodes. For the trees above, the costs are 120 * 24 * 5 * 6 * 4 * 2 * 3 * 1 * 2 = 4147200, 120 * 1 * 120 * 60 * 2 * 3 * 20 * 5 * 4 = 2073600000, and 120 * 20 * 6 * 4 * 5 * 3 * 2 * 1 * 2 = 3456000.



Which is the minimum cost for a product tree, given a list of its external nodes?

Input

Input consists of a sequence of cases. Every case begins with n, followed by n real numbers between 1 and 10. Assume 1 ≤ n ≤ 1000. A special case with n = 0 ends the input.

Output

For every case, print a line with the minimum cost for a product tree with the given external nodes. Print only the integer part of the result. If the result has more than seven digits, print only its most significant seven digits. The input is such that the result always fits into a double, and such that there are no precission issues.

Public test cases
  • Input

    5   1 2 3 4 5
    1   7.8
    4   2 1 2 1
    4   10 10 10 10
    9   9.9 8.8 7.7 6.6 5.5 4.5 3.5 2.5 1.5
    0
    

    Output

    3456000
    7
    32
    1000000
    1604498
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Cinquè Concurs de Programació de la UPC - SemiFinal
    Date
    2007-09-19