무지성 로봇청소기

NYPC 2021 · 본선

무한한 이차원 격자판에 하나의 로봇청소기가 있다.

일반적인 로봇청소기는 인공지능이 탑재되어 있어 지성을 갖고 청소를 한다. 하지만, 이 로봇청소기는 청소를 시작하면 기존에 탑재된 NN 개의 명령어를 무지성으로 차례대로 수행한 후 종료한다.

초기에 로봇청소기는 (0,0)(0, 0) 칸에 있다.

하나의 명령어는 (a,b)(a, b)의 형태로 나타낼 수 있다. 여기서, aa는 이동 방향, bb는 반복 횟수를 의미하며, 명령어는 "aa 방향으로 한 칸 이동하는 것을 bb 번 반복하라"라는 의미가 있다. aaU, D, R 중 하나이며, 각각 차례대로 위쪽(yy 좌표가 증가하는 방향), 아래쪽(yy 좌표가 감소하는 방향), 오른쪽(xx 좌표가 증가하는 방향)을 뜻한다.

로봇청소기에 탑재된 ii 번째 명령어는 (Ai,Bi)(A_i, B_i)이다.

여러분은 (0,0)(0, 0) 칸이 아닌 서로 다른 NN 개의 칸에 가구를 설치할 수 있다. 가구가 설치된 칸에는 로봇청소기가 이동할 수 없다. 따라서, 어떤 명령어를 수행하는 로봇청소기가 가구에 의해 더 이동할 수 없다면 그 칸에서 멈추게 되며, 이후의 명령어를 이어서 수행한다.

예를 들어, 세 칸 (0,2)(0, 2), (1,3)(1, -3), (2,0)(2, 0)에 가구가 설치되어 있고 N=3N = 3 개의 명령어가 차례대로 (U, 22), (R, 11), (D, 33)라면, 로봇청소기는 (1,2)(1, -2) 칸에서 청소를 마친다.

청소가 끝난 로봇청소기는 바로 충전을 해주어야 한다. 따라서, 로봇청소기가 청소를 끝마치는 칸과 충전기가 위치하는 칸은 동일해야 한다. 어떤 칸에 충전기를 놓을 수 있도록 하는 가구 배치가 존재하면, 그 칸을 충전 가능 칸이라 부르자.

로봇청소기에 탑재된 NN 개의 명령어가 주어질 때, 모든 충전 가능 칸의 개수를 세고, 입력으로 주어지는 칸이 충전 가능 칸인지 판별하는 프로그램을 작성하라.

입력 형식

첫 줄에 명령어의 수와 가구를 설치할 수 있는 칸의 수를 나타내는 정수 NN이 주어진다. (1N250000)(1 \le N \le 250\,000)

그다음 NN 개의 줄에 걸쳐 NN 개의 명렁어에 대한 정보가 차례대로 주어진다. 이 중 ii 번째 줄에 문자 AiA_i와 정수 BiB_i가 공백으로 구분되어 주어진다. AiA_iU, D, R 중 하나이며, 1Bi80001 \le B_i \le 8\,000이다.

그다음 줄에 충전 가능 칸인지 판별해야 하는 칸의 좌표를 나타내는 두 정수 XXYY가 공백으로 구분되어 주어진다. (X,Y2100000000)(|X|, |Y| \le 2\,100\,000\,000) 여러분은 (X,Y)(X, Y) 칸이 충전 가능 칸인지 여부를 판별하여야 한다.

출력 형식

첫 줄에 모든 충전 가능 칸의 개수를 출력한다.

만일, (X,Y)(X, Y) 칸이 충전 가능 칸이 아니라면, 둘째 줄에 NO를 출력한다.

(X,Y)(X, Y) 칸이 충전 가능 칸이라면, 둘째 줄에 YES를 출력한다. 이어서, 그다음 줄부터 NN 개의 줄에 걸쳐, (X,Y)(X, Y) 칸에 충전기를 놓을 수 있도록 하는 가구 배치를 출력한다. (x1,y1),,(xN,yN)(x_1, y_1), \cdots, (x_N, y_N) 칸에 가구를 배치했을 때 (X,Y)(X, Y) 칸에 충전기를 놓을 수 있다면, 이 중 ii 번째 줄에 두 정수 xix_i, yiy_i를 공백으로 구분하여 출력한다. (xi,yi2100000000)(|x_i|, |y_i| \le 2\,100\,000\,000)

어떤 칸이 충전 가능 칸이면, 위의 조건을 만족하는 가구 배치가 항상 존재함을 증명할 수 있다.

예제 1

입력

3 U 2 R 1 D 1 1 0

출력

7 YES 0 2 2 -1 2 2

예제 2

입력

3 U 2 R 1 D 1 0 2

출력

7 NO

예제 3

입력

2 R 1 R 1 2 0

출력

3 YES 0 1 0 -1

예제 4

입력

8 D 4 R 4 U 6 D 2 R 2 D 1 R 1 U 2 3 -1

출력

103 YES 1 1 3 -2 0 2 2 3 3 1 0 -3 1 -1 3 0

예제 설명

첫 예제에서 충전 가능 칸(0,1)(0, -1), (0,0)(0, 0), (0,1)(0, 1), (1,1)(1, -1), (1,0)(1, 0), (1,1)(1, 1), (1,2)(1, 2)로 총 77 개다.

채점 방식

각 데이터에 대해, 충전 가능 칸의 총 개수가 올바르면 4040%, (X,Y)(X, Y) 칸의 충전 가능 칸 여부와 배치가 올바르면 6060%의 점수를 얻을 수 있다.

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 8

N6;Bi10N \le 6; B_i \le 10

종류 2: 16

AiA_iU 또는 D.

종류 3: 10

AiA_iU 또는 R.

종류 4: 19

N2500;Bi=1N \le 2\,500; B_i = 1

종류 5: 7

N2500N \le 2\,500

종류 6: 17

Bi=1B_i = 1

종류 7: 23

추가적인 제한 조건이 없음.

해설