농부 존은 세가지 사료(보리,귀리,밀)를 섞어서 소의 먹이로 사용하고 있다. 세 가지 종류의 비율이 주어질 때 이 세가지 비율의 곱의 합이 존이 원하는 사료의 비가 되게 하는게 문제이다. 가능한 곱 중에서 합이 최소로 하게 하여야 한다.
예를 들어 , 3:4:5 의 비율로 맞추어야 하고 세 가지 비율이 주어진다면
1:2:3
3:7:1
2:1:2
8*(1:2:3) + 1*(3:7:1) + 5*(2:1:2) = (21:28:35) = 7*(3:4:5)
목적 비율과 주어지는 비율은 음이 아닌 100 이하의 정수이고 , 곱해지는 수도 100 이하이고 , 배합의 비율은 서로 다른 비율
이다.
입력 3 4 5 1 2 3 3 7 1 2 1 2 출력 8 1 5 7
출처: 1998 ACM Finals