기름을 병에 담기

두 병 용량으로 배송량을 정확히 채우는 병 수의 최소 조합을 구하고 없으면 Impossible을 출력합니다.

쉬움2완전 탐색수학면접 대비아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

피터는 연료유를 대량으로 들여오는데, 담을 그릇이 마땅치 않다. 가진 것이라고는 부피가 모두 같은 큰 병 여러 개와, 역시 부피가 모두 같으면서 큰 병보다는 작은 병 여러 개뿐이다. 기름의 총 부피가 주어지면 피터는 다음 세 조건을 모두 만족하도록 기름을 나눠 담으려 한다.

  1. 기름을 남김없이 담는다.
  2. 사용한 병은 모두 입구까지 가득 채운다.
  3. 사용하는 병의 개수를 최소로 한다.

피터는 지금 가진 병 크기로는 답을 구해 두었지만, 병 부피가 달라지면 결과가 어떻게 바뀌는지 궁금해한다. 기름의 총 부피와 두 병의 부피가 주어질 때 답을 구하라.

입력

첫째 줄에 양의 정수 ss, v1v_1, v2v_2가 공백으로 구분되어 주어진다. ss는 기름의 총 부피이고 s106s \le 10^6이다. v1v_1v2v_2는 각각 큰 병과 작은 병의 부피이며 v1106v_1 \le 10^6, v2106v_2 \le 10^6, v1>v2v_1 > v_2이다.

출력

세 조건을 모두 만족할 때 사용한 부피 v1v_1 병의 개수와 부피 v2v_2 병의 개수를 공백으로 구분해 한 줄에 출력한다. 조건을 만족하는 방법이 없으면 Impossible을 출력한다. 기름을 정확히 나눠 담는 방법이 여럿이어도 병의 개수가 최소인 방법은 하나뿐이므로 답은 유일하다.