★ solved.ac 난이도 : B3
(작성 시점 기준)
[문제 본문 링크]
11759번: Bottled-Up Feelings
The input consists of a single line containing three positive integers s v1 v2, where s ≤ 106 is the volume of the shipment, and v1, v2 ≤ 106 are the volumes of the two types of bottles, with v1 > v2.
www.acmicpc.net
★ 문제 번역
Peter는 대량의 연료유 선적을 기대하고 있지만, 작은 문제가 있습니다. (이 프로그래밍 문제에 있는 모든 사람이 그렇지는 않습니다!) 그가 가지고 있는 유일한 용기는 큰 병 세트(각각 부피가 동일함)와 작은 병 세트(각각 부피가 동일하지만 더 작은 병 세트)뿐입니다. 기름의 선적량을 고려할 때, 그는 병에 기름을 저장하기를 원합니다.
- 모든 기름이 저장됩니다,
- 각각의 병은 꼭대기까지 채워집니다,
- 그리고 최소한의 병이 사용됩니다.
Peter는 자신이 주어진 병 크기에 대해 이 문제를 해결했다고 생각하지만, 종종 자신의 병이 다른 부피를 가지고 있다면 어떤 일이 일어날지 궁금해하며 몇 시간을 보냅니다. (분명 Peter는 가장 신나는 삶을 살지 못합니다)
★ 입력 형식
3개의 양의 정수 s, v1, v2가 한 줄에 주어집니다. s는 선적량의 부피이고, v1과 v2는 두 종류의 병의 부피입니다.
- s, v1, v2 ≤ 10^6
- v1 > v2
★ 출력 형식
Peter의 두 조건을 만족하는 v1 크기의 병과 v2 크기의 병의 개수를 출력합니다. 조건을 만족하는 경우가 없으면 Impossible을 출력합니다.
★ 풀이
v1 크기의 병의 개수를 (s/v1)에서 점점 줄이면서 가능한 경우가 있는지 검사하면 됩니다. (코드를 참고해 주세요.)
[소스 코드 (C++98)]
공유 소스 보기
www.acmicpc.net
★ 틀린 점이 있다면 알려주세요~!