시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB297785324.424%

문제

BOJ 알고리즘 캠프의 스페셜 게스트 성원이는 캠프 참가자들에게 사탕을 만들어주려고 한다. BOJ 알고리즘 캠프의 참가자의 수는 N명이고, 0번부터 N-1번까지 번호가 매겨져 있다.

i번 참가자는 총 C[i] 리터의 사탕이 들어가는 바구니를 가지고 있고, 받고 싶은 사탕의 무게는 W[i] 그램이다.

성원이는 모든 참가자들의 바구니를 가득 채워줄 것이다 즉, C[i]리터만큼 모두 채울 것이다. 하지만, 성원이는 사탕을 한 종류만 만들 수 있다(밀도가 일정하다)

성원이는 되도록 많은 참가자를 만족시키는 밀도를 선택해야 한다. 최대한 많은 참가자를 만족시키게 하기 위해서, 각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합을 최소로 하려고 한다.

각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합을 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 참가자의 수 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄에는 C[i], 셋째 줄에는 W[i]가 주어진다. (1 ≤ C[i], W[i] ≤ 1,000,000)

출력

각 참가자의 W[i]와 실제로 받은 사탕의 무게의 차이의 합을 최솟값을 출력한다. 정답과의 절대/상대 오차는 10-9 까지 허용한다.

예제 입력 1

1
5
1000

예제 출력 1

0.0

예제 입력 2

2
10 10
1000 2000

예제 출력 2

1000.0

예제 입력 3

3
10 20 40
4000 2000 1000

예제 출력 3

5250.0

힌트

예제 1의 경우에 참가자가 1명이다. 밀도를 200그램/리터로 하면 W[i]와 실제로 받은 무게의 차이는 0.0이 된다.

예제 2의 경우에는 두 사람이 가지고 있는 사탕 바구니는 10리터인데, 한 사람은 1000그램을, 다른 한 사람은 2000그램을 받으려고 한다. 밀도 100그램/리터로 정하면 차이가 1000.0이 나게 만들 수 있다.

출처