아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

카페

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

요약
n×m 격자에 의자 k개를 정확히 놓되 모든 의자가 8방향 이웃 중 하나에서 탁자와 맞닿게 하고, 불가능하면 불가능을 출력한다.
난이도

보통10점 중 6점

유형
그리디, 구현, 완전 탐색, 수학
정답자
아직 제출이 없습니다

문제

여름 카페는 n×mn\times m칸 크기의 직사각형 모양이고, 각 칸에는 탁자나 의자가 놓일 수 있다.

카페에서 kk명을 위한 연회를 열려고 한다. 이를 위해 정확히 kk개의 의자를 놓되, 각 의자에 인접한 칸(세로, 가로, 대각선 방향으로 이웃한 칸) 중 하나에는 탁자가 있어야 한다. 카페 관리자가 이 문제를 해결하도록 돕거나, 불가능하다면 불가능함을 알려라.

입력

입력 파일에는 세 수 nn, mm, kk가 주어진다. (1≤n,m≤501 \le n, m \le 50, 1≤k≤100001 \le k \le 10000)

출력

출력 파일에는 연회를 위한 탁자와 의자의 배치 계획을 mm글자씩 nn줄에 걸쳐 출력한다. h는 의자, T는 탁자, .은 빈 칸을 나타낸다. 해가 없으면 Impossible을 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    3 4 8
    
    예상 출력
    hhh.
    hTTh
    .hhh
    
  2. 예제 2

    입력
    2 2 4
    
    예상 출력
    Impossible