삼색정리

시간 제한1초메모리 제한1024 MB

요약

상하좌우로 이웃한 칸이 같은 색이 되지 않도록 R개의 빨강, G개의 초록, B개의 파랑 칸으로 N행 M열 격자를 칠할 수 있는지 판정하고, 가능하면 한 가지 색칠을 출력한다.

난이도: 어려움10점 중 8점
유형: 그리디, 수학, 구현, 완전 탐색
정답자: 아직 제출이 없습니다

문제

다음 조건들에 부합하도록 $N$ 행 $M$ 열 격자판의 각 칸을 색칠해 보자.

빨간색 칸이 $R$ 개, 초록색 칸이 $G$ 개, 파란색 칸이 $B$ 개여야 한다.
상하좌우로 이웃한 두 칸의 색은 서로 달라야 한다.

입력

첫째 줄에 격자판의 행의 개수와 열의 개수를 각각 나타내는 정수 $N$ , $M$ 이 공백으로 구분되어 주어진다. $(2 \leq N, M \leq 2\\,000)$

둘째 줄에 사용 가능한 세 가지 색상의 개수 $R$ , $G$ , $B$ 가 공백으로 구분되어 주어진다. $(1 \le R, G, B \le N\times M;$ $R + G + B = N \times M)$

출력

주어진 조건에 맞게 격자판을 색칠할 수 있다면 첫째 줄에 YES, 불가능하다면 NO를 출력한다.

색칠할 수 있다면 다음 $N$ 줄에 걸쳐 색칠된 격자판을 출력한다. 그중 $r$ 번째 줄 $c$ 번째 문자로는 격자판의 $r$ 행 $c$ 열에 있는 칸이 빨간색이면 R, 초록색이면 G, 파란색이면 B를 출력한다. $(1 \le r \le N;$ $1 \le c \le M)$

가능한 방법이 여러 가지라면 그중 아무거나 출력한다.

예제4

예제 1
입력
```
2 3
1 3 2
```
예상 출력
```
YES
GBG
RGB
```
예제 2
입력
```
3 3
4 4 1
```
예상 출력
```
YES
RGR
GBG
RGR
```
예제 3
입력
```
3 4
4 4 4
```
예상 출력
```
YES
RGRB
GBGR
BRBG
```
예제 4
입력
```
2 3
4 1 1
```
예상 출력
```
NO
```