/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 900 点
問題文
高橋君は、縦 N マス横 M マスのマス目を持っています。 次の条件をすべて満たすように、縦 1 マス横 2 マスのタイル A 枚と、縦 2 マス横 1 マスのタイル B 枚を マス目に置くことができるかどうかを判定し、可能なら置き方をひとつ構成してください。
- マス目の上に、全てのタイルを置かなければならない。
- タイルはマス目からはみ出してはならず、また異なるタイル同士が重なってはならない。
- マス目やタイルを回転させてはならない。
- 全てのタイルは、マス目のちょうど 2 マスを完全に覆う。
制約
- 1 \leq N,M \leq 1000
- 0 \leq A,B \leq 500000
- N,M,A,B は整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A B
出力
タイルを全て置くことができない場合、NO を出力せよ。
そうでない場合、以下のように出力せよ。
YES
c_{11}...c_{1M}
:
c_{N1}...c_{NM}
ただし、c_{ij} はマス目の i 行 j 列目の状態を表し、文字 .,<.>,^,v のいずれかでなければならない。
c_{ij} が、
.のとき、マス目の i 行 j 列目はタイルで覆われていないことを、<のとき、マス目の i 行 j 列目は縦 1 マス、横 2 マスのタイルの左半分で覆われていることを、>のとき、マス目の i 行 j 列目は縦 1 マス、横 2 マスのタイルの右半分で覆われていることを、^のとき、マス目の i 行 j 列目は縦 2 マス、横 1 マスのタイルの上半分で覆われていることを、vのとき、マス目の i 行 j 列目は縦 2 マス、横 1 マスのタイルの下半分で覆われていることを、
それぞれ表す。
入力例 1
3 4 4 2
出力例 1
YES <><> ^<>^ v<>v
縦 3 マス横 4 マスのマス目に、縦 1 マス横 2 マスのタイル 4 枚と、縦 2 マス横 1 マスのタイル 2 枚を置く方法の一例として、 出力例のようなものがあります。
入力例 2
4 5 5 3
出力例 2
YES <>..^ ^.<>v v<>.^ <><>v
入力例 3
7 9 20 20
出力例 3
NO
Score : 900 points
Problem Statement
Takahashi has an N \times M grid, with N horizontal rows and M vertical columns. Determine if we can place A 1 \times 2 tiles (1 vertical, 2 horizontal) and B 2 \times 1 tiles (2 vertical, 1 horizontal) satisfying the following conditions, and construct one arrangement of the tiles if it is possible:
- All the tiles must be placed on the grid.
- Tiles must not stick out of the grid, and no two different tiles may intersect.
- Neither the grid nor the tiles may be rotated.
- Every tile completely covers exactly two squares.
Constraints
- 1 \leq N,M \leq 1000
- 0 \leq A,B \leq 500000
- N, M, A and B are integers.
Input
Input is given from Standard Input in the following format:
N M A B
Output
If it is impossible to place all the tiles, print NO.
Otherwise, print the following:
YES
c_{11}...c_{1M}
:
c_{N1}...c_{NM}
Here, c_{ij} must be one of the following characters: ., <, >, ^ and v. Represent an arrangement by using each of these characters as follows:
- When c_{ij} is
., it indicates that the square at the i-th row and j-th column is empty; - When c_{ij} is
<, it indicates that the square at the i-th row and j-th column is covered by the left half of a 1 \times 2 tile; - When c_{ij} is
>, it indicates that the square at the i-th row and j-th column is covered by the right half of a 1 \times 2 tile; - When c_{ij} is
^, it indicates that the square at the i-th row and j-th column is covered by the top half of a 2 \times 1 tile; - When c_{ij} is
v, it indicates that the square at the i-th row and j-th column is covered by the bottom half of a 2 \times 1 tile.
Sample Input 1
3 4 4 2
Sample Output 1
YES <><> ^<>^ v<>v
This is one example of a way to place four 1 \times 2 tiles and three 2 \times 1 tiles on a 3 \times 4 grid.
Sample Input 2
4 5 5 3
Sample Output 2
YES <>..^ ^.<>v v<>.^ <><>v
Sample Input 3
7 9 20 20
Sample Output 3
NO