나열에서 소트되지 않은 정도(unsortedness)는 각 문자사이에의 순서가 어긋나는 수로 판단할 수 있다.
예를 들어, 문자열 DAABEC 나열되지 않은 정도는(unsortedness) 는 5 이다. 왜냐하면 D 의 오른쪽에 있는 문자중 D 보다 작은 문자가 4 개 있고 E 는 한개 있어 합이 5.
이 측도를 나열에서의 반전할 수(number of inversions) 로 불린다.
``AACEDGG'' 의 반전의 수는 1 ( E 와 D) --- 거의 소트되어 있음 -- 반면에 ``ZWQM'' 의 6 의 inversion 을 가진다.( 이는 거의 소트되어 있지 않다 --- 정확이 역순으로 정렬되어 있다)
당신이 해야 할 일은 4 문자(A,C,G,T)로 이루어진 나열을 입력으로 받아 카탈로그화 하려고 하는데 단순히 알파벳 순서가 아니고 거의 소트 된 상태에서 거의 소트되지 않은 상태로 카탈로그화 하고 자 한다. 즉 반전의수가 작은 것 부터 큰 순으로 .
모든 문자열은 같은 길이를 가진다.
입력 10 6 AACATGAAGG TTTTGGCCAA TTTGGCCAAA GATCAGATTT CCCGGGGGGA ATCGATGCAT 출력 CCCGGGGGGA AACATGAAGG GATCAGATTT ATCGATGCAT TTTTGGCCAA TTTGGCCAAA
출처: East Central North America 1998