Problem #447
✰ - click to bookmark
★ - in your bookmarks
Tags:
unlabeled
For a given integer N, we will define a Product List to be any list of positive integers where the product of all integers in the list is
equal to N. The list can contain any number of integers and may contain duplicates. We are also interested in the sum of the integers in the
Product List. As an example, consider N = 36. Some of the Product Lists for N = 36 are shown below, together with the sum of their values.
{1, 2, 3, 6} 1 + 2 + 3 + 6 = 12
{2, 3, 6} 2 + 3 + 6 = 11
{3, 3, 4} 3 + 3 + 4 = 10
{6, 6} 6 + 6 = 12
{12, 3} 12 + 3 = 15
For the Product Lists shown above, the smallest sum is 10. This is actually the minimum sum that can be achieved for any Integer Product List
for N = 36.
If we allow the elements of the list to be rational numbers (fractions), rather than integers, then we can do slightly better than this.
Note that integers are also rational numbers so can still be used in this case. (for example 5 = 5/1) Consider the following Product List of
rational numbers which multiply to give 36.
{10/3, 19/6, 324/95}
10/3 x 19/6 x 324/95 = 36
10/3 + 19/6 + 324/95 = 1883/190 = 9.91 (rounded to 2 decimal places)
Not surprisingly, using rational numbers we can achieve a smaller sum than the minimum value for Integer Product Lists. However, 9.91 is not
the minimum for rational numbers. For N = 36 and a Rational Product List the minimum sum is 9.80 (rounded to 2 decimal places).
In this problem you will be given several integer numbers N. For each value of N you are asked to find the minimum sum for an Integer
Product List and the minimum sum for a Rational Product List. To facilitate factorisation you can assume that no value of N will contain any
prime factors greater than 20.
Input and Answer:
The first line of the problem will be a single integer T denoting the number of test cases. Each of the following T lines will hold a single
integer N. For each test case give the minimum sum for Integer Product Lists followed by a space and then the minimum sum for Rational
Product Lists. Combine all answers into a single string, separated by single spaces. All answers for the Rational Product List should be
rounded to 2 decimal places.
Example:
input:
2
36
2765070
answer:
10 9.80 60 40.32