시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 18 | 10 | 9 | 56.250% |
수평선 상에 N개의 점이 있다. N개의 점은 서로 다른 위치에 존재하며, 왼쪽부터 1번부터 N번까지의 번호가 붙어 있다. 각 점에는 색이 있어 i번 점의 색깔은 Ai이다. 당신은 두 점을 연결하는 선을 여러개 긋고 싶어한다. 그러나 점을 연결하는 선에는 다음과 같은 제한이 존재한다.
예를 들어, 아래와 같이 4개의 점이 있고 1, 2번 점은 붉은색, 3, 4번 점은 푸른색인 경우 1번 점과 4번 점, 2번 점과 3번 점, 2번 점과 4번 점 사이에 선을 연결하여 총 3개를 그을 수 있다.
선을 4개 그으려면 3가지 제한 중 적어도 하나 이상을 위반하게 되므로 이 경우 3개가 최대이다. 각 점의 색깔이 주어질 때, 어떤 제한도 위반하지 않으면서 두 점 사이를 연결하는 선을 최대한 많이 그리는 방법을 찾아 각 선이 어떤 두 점을 연결하는지 출력하라. 가능한 여러 방법이 존재하는 경우, 그 중 하나를 출력하면 정답으로 인정된다.
첫 줄에는 테스트 케이스의 개수 T(1≤T≤101)가 주어진다.
각 테스트 케이스의 첫 줄에는 집의 수 N과 색의 종류 M이 주어진다. (2≤N≤30,000, 2≤M≤N).
각 테스트 케이스의 둘째 줄에는 각 점의 색깔 A1,A2, ..., AN이 주어진다. (1≤Ai≤M).
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 C는 테스트 케이스의 번호이다.
그 다음 줄에는 두 점 사이를 연결하는 선의 최대 개수 K를 출력한다.
그 다음 K줄에 걸쳐 각 선이 연결하는 두 점의 번호를 출력한다.
3 4 2 1 1 2 2 4 2 1 2 1 2 3 3 1 2 3
Case #1 3 1 4 2 3 2 4 Case #2 4 1 2 1 4 2 3 3 4 Case #3 3 1 2 2 3 1 3
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 2: GP of ainta K번