問題
길이가 N인 배열 A가 있다. 이 배열은 1, 2, 3 세 값으로만 이루어져 있다.
우리는 이 배열에서 다음 조건을 만족하는 세 인덱스의 순서쌍 (i, j, k)들을 최대한 많이 찾으려고 한다.
- 배열의 세 인덱스 i, j, k (0 ≤ i < j < k < N)에 대해서 A[i] = 1, A[j] = 2, A[k] = 3이거나, A[i] = 3, A[j] = 2, A[k] = 1이어야 한다. 단, 한 인덱스는 최대 한 개의 순서쌍에만 들어갈 수 있다.
예를 들어 A = {1, 2, 3, 2, 3, 1}이 주어졌다고 하자. 조건을 만족하는 답은 (0, 1, 4), (2, 3, 5) 가 된다. (A[0] = 1, A[1] = 2, A[4] = 3이고 A[2] = 3, A[3] = 2, A[5] = 1)
A가 주어졌을 때, 조건을 만족하는 순서쌍을 최대한 많이 찾아서 보고하는 프로그램을 작성하라.
여러분은 다음 함수를 작성하여야 한다.
void maximize( vector<int> A ) : A는 길이 N인 vector로, 1, 2, 3 세 값으로만 이루어 져 있다. maximize는 A에서 문제의 조건에 맞는 순서쌍 (i, j, k)들을 최대한 많이 찾아내고, 찾아낸 (i, j, k) 하나마다 grader의 answer(int i, int j, int k) 함수를 정확하게 한 번 호출한다. 최대 개수의 순서쌍들을 찾는 방법이 여러 가지인 경우 그 중 어떤 것을 찾아도 좋다. 또, 순서쌍들끼리의 호출 순서는 무시된다. 즉, 문제의 예에서는 answer(0, 1, 4)를 호출하고 answer(2, 3, 5)를 호출해도 되고, answer(2, 3, 5)를 호출한 후 answer(0, 1, 4)를 호출해도 된다.
輸入
작성한 코드는 입력과 출력을 받지 않아야 한다.
주어지는 grader는 다음과 같은 형식으로 입력을 받는다.
line 1 : N
line 2 : N개의 정수로 각각 1, 2, 3 중 하나
주어진 grader는 첫 줄에 maximize 함수가 answer(i, j, k) 함수를 호출한 횟수를 출력한 후, 각각의 answer(i, j, k) 호출마다 i, j, k 값을 한 줄에 출력한다.
1 <= N <= 15000
9점 : N <= 18
21점 : N <= 100
36점 : N <= 3000
34점 : 추가적인 제한 조건이 없음
範例
6
1 2 3 2 3 1
2
0 1 4
2 3 5
需要登入才能撰寫程式碼。