문제
연속된 정수들(n, n+1, n+2, ... , m)의 수열이 주어질 때, 안티프라임 수열은 이 정수들을 재배열하여 서로 인접한 정수 쌍 각각의 합이 합성수가 되도록(소수가 아니도록) 하는 수열이다. 예를 들어, n=1이고 m=10일 때, 1, 3, 5, 4, 2, 6, 9, 7, 8, 10은 이러한 안티 프라임 수열 중 하나이다. 또, 이것은 사전순으로 가장 앞서는 수열이다.
위의 정의를 확장하여, 연속하는 길이가 d인 부분 수열들의 합이 모두 합성수가 되는 수열을 d-안티프라임 수열이라고 하자. 위의 수열은 2-안티프라임 수열이지만, 부분 수열 5, 4, 2의 합이 11이 되므로 3-안티프라임 수열은 되지 않는다.
이들 숫자로 만들 수 있는 3-안티프라임 수열들 중에 사전식으로 가장 앞서는 수열은 1, 3, 5, 4, 6, 2, 10, 8 , 7, 9 이다.
입력
입력은 여러 개의 셋을 포함하고 있다. 각각의 집합에 대해 세 개의 정수 n, m(1≤n＜m≤1,000), d(2≤d≤10)가 한 줄에 주어진다. n=m=d=0일 때 입력의 끝을 나타내므로, 처리하지 않도록 한다.
출력
각각의 입력에 대해, 한 줄에 콤마로 구분된 정수의 리스트를 '한 줄에' 출력하라. 만약 한 가지 이상의 d-안티프라임 수열이 존재한다면, 사전식으로 가장 앞서는 수열을 출력하도록 한다. 만일 조건을 만족하는 어떤 수열도 존재하지 않는다면 "No anti-prime sequence exists."를 출력하라.
예제
1 10 2
1 10 3
1 10 5
40 60 7
0 0 0
1,3,5,4,2,6,9,7,8,10
1,3,5,4,6,2,10,8,7,9
No anti-prime sequence exists.
40,41,43,42,44,46,45,47,48,50,55,53,52,60,56,49,51,59,58,57,54
출처
2004 East Central Regional Contest B번
로그인해야 코드를 작성할 수 있어요.