원문보기(http://online-judge.uva.es/p/v100/10090.html)
----
인기도:B(A,B,C), 성공률:낮음(낮음,보통,높음), 레벨:1(1~4)

About Marbles

나는 유리 구슬을 모으는데, 그 구슬들을 담아놓을 상자를 사려고 한다. 상자는 두 가지 유형으로 나눌 수 있다.

타입 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

Sample Output

~cpp 
13 1
failed

풀이

작성자 사용언어 개발시간 코드
문보창 C++ 5시간 Marbles/문보창
이동현 C++ 3시간 Marbles/이동현
신재동 C++ 45분 Marbles/신재동
조현태 C . Marbles/조현태

쓰레드

Retrieved from http://wiki.zeropage.org/wiki.php/Marbles
last modified 2021-02-07 05:23:45