7481번 - ATM놀이 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 1035 | 120 | 85 | 28.333% |
문제
ATM에는 다른 종류 두 가지의 지폐가 굉장히 많이 있다. ATM에서 돈을 찾을 때 ATM은 예금주의 잔액을 넘지 않는 범위에서 정확한 양의 돈을 지급한다. 꿍은 지폐를 많이 들고다니고 싶지 않기때문에 되도록이면 가장 적은 수의 지폐를 들고다니고 싶어한다.
여러분은 가장 적은 수의 지폐로 꿍이 인출하려는 금액을 정확히 지급해주는 ATM을 만들어야 한다. ATM을 만들 때, ATM안에는 무제한으로 지폐가 들어있다고 가정해도 좋다.
입력
첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있으며 각 줄에는 a, b(ATM에 있는 지폐의 종류)와 S(꿍이 인출하려는 금액) 세개의 정수로 이루어져 있으며 공백으로 구분되어 있다.
출력
각 테스트케이스에 대해 ATM에서 인출되는 두 가지 지폐의 장수를 각각 출력한다. 만약 가능한 경우가 없다면 "Impossible" (따옴표 제외)이라고 출력한다.
제한
- 1 ≤ T ≤ 100
- 1 ≤ a, b ≤ 10000
- a ≠ b
- 0 ≤ S ≤ 109
예제 입력 1
3 1 10 23 3 2 7 4 6 2
예제 출력 1
3 2 1 2 Impossible
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호