시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 222 | 64 | 41 | 30.597% |
앨버트는 공구점을 운영하는 친구로부터 1×2 크기의 타일을 매우 많이 받았다. 이 타일은 아래와 같이 가로로 긴 직사각형 형태이며, 두 개의 정사각형 칸이 '두 개' 이어 붙여져 있다.
마침 별장의 정원 발코니 바닥이 부서져서 수리하려던 참이라, 얻은 타일을 이용해 빈 공간을 채우려고 한다. 정원 발코니 바닥은 직사각형 모양이고, R×C개의 정사각형 칸으로 나누어져 있다. 아래 그림은 R = 4, C = 5인 경우이다. 1×2 타일을 이용하면 좌우로 인접한 두 칸을 완전히 덮어서 채울 수 있지만, 타일을 회전해서 상하 두 칸을 덮을 수는 없다.
칠해져 있는 칸은 부서지지 않은 칸, 칠해져 있지 않은 칸은 부서진 칸이다. 위의 그림에서는 6개의 칸이 부서지지 않은 칸, 14개의 칸은 부서진 칸이다.
이제, 부서진 칸을 1×2 크기의 타일만 가지고 채워 넣어야 한다. 크기가 1×2이기 때문에, 모든 칸을 채울 수 없을 수도 있지만, 최대한 많은 칸에 타일을 채워 넣으려고 한다.
타일은 부서진 칸 두 칸을 모두 덮어야 하고, 두 타일이 겹치면 안 된다. 또한, 발코니의 경계선을 넘어가도 안되고, 부서지지 않은 칸을 덮어도 안 된다.
위의 그림의 경우에 6개의 타일을 이용해서 부서진 칸을 최대한 많이 채울 수 있다. 모든 타일은 똑같이 생겨서 구분되지 않지만, 편의상 번호를 붙여 구분했다.
또 다른 두 가지 방법으로 아래와 같이 채우는 것도 가능하다.
별장 발코니 바닥을 채울 수 있는 방법의 수를 구하는 프로그램을 작성하시오. 두 방법이 있을 때, 적어도 한 칸에 대해서 한 방법에선 타일로 채웠고, 다른 방법에선 채우지 않은 경우가 있다면, 두 방법은 다른 방법이라고 한다.
첫째 줄에 별장 발코니의 크기 R, C와 부서지지 않은 칸의 개수 K가 주어진다. (1 ≤ R ≤ 1,000,000,000, 2 ≤ C ≤ 1,000,000,000, 0 ≤ K ≤ 1,000)
둘째 줄부터 K개의 줄에는 부서지지 않은 칸의 위치가 공백으로 구분해 주어진다. 위치는 행과 열의 번호로 나타낸다. 행은 1부터 R까지, 열은 1부터 C까지이다. 똑같은 위치가 여러 번 주어지는 경우는 없다.
적어도 하나의 타일을 놓을 수 있는 경우만 주어진다.
총 두 개의 수를 출력해야 한다. 첫 번째 수는 가장 많은 타일을 사용한 경우에 사용된 타일의 수, 두 번째 수는 그때 방법의 수이다. 단, 방법의 수가 매우 클 수 있기 때문에, 1,000,000,007로 나눈 나머지를 출력한다. 타일의 수는 항상 1018이하이기 때문에, 나누지 않아야 한다.
2 2 0
2 1
각 줄에 하나의 타일을 이용해서 채워야 하고 이 방법이 유일하다.
2 3 1 2 2
1 2
첫 줄은 타일 하나로 두 가지 다른 방법으로 채울 수 있고, 두 번째 줄은 채울 수 없다.
4 5 6 1 2 1 3 3 1 4 3 4 4 4 5
6 3
1000000000 1000000000 0
500000000000000000 1
1000000000 1000000000 2 324873289 23476755 99584832 4721222
499999999999999998 750063488