만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

나무 심기

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

요약
격자에서 이웃 칸 수가 짝수인 칸 A개와 홀수인 칸 B개로 이루어진 연결된 칸 집합이 있는지 판별하고, 가능하면 배치를 출력합니다.
난이도

보통10점 중 6점

유형
구현, 수학
정답자
아직 제출이 없습니다

문제

승연이는 나무를 심으려 한다. 이를 위해 무한 격자 위에서 몇 개의 칸을 골라 나무 씨앗을 뿌린다. 나무 씨앗에는 신비한 힘이 있어, 주변 씨앗의 영향을 받아 사과나무 또는 복숭아나무 중 하나로 자란다.

변을 맞댄 두 칸에 각각 씨앗이 있으면 그 두 씨앗을 서로 인접하다고 한다. 인접한 씨앗의 수가 짝수인 씨앗은 사과나무가 된다. 인접한 씨앗의 수가 홀수인 씨앗은 복숭아나무가 된다.

변을 맞댄 두 칸에 들어있는 씨앗은 인접함

승연이가 위와 같이 5개의 씨앗을 심었다고 하자. 파란색 화살표는 서로 인접한 씨앗을 나타낸다. 가운데 씨앗은 3개의 씨앗과 인접해 있으므로 복숭아나무가 된다.

세 개의 사과나무와 두 개의 복숭아나무가 열린 모습

이 경우 3개의 사과나무와 2개의 복숭아나무가 열린다.

씨앗들은 격자에서 모두 연결되어 있어야 한다. 즉 임의의 두 씨앗에 대해, 인접한 씨앗만 거쳐서 두 씨앗 사이를 이동할 수 있어야 한다. 예를 들어 아래와 같은 배치는 불가능하다.

모든 씨앗이 연결되어 있지 않아 불가능한 배치의 예시

승연이는 사과나무 AA개, 복숭아나무 BB개를 심으려 한다. 이것이 가능한지 판단하고, 가능하다면 나무 배치를 출력하라.

입력

첫 줄에 음이 아닌 정수 AA와 BB가 공백으로 구분되어 주어진다. (A≥0A \ge 0, B≥0B \ge 0, 1≤A+B≤2001 \le A + B \le 200)

출력

첫 줄에 배치가 가능하면 YES, 불가능하면 NO를 출력한다.

배치가 가능하면 둘째 줄에 행의 수 RR과 열의 수 CC를 공백으로 구분해 출력한다. (1≤R,C≤2001 \le R, C \le 200)

셋째 줄부터 RR개의 줄에 걸쳐 각 줄에 CC개의 문자를 공백 없이 출력한다. 각 문자는 O 또는 .이며, 씨앗이 있는 칸에는 O, 없는 칸에는 .을 출력한다.

예제5

  1. 예제 1

    입력
    3 2
    
    예상 출력
    YES
    3 3
    .OO
    OOO
    ...
    
  2. 예제 2

    입력
    1 0
    
    예상 출력
    YES
    1 1
    O
    
  3. 예제 3

    입력
    7 0
    
    예상 출력
    YES
    3 3
    .OO
    OOO
    OO.
    
  4. 예제 4

    입력
    8 0
    
    예상 출력
    YES
    4 4
    ....
    .OOO
    .O.O
    .OOO
    
  5. 예제 5

    입력
    9 0
    
    예상 출력
    NO