시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1536 MB | 46 | 17 | 13 | 54.167% |
동규는 단면 PCB 회로를 설계하려고 한다. PCB 회로는 부품을 장착하는 곳인 패드와, 패드를 잇는 도선으로 구성된다. 회로를 그릴 PCB는 무한한 2차원 평면, 패드는 평면 위의 점, 도선은 평면 위에서 이어진 선분들로 생각할 수 있다.
동규가 설계하려는 회로에는 $2N$개의 패드가 수평 방향으로 나열되어 있다. 왼쪽에서 $i$번째에 위치한 패드의 좌표는 $(i-1, 0)$이다. 패드마다 $1$번부터 $N$번까지의 번호 중 하나가 붙어 있으며, 같은 번호를 가진 패드는 각각 두 개씩 존재한다.
동규는 번호가 같은 패드 쌍들을 서로 만나지 않는 도선들로 이어야 한다. 각 도선은 $x$축 또는 $y$축에 평행한 하나 이상의 선분이 차례로 이어져 있는 모양이고, 자기 자신과 교차하지 않아야 한다. 또한 도선을 구성하는 각 선분은 길이가 양의 정수여야 한다.
패드의 번호가 순서대로 주어졌을 때, 회로를 설계하는 프로그램을 작성하시오.
첫 번째 줄에 $N$이 주어진다. $(1 ≤ N ≤ 1,000)$
두 번째 줄에 패드의 번호를 나타내는 $2N$개의 정수가 순서대로 주어진다. $i$번째 정수는 왼쪽에서 $i$번째에 위치한 패드의 번호이다.
회로 설계가 불가능하다면 NO를 출력한다.
회로 설계가 가능하다면 첫 줄에 YES를 출력한 다음, 회로를 나타내는 $N$개의 줄을 출력한다. $i$번째 줄에는 $i$번 패드 둘을 잇는 도선을 출력한다. 도선의 시작점은 둘 중 왼쪽에 있는 패드, 끝점은 오른쪽에 있는 패드이며, 도선을 출력하는 형식은 다음과 같다.
또한 구성된 회로는 다음 조건을 만족해야 한다. 회로 설계가 가능하다면 아래 조건을 만족하는 회로가 존재함이 보장된다.
가능한 회로가 여러 가지라면 아무거나 하나만 출력한다.
4 1 2 3 4 1 2 3 4
YES 3 U 1 R 4 D 1 5 D 1 L 2 U 3 R 6 D 2 5 D 2 R 6 U 3 L 2 D 1 3 D 1 R 4 U 1
본문에 주어진 그림과 같이 회로 설계가 가능하다.
4 1 2 3 4 1 3 2 4
NO
패드를 어떻게 이어도 도선끼리 만나는 일이 생긴다.