문제 설명
영화 '다이 하드 3'에서 브루스 윌리스와 새뮤얼 L. 잭슨은 다음과 같은 퍼즐 문제에 직면했다. 그들은 3갤런짜리 물통과 5갤런짜리 물통을 받았고, 5갤런짜리 물통에 정확히 4갤런을 채워야 했다. 이 문제는 그 퍼즐을 일반화하는 것이다.
당신에게는 두 개의 물통, A와 B가 있고 무한히 많은 물이 공급된다. 당신이 사용할 수 있는 행동에는 세 가지 종류가 있다:
(1) 물통을 채울 수 있고,
(2) 물통을 비울 수 있고,
(3) 한 물통에서 다른 물통으로 따를 수 있다.
한 병에서 다른 병으로 붓는 작업은 첫 번째 병이 비어 있거나 두 번째 병이 가득차는 것 둘 중 먼저 발생하는 시점에 중단된다. 예를 들어 A의 물통에 5갤런의 물이 들어 있으며 B의 물통에 6갤런이 들어 있으며, B 물통의 총 용량이 8갤런이라면 A에서 B로 물을 부으면 B는 가득 차고 A에는 3갤런이 남는다.
문제는 세가지 요소(Ca,Cb,N)가 제공된다. 여기서 Ca와 Cb는 각각 물통 A와 B의 용량이고, N은 목표이다. 해결책은 용기 B에 정확히 N갤런을 남기는 일련의 단계이다. 가능한 단계는 다음과 같다.
A를 채우다
B을 채우다
A를 비우다
B을 비우다
A를 B에 붓는다.
B를 A에 붓는다.
성공.
여기서 "A를 B에 붓는다"는 "A의 내용물을 B에 붓는다"를 의미하며, "성공"은 목표를 달성했음을 의미한다.
주어진 입력에는 반드시 해결책이 있다고 가정한다.
당신에게는 두 개의 물통, A와 B가 있고 무한히 많은 물이 공급된다. 당신이 사용할 수 있는 행동에는 세 가지 종류가 있다:
(1) 물통을 채울 수 있고,
(2) 물통을 비울 수 있고,
(3) 한 물통에서 다른 물통으로 따를 수 있다.
한 병에서 다른 병으로 붓는 작업은 첫 번째 병이 비어 있거나 두 번째 병이 가득차는 것 둘 중 먼저 발생하는 시점에 중단된다. 예를 들어 A의 물통에 5갤런의 물이 들어 있으며 B의 물통에 6갤런이 들어 있으며, B 물통의 총 용량이 8갤런이라면 A에서 B로 물을 부으면 B는 가득 차고 A에는 3갤런이 남는다.
문제는 세가지 요소(Ca,Cb,N)가 제공된다. 여기서 Ca와 Cb는 각각 물통 A와 B의 용량이고, N은 목표이다. 해결책은 용기 B에 정확히 N갤런을 남기는 일련의 단계이다. 가능한 단계는 다음과 같다.
A를 채우다
B을 채우다
A를 비우다
B을 비우다
A를 B에 붓는다.
B를 A에 붓는다.
성공.
여기서 "A를 B에 붓는다"는 "A의 내용물을 B에 붓는다"를 의미하며, "성공"은 목표를 달성했음을 의미한다.
주어진 입력에는 반드시 해결책이 있다고 가정한다.
입력 설명
입력은 세 개의 양의 정수 Ca, Cb, N 으로 구성된 한줄이다.
Ca와 Cb는 물통 A와 B의 용량이고 N은 목표이다.
0 < Ca <= Cb
N <= Cb <= 1000
A와 B는 서로 소이다.
Ca와 Cb는 물통 A와 B의 용량이고 N은 목표이다.
0 < Ca <= Cb
N <= Cb <= 1000
A와 B는 서로 소이다.
출력 설명
N갤런의 물이 담긴 B물통을 만들기 위한 명령의 출력이며, 마지막 줄은 반드시 success를 출력한다.
빈 줄이나 공백이 없어야 한다.
빈 줄이나 공백이 없어야 한다.
입력 예시 Copy
3 7 1
출력 예시 Copy
fill B
pour B A
empty A
pour B A
success