존은 정렬 알고리즘을 매우 좋아합니다. 그는 퀵 정렬, 병합 정렬, 기수 정렬 등을 연구했습니다.
오래전 그는 록-프리(lock-free) 병렬 문자열 정렬 프로그램을 작성했습니다. 이는 버스트 정렬과 다중 키 퀵 정렬의 조합이었습니다. 버스트 정렬을 구현하려면 버킷 트리(tree of buckets)를 만들어야 합니다. 각 입력 문자열에 대해 트리를 탐색하고 문자열의 일부를 올바른 버킷에 삽입합니다. 버킷이 채워지면 "버스트(bursts)"되어 새로운 서브트리(새로운 버킷 포함)가 됩니다.
(그림 참조)
그림 G.1: 버스트 정렬 데이터 구조
과거 이야기는 이쯤 하고, 오늘 존은 다시 정렬 알고리즘을 가지고 놀고 있습니다. 이번에는 숫자입니다. 그는 "익스트림 정렬(extreme sort)"이라는 새로운 알고리즘에 대한 아이디어를 가지고 있습니다. 이 알고리즘은 매우 빠르며, 성능 수준은 9000을 넘어섭니다. 그는 누구에게도 자세한 내용을 말하기 전에, 이 알고리즘이 올바르게 작동하는지 확인하고 싶어 합니다.
당신의 임무는 그를 돕고, 알고리즘의 첫 번째 단계 후에 소위 **익스트림 속성(extreme property)**이 유지되는지 확인하는 것입니다. 익스트림 속성은 min(xi,j)≥0으로 정의됩니다. 여기서,
xi,j=aj−ai (단, 1≤i<j≤N)
xi,j=9001 (그 외의 경우)
입력
첫 번째 줄에는 단일 정수 N (1≤N≤1024)이 포함됩니다.
두 번째 줄에는 N개의 정수 a1,a2,…,aN (1≤ai≤1024)이 포함됩니다.
출력
주어진 입력에 대해 익스트림 속성이 유지되면 "yes"를, 그렇지 않으면 "no"를 한 줄로 출력합니다.
seoulin1234 1년 전
문제
존은 정렬 알고리즘을 매우 좋아합니다. 그는 퀵 정렬, 병합 정렬, 기수 정렬 등을 연구했습니다.
오래전 그는 록-프리(lock-free) 병렬 문자열 정렬 프로그램을 작성했습니다. 이는 버스트 정렬과 다중 키 퀵 정렬의 조합이었습니다. 버스트 정렬을 구현하려면 버킷 트리(tree of buckets)를 만들어야 합니다. 각 입력 문자열에 대해 트리를 탐색하고 문자열의 일부를 올바른 버킷에 삽입합니다. 버킷이 채워지면 "버스트(bursts)"되어 새로운 서브트리(새로운 버킷 포함)가 됩니다.
(그림 참조)
그림 G.1: 버스트 정렬 데이터 구조
과거 이야기는 이쯤 하고, 오늘 존은 다시 정렬 알고리즘을 가지고 놀고 있습니다. 이번에는 숫자입니다. 그는 "익스트림 정렬(extreme sort)"이라는 새로운 알고리즘에 대한 아이디어를 가지고 있습니다. 이 알고리즘은 매우 빠르며, 성능 수준은 9000을 넘어섭니다. 그는 누구에게도 자세한 내용을 말하기 전에, 이 알고리즘이 올바르게 작동하는지 확인하고 싶어 합니다.
당신의 임무는 그를 돕고, 알고리즘의 첫 번째 단계 후에 소위 **익스트림 속성(extreme property)**이 유지되는지 확인하는 것입니다. 익스트림 속성은 min(xi,j)≥0으로 정의됩니다. 여기서,
xi,j=aj−ai (단, 1≤i<j≤N) xi,j=9001 (그 외의 경우)
입력
첫 번째 줄에는 단일 정수 N (1≤N≤1024)이 포함됩니다. 두 번째 줄에는 N개의 정수 a1,a2,…,aN (1≤ai≤1024)이 포함됩니다.
출력
주어진 입력에 대해 익스트림 속성이 유지되면 "yes"를, 그렇지 않으면 "no"를 한 줄로 출력합니다.