아름다운 화폐
시간 제한5초메모리 제한512 MB
증가하는 N개의 동전 값이 주어질 때, 각 값이 다음 값을 나누도록 새로운 양의 정수를 정하고 |a_i - b_i| / a_i의 최댓값을 최소화한다.
문제
KM 나라에는 N종류의 동전이 있고, 각 동전의 가치는 ai이다.
이 나라의 왕 Kita_masa는 현재 화폐 체계가 못마땅하다고 생각하여, 일부 동전(없을 수도 있음)의 가치를 바꿔서 화폐 체계를 아름답게 만들기로 했다.
화폐 체계가 아름답다는 것은, 각 동전이 정수 가치를 가지고 모든 i (1≤i≤N−1)에 대해 (i+1)번째로 작은 가치가 i번째로 작은 가치로 나누어떨어지는 것이다.
예를 들어 집합 1,5,10,50,100,500은 아름다운 체계로 간주되지만, 집합 1,5,10,25,50,100은 25가 10으로 나누어떨어지지 않으므로 아름답지 않다.
화폐 체계를 바꾸면 시민들이 혼란스러울 수 있으므로, 왕 Kita_masa는 혼란 비율의 최댓값을 최소화하고자 한다. 여기서 i번째 동전을 바꿀 때의 혼란 비율은 |ai−bi|⁄ai로 정의되며, ai와 bi는 각각 구조 변경 전과 후의 i번째 동전의 가치이다.
Kita_masa는 기존 각 동전의 가치는 바꿀 수 있지만, 새로운 동전을 도입하거나 기존 동전을 없앨 수는 없다. 변경 후에는 두 개 이상의 동전 가치가 같아질 수도 있다.
입력
각 데이터셋은 두 줄로 이루어진다. 첫 번째 줄에는 정수 N이 하나 주어지고, 두 번째 줄에는 N개의 정수 ai가 주어진다.
다음 제약 조건이 성립한다고 가정할 수 있다.
1≤N≤20
1≤a1<a2<…<aN<105
출력
혼란 비율의 최댓값의 최솟값을 나타내는 수 하나를 출력한다. 값은 소수점 이하 자릿수를 임의로 출력해도 되지만, 절대 오차가 10−8 이상이어서는 안 된다.