문제
다각형의 삼각 측정은 다각형을 삼각형으로 나누는 정점사이의 선들을 적절히 긋는 것으로 구할 수 있다. 정점 사이의 선들은 다각형 내부에 있어야 하며 정점을 제외하고는 서로 만나지 않아야 한다.
아래 예를 보자.
위의 예에서 굵은 선은 다각형의 외곽선이고 가는 선은 삼각측정을 위하여 그은 정점사이의 선들이다.
K개의 정점을 가진 다각형에서 나올 수 있는 삼각형의 개수는 K-2개이다.
삼각측정을 위하여 간선을 적절히 그은 후 삼각형 개수 수열을 구할 수 있다. 위 예에서 다각형 A의 삼각형 개수 수열은 다각형의 맨 위 왼쪽 정점을 시작으로 시계방향으로 진행하면서 정점에서 만들어지는 삼각형의 개수를 나열하면 된다. 다각형 A, B, C의 삼각형 개수 수열을 만들어 보면 아래와 같다.
A : 1 3 1 3 1 3 B : 2 2 1 4 1 2 C : 1 2 3 2 1 6 1 2 3 2 1 6
N 개의 정수로 입력된 수열을 입력받아 삼각형 개수 수열로 가능한지, 불가능한지 판별하는 프로그램을 작성하시오. 가능하다면 구성된 삼각형을 사전편집상 순서로 출력하는 프로그램을 작성하시오.
입력
첫 행에 테스트 케이스의 수 T(1 ≤ T ≤ 5)가 입력된다. 두 번째 행에서부터 T개의 행에 걸쳐 각 테스트 케이스에 대한 정보가 입력된다. 각 테스트 케이스의 첫 번째 수는 정점이 개수 K(4 ≤ K ≤ 20)이다. 이어서 삼각형의 개수를 나타내는 K개의 정수가 입력된다. 각 행의 수들은 공백으로 구분된다.
출력
각 테스트 케이스에 대하여 불가능한 경우에는 행으로 구분하여 N을 출력한다. 가능한 경우 하나의 행에 Y를 출력하고 다음 행부터 K-2개의 행에 걸쳐 삼각형을 구성하는 노드의 번호 3쌍을 공백으로 구분하여 출력한다. 각행의 정점의 순서도 사전 편집상으로 정렬되어야 하며 각각의 행도 사전 편집상으로 정렬되어 출력되어야 한다.
예제
4
6 1 3 1 3 1 3
6 1 3 2 2 1 3
12 1 2 3 2 1 6 1 2 3 2 1 6
20 1 2 3 2 1 6 1 2 3 2 1 6 1 3 2 2 1 3 1 2
Y
1 2 6
2 3 4
2 4 6
4 5 6
N
Y
1 2 12
2 3 12
3 4 6
3 6 12
4 5 6
6 7 8
6 8 9
6 9 12
9 10 12
10 11 12
N
로그인해야 코드를 작성할 수 있어요.