별 프랙탈 카펫
실버 III의견: 0
양탄자 장인 별이는 별 프랙탈 카펫을 짠다. 차수가 \(K\) 인 카펫은 \(3^K \times 3^K\) 크기의 격자이며 다음과 같이 만들어진다.
-
전체 정사각형을 똑같은 크기의 \(3 \times 3\) 개의 정사각형으로 나눈다.
-
한가운데(아홉 칸 중 가운데) 정사각형을 통째로 비운다.
-
남은 여덟 개의 정사각형 각각에 대해 같은 과정을 재귀적으로 반복한다.
이 과정을 \(K\) 단계까지 진행한다. \(K\) 단계 동안 한 번도 '한가운데'에 걸리지 않고 끝까지 살아남은 칸을 별(#)이라 하고, 어느 단계에서든 한가운데에 들어가 비워진 칸을 빈칸(.)이라고 한다.
행과 열은 \(0\)번부터 시작한다. 즉 \((0,0)\) 은 가장 왼쪽 위 칸이고 \((3^K-1,\ 3^K-1)\) 은 가장 오른쪽 아래 칸이다.
예를 들어 \(K=1\) 이면 \(3\times3\) 격자에서 한가운데 칸 \((1,1)\) 하나만 빈칸이고 나머지 여덟 칸은 모두 별이다. \(K=2\) 이면 \(9\times9\) 격자가 되며 시에르핀스키 카펫과 같은 무늬가 나타난다.
카펫의 차수 \(K\) 가 주어지고, 이어서 \(Q\) 개의 질의로 칸 \((r, c)\) 가 주어진다. 먼저 카펫 전체의 별의 개수를 출력하고, 그 다음 각 질의에 대해 그 칸이 별인지 빈칸인지 판정하라.
\(0 \le K \le 37\)
\(1 \le Q \le 100{,}000\)
\(0 \le r, c < 3^K\)
(\(K=0\) 이면 격자는 \(1\times1\) 이고 유일한 칸 \((0,0)\) 은 별이다.)
첫째 줄에 카펫의 차수 \(K\) 와 질의의 개수 \(Q\) 가 공백으로 구분되어 주어진다 (\(0 \le K \le 37\), \(1 \le Q \le 100{,}000\)).
다음 \(Q\) 개의 줄에는 각각 두 정수 \(r\), \(c\) 가 주어진다 (\(0 \le r, c < 3^K\)). 이는 판정할 칸의 행과 열이다.
첫째 줄에 차수 \(K\) 카펫에 있는 별의 총 개수를 출력한다.
이어서 각 질의에 대해 한 줄씩, 그 칸 \((r, c)\) 가 별이면 YES, 빈칸이면 NO 를 출력한다.
1 3
0 0
1 1
2 2
8
YES
NO
YES
\(K=1\) 일 때 카펫은 \(3\times3\) 격자이며 한가운데 칸 \((1,1)\) 하나만 빈칸이다. 전체 별의 개수는 \(8^1=8\).
\((0,0)\) → 별, \((1,1)\) → 빈칸, \((2,2)\) → 별.
2 4
4 4
0 4
1 1
8 8
64
NO
YES
NO
YES
\(K=2\) 일 때 카펫은 \(9\times9\) 격자이고 별은 \(8^2=64\) 개다.
\((4,4)\) 는 가장 큰 중앙 블록 안이라 빈칸, \((0,4)\) 는 윗 가운데 블록의 그 블록 안 중앙이라 빈칸, \((1,1)\) 은 좌상단 블록의 중앙이라 빈칸, \((8,8)\) 은 어느 단계에서도 중앙에 걸리지 않아 별이다.
riseoj 작성
출처 Original
평가 및 의견
별 프랙탈 카펫
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
별 프랙탈 카펫