BOJ 22899-22908 Orange Cup¶
https://www.acmicpc.net/category/detail/2745
아직 다 안 풀었기 때문에 푼 문제만 작성합니다.
BOJ 22899 오렌지컵 출제하기¶
BOJ 22901 ko_orange¶
BOJ 22904 오렌지 수¶
BOJ 22906 장난감 오렌지 만들기¶
BOJ 22907 오렌지 키우기¶
BOJ 22908 브루와 오렌지 나누기¶
서브태스크 3¶
A의 모든 원소가 다를 경우 X+Y는 그냥 i<j인 (i, j)의 개수, 즉 N(N-1)/2와 같기 때문에, X와 Y로부터 N이 유일하게 결정됩니다. 이제 Y는 무시하고 반전의 개수가 X인 순열을 만들면 됩니다.
서브태스크 2¶
X <= N(N-1)/2인 최소의 N을 잡읍시다. 그러면 N(N-1)/2-X는 i<j이면서 A[i] = A[j]인 (i, j)의 개수와 같습니다. 이는 각 x에 대해, 수열에 들어있는 x의 개수를 k라고 할 때, k(k-1)/2의 합과 같습니다.