4241번 - 소수 없는 수열 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 85 | 26 | 22 | 37.288% |
문제
n부터 m까지 숫자가 연속되어 있는 수열 n,n+1,n+2,...,m이 주어졌을 때, 이 수열의 수의 위치를 적절히 바꿔서 인접한 수의 합이 모두 소수가 아닌 수열을 소수 없는 수열이라고 한다. 예를 들어, n=1, m=10일 때, 1,3,5,4,2,6,9,7,8,10은 소수 없는 수열 중 하나이고, 그러한 수열 중 사전순으로 가장 앞서는 수열이다.
여기서 d차 소수 없는 수열은, 연속된 2,3,...,d개의 합이 모두 소수가 아닌 수열이다. 위에서 예로 든 수열은 2차 소수 없는 수열이다. 하지만, 5, 4, 2의 합이 11이 되고, 이 수는 소수이므로 3차 소수 없는 수열은 아니다. 3차 소수 없는 수열 중 사전순으로 가장 앞서는 것은 1,3,5,4,6,2,10,8,7,9이다.
n, m, d가 주어졌을 때, 사전순으로 가장 앞서는 d차 소수 없는 수열을 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, m, d가 공백으로 구분되어져 있다. n, m, d는 1 ≤ n < m ≤ 1000, 2 ≤ d ≤ 10을 만족한다. 입력의 마지막 줄에는 0 0 0이 주어진다.
출력
각 테스트 케이스에 대해서, d차 소수 없는 수열을 콤마(,)로 구분해서 출력한다. 만약 그러한 수열이 여러개일 경우에는 사전순으로 가장 앞서는 것을 출력한다. (즉, 첫째 수가 가장 작은 수열, 같을 때는 두 번째 수가 작은 수열, ....) 만약, d차 소수 없는 수열이 없는 경우에는 "No anti-prime sequence exists."을 출력한다.
예제 입력 1
1 10 2 1 10 3 1 10 5 40 60 7 0 0 0
예제 출력 1
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
출처
ICPC > Regionals > North America > East Central North America Regional > 2004 East Central Regional Contest B번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호