생산 라인의 시험 운전표

문제

한 공장의 생산 라인은 시험 운전에서 두 가지 작업 모드를 사용할 수 있다. 첫 번째 모드를 한 번 실행하면 부품 A개가 나오고, 두 번째 모드를 한 번 실행하면 부품 B개가 나온다. 각 모드는 정해진 작업을 끝까지 실행해야 하므로 실행 횟수는 음이 아닌 정수여야 한다. 시험 운전에서는 두 모드의 실행 횟수를 합하여 최대 K번까지만 실행할 수 있다. 담당자는 목표 생산량 T개에 최대한 가까운 시험 운전표를 만들려고 한다. 첫 번째 모드를 x번, 두 번째 모드를 y번 실행하는 운전표의 생산량은 A×x+B×y개다. 목표보다 적게 생산하는 운전표와 많이 생산하는 운전표를 모두 허용한다. 운전표의 오차는 생산량과 목표 생산량의 차이의 절댓값이다. 따라서 목표보다 3개 적게 생산하는 경우와 3개 많이 생산하는 경우의 오차는 모두 3이다. 운전표는 다음 우선순위에 따라 하나를 선택한다. 먼저 오차가 가장 작은 운전표를 고른다. 그러한 운전표가 여러 개라면 전체 실행 횟수 x+y가 가장 작은 것을 고른다. 오차와 전체 실행 횟수까지 같다면 첫 번째 모드의 실행 횟수 x가 가장 작은 것을 고른다. 이 기준을 모두 적용하면 선택되는 x와 y는 유일하다. 모드를 실행하는 순서는 고려하지 않으며 실행 횟수만 비교한다. 아무 모드도 실행하지 않는 운전표도 허용한다. 이때 x와 y는 모두 0이고 생산량도 0이다. 따라서 어떤 입력에서도 가능한 운전표가 적어도 하나 존재한다. 두 모드의 한 번당 생산량이 서로 같아도 모드 번호와 동점 처리 기준은 그대로 유지된다. 주어진 생산량과 실행 제한을 바탕으로 선택되는 두 실행 횟수와 그 운전표의 오차를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 A, B, T, K가 공백으로 구분되어 주어진다.
1 ≤ A, B ≤ 10,000, 0 ≤ T ≤ 2,000,000, 0 ≤ K ≤ 200이다.
가능한 운전표의 실행 횟수 x, y는 정수이며 x ≥ 0, y ≥ 0, x+y ≤ K를 만족해야 한다.

출력

선택된 운전표의 첫 번째 모드 실행 횟수 x, 두 번째 모드 실행 횟수 y, 오차를 공백으로 구분하여 한 줄에 출력한다. 동점이면 전체 실행 횟수가 작은 운전표를 우선하고, 그래도 같으면 x가 작은 운전표를 우선한다.

4 7 19 4

3 1 0

5 5 8 2

0 2 2

9 14 20 0

0 0 20

출처: Devin.KR 자체 제작