원문보기(http://online-judge.uva.es/p/v100/10090.html)
----
인기도:B(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:1(1~4)
나는 유리 구슬을 모으는데, 그 구슬들을 담아놓을 상자를 사려고 한다. 상자는 두 가지 유형으로 나눌 수 있다.
타입 1: 하나에 c1 달러며 정확하게 n1개의 구슬을 담을 수 있다.
타입 2: 하나에 c2 달러며 정확하게 n2개의 구슬을 담을 수 있다.
각 상자에는 정확하게 주어진 용량만큼의 구슬을 집어넣을 것이며, 총비용은 최소한으로 줄였으면 한다. 여러 상자에 구슬을 나눠 담는 가장 좋은 방법을 찾아보자.
Input ¶
입력 파일에는 테스트 케이스가 여러 개 들어갈 수 있다. 각 테스트 케이스는 정수 n(1 이상 2,000,000,000 이하)이 들어있는 줄로 시작한다. 그 다음 줄에는 c1과 n1이, 그 다음 줄에는 c2와 n2가 입력된다. 여기에서 c1, c2, n1, n2는 모두 양의 정수며 2,000,000,000보다 작다.
구슬의 개수를 입력하는 자리에 0이 들어오면 입력이 종료된다.
Output ¶
입력에 있는 각 테스트 케이스에 대해 비용을 최소화할 수 있는 해법을 출력한다(한 줄에 테스트 케이스 하나씩). 해법이 있으면 두 개의 음이 아닌 정수 m1, m2를 출력한다. 이때 mi는 타입 i인 상자의 개수를 의미한다. 해가 없으면 "failed"를 출력한다.
해가 존재하면 그 해가 유일한 해라고 가정해도 된다.
Sample Input ¶
~cpp
43
1 3
2 4
40
5 9
5 12
0