주화 체계 S는 실제 혹은 가상의 화폐 체계에서, 액면가라고도 불리는 주화 가치를 나타내는 서로 다른 양의 정수의 (공집합이 아닌) 유한 집합입니다. 예를 들어, 캐나다에서 주로 쓰이는 주화 체계는 {1, 5, 10, 25, 100, 200}로 1은 1센트 주화를 나타내고 200은 200센트 (2달러) 주화를 나타냅니다. 임의의 주화 체계 S에서 각 액면가마다 동전은 무한하게 공급된다고 가정하며, 모든 양의 정수를 S의 값을 (반복해서라도) 사용해 나타낼 수 있음을 보장하기 위해 S는 1을 포함한다고 가정합니다.
전세계의 모든 계산원은 다음 문제를 직면(하고 해결)합니다: 주화 체계 S = {c1, c2, ..., cn}이 주어질 때, S가 표준인지 비표준인지 판정하라. S는 한 개의 반례, 즉, 정확히 x를 지불하기 위해 필요한 최소 동전의 수가 그리디 알고리즘을 통해 구한 동전의 수보다 작은 양의 정수 x가 존재할 경우 S는 비표준입니다. 비표준 주화 체계의 예로는 {1, 3, 4}가 있는데, 반례는 6으로 그리디 알고리즘을 통한 해는 4 + 1 + 1 (동전 3개)이지만 최적 해는 3 + 3 (동전 2개)입니다. (덱스터 코젠과 슈무엘 작스가 발견한) 유용한 사실이 있는데, S가 비표준일 경우 가장 작은 반례는 가장 큰 두 액면가의 합보다 작습니다.
입력
입력은 하나의 케이스입니다. 첫 줄에 주화 체계의 액면가 수를 나타내는 하나의 정수 n(2 <= n <= 100)이 주어집니다. 다음 줄에 n개의 액면가를 나타내는 공백으로 구분된 정수 c1 c2 ... cn이 주어지는데, c1 = 1이고 c1 < c2 < ... < cn <= 106이다.
출력
주화 체계가 표준일 경우 "canonical"을 출력하고, 비표준일 경우 "non-canonical"을 출력합니다.
ez_code 3년 전 2
문제
주화 체계 S는 실제 혹은 가상의 화폐 체계에서, 액면가라고도 불리는 주화 가치를 나타내는 서로 다른 양의 정수의 (공집합이 아닌) 유한 집합입니다. 예를 들어, 캐나다에서 주로 쓰이는 주화 체계는 {1, 5, 10, 25, 100, 200}로 1은 1센트 주화를 나타내고 200은 200센트 (2달러) 주화를 나타냅니다. 임의의 주화 체계 S에서 각 액면가마다 동전은 무한하게 공급된다고 가정하며, 모든 양의 정수를 S의 값을 (반복해서라도) 사용해 나타낼 수 있음을 보장하기 위해 S는 1을 포함한다고 가정합니다.
전세계의 모든 계산원은 다음 문제를 직면(하고 해결)합니다: 주화 체계 S = {c1, c2, ..., cn}이 주어질 때, S가 표준인지 비표준인지 판정하라. S는 한 개의 반례, 즉, 정확히 x를 지불하기 위해 필요한 최소 동전의 수가 그리디 알고리즘을 통해 구한 동전의 수보다 작은 양의 정수 x가 존재할 경우 S는 비표준입니다. 비표준 주화 체계의 예로는 {1, 3, 4}가 있는데, 반례는 6으로 그리디 알고리즘을 통한 해는 4 + 1 + 1 (동전 3개)이지만 최적 해는 3 + 3 (동전 2개)입니다. (덱스터 코젠과 슈무엘 작스가 발견한) 유용한 사실이 있는데, S가 비표준일 경우 가장 작은 반례는 가장 큰 두 액면가의 합보다 작습니다.
입력
입력은 하나의 케이스입니다. 첫 줄에 주화 체계의 액면가 수를 나타내는 하나의 정수 n(2 <= n <= 100)이 주어집니다. 다음 줄에 n개의 액면가를 나타내는 공백으로 구분된 정수 c1 c2 ... cn이 주어지는데, c1 = 1이고 c1 < c2 < ... < cn <= 106이다.
출력
주화 체계가 표준일 경우 "canonical"을 출력하고, 비표준일 경우 "non-canonical"을 출력합니다.