Greedy, Greedy.
시간 제한8초메모리 제한512 MB
각 동전 집합에 대해 모든 금액을 지불할 수 있는지와 그리디 알고리즘이 항상 최소 동전 수를 쓰는지 판정하고, 첫 번째 실패 원인이나 OK를 출력한다.
문제
옛날 어느 나라에 어리석은 왕이 살았다. 왕은 늘 즉흥적인 생각으로 일을 망치곤 했다. 이번에는 나라의 화폐 체계를 바꾸기로 마음먹었다. 지금 이 나라에는 1, 5, 25의 세 가지 동전이 있다. 왕은 이 동전들을 다른 동전 집합으로 바꾸려고 한다.
어제 왕은 7, 77, 777을 값으로 하는 동전 집합을 제안했다. "참 길한 숫자 같지 않느냐?"라고 왕은 말했다. 하지만 이 동전 집합으로는 예를 들어 10을 지불할 수 없다. 그래서 왕의 제안은 거부되었다.
오늘 왕은 1, 8, 27, 64를 값으로 하는 동전 집합을 제안했다. "모두 세제곱수구나. 얼마나 아름다우냐!" 하지만 또 다른 문제가 생겼다. 이 동전 집합으로 거스름돈을 효율적으로 만들려면 꽤 조심해야 한다. 값 40에 대한 거스름돈을 만든다고 하자. 그리디 알고리즘, 즉 끝에 도달할 때까지 계속 가장 큰 값의 동전을 고르는 방법을 쓰면 동전 일곱 개가 나온다. 값 27인 동전 하나, 값 8인 동전 하나, 값 1인 동전 다섯 개다. 그러나 값 40은 값 8인 동전 다섯 개로 만들 수 있고, 이쪽이 더 적다. 이런 비효율은 바람직하지 않으므로 왕의 제안은 다시 거부되었다.
내일이면 왕은 또 다른 제안을 할 것이다. 왕을 상대하는 데 시간을 쏟는 것은 아깝기 때문에, 위의 두 조건이 만족되는지 자동으로 검사하는 프로그램을 작성하자.
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 다음과 같은 형식으로 주어진다.
n c1 c2 . . . cn
여기서 n은 왕이 제안한 동전의 종류 수이고, 각 ci는 동전의 값이다.
1 ≤ n ≤ 50이고 0 < c1 < c2 < . . . < c**n < 1000이라고 가정할 수 있다.
입력은 0 하나로 끝난다.
출력
각 테스트 케이스마다 한 줄에 답을 출력한다. 답은 "Case #i: "로 시작한다. 여기서 i는 1부터 시작하는 테스트 케이스 번호이고, 그 뒤에 다음 중 하나가 온다.
- 주어진 동전 집합으로 지불할 수 없는 (양의 정수) 금액이 있으면 "Cannot pay some amount"
- 어떤 금액이든 지불할 수 있지만, 그리디 알고리즘으로 반드시 최소 개수의 동전을 쓰지는 않으면 "Cannot use greedy algorithm"
- 그 외의 경우에는 "OK"