시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 1127 | 503 | 398 | 45.958% |
정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i < j)를 선택하고, 그 위치를 서로 바꿔준다. 이렇게 올바른 순서가 아닌 것을 도치(inversion)라고 하며, 도치의 개수는 최대 n(n-1)/2개이다.
현주는 사회에 대한 불만이 많은 아이이다. 그는 항상 정렬을 할 때, 두 원소를 선택하는 것에도 큰 불만을 가지고 있다. 현주는 ai > aj > ak와 i < j < k를 만족하는 세 원소를 선택한 뒤, ak, aj, ai로 순서를 바꾸려고 한다.
현주는 자신이 만든 정렬 알고리즘을 불만 정렬 알고리즘이라고 이름을 붙였다. 이제 이 알고리즘의 상한을 구하려고 한다. 현주가 선택할 수 있는 세 원소의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 수열의 길이가 주어진다. (1 ≤ n ≤ 105)
다음 줄에는 수열의 원소가 공백으로 구분되어 주어진다. 각 원소는 1보다 크거나 같고, n보다 작거나 같은 정수이다.
첫째 줄에 도치된 세 원소 (ai > aj > ak와 i < j < k를 만족하는 세 원소)의 개수를 출력한다.
4 3 3 2 1
2
3 1 2 3
0
ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2011 B번