Beautiful Currency
Time limit5sMemory limit512 MB
Given N increasing coin values, assign new positive integers so each value divides the next, minimizing the maximum relative change |a_i - b_i| / a_i.
- Level
Hard8 of 10
- Topics
- Binary search, Greedy, Dynamic programming, Number theory
- Solved
- No attempts yet
Problem
KM country has N kinds of coins and each coin has its value ai.
The king of the country, Kita_masa, thought that the current currency system is poor, and he decided to make it beautiful by changing the values of some (possibly no) coins.
A currency system is called beautiful if each coin has an integer value and the (i+1)-th smallest value is divisible by the i-th smallest value for all i (1≤i≤N−1).
For example, the set 1,5,10,50,100,500 is considered a beautiful system, while the set 1,5,10,25,50,100 is NOT, because 25 is not divisible by 10.
Since changing the currency system may confuse citizens, the king, Kita_masa, wants to minimize the maximum value of the confusion ratios. Here, the confusion ratio for the change in the i-th coin is defined as |ai−bi|⁄ai, where ai and bi are the value of the i-th coin before and after the structure changes, respectively.
Note that Kita_masa can change the value of each existing coin, but he cannot introduce new coins nor eliminate existing coins. After the modification, the values of two or more coins may coincide.
Input
Each dataset contains two lines. The first line contains a single integer, N, and the second line contains N integers, ai.
You may assume the following constraints:
1≤N≤20
1≤a1<a2<…<aN<105
Output
Output one number that represents the minimum of the maximum value of the confusion ratios. The value may be printed with an arbitrary number of decimal digits, but may not contain an absolute error greater than or equal to 10−8.