コンテンツにスキップ

フラクタル

タグ「フラクタル」の記事 1 件

SamCoding Round 9 (Div. 4) E - Carpet Pattern

レベル 00 の絨毯は黒いマス 1 個です。レベル nn の絨毯は、レベル n−1n - 1 の絨毯を 3×33 \times 3 に 9 個並べ、真ん中の 1 個だけを同じ大きさの真っ白な正方形に置き換えたものです(シェルピンスキーのカーペット)。レベル nn の絨毯は 3n×3n3^n \times 3^n になります。

レベル nn の絨毯の rr 行 cc 列のマスが黒か白かを答えるクエリが qq 個与えられます(1≤q≤1051 \le q \le 10^5、0≤n≤300 \le n \le 30、1≤r,c≤3n1 \le r, c \le 3^n)。黒なら #、白なら . を出力します。

行と列を 00 始まりにして、r,cr, c を 33 進数で見ます。

レベル nn の絨毯を 3×33 \times 3 のブロックに分けたとき、マス (r,c)(r, c) が入るブロックは、r,cr, c の 33 進数の一番上の桁(下から nn 桁目)で決まります。これが両方 11 なら真ん中のブロックなので白です。そうでなければレベル n−1n - 1 の絨毯の中にいるので、残りの桁で同じことを繰り返します。最後まで真ん中のブロックに入らなければ黒です。

つまり、r,cr, c の 33 進数の同じ桁がどちらも 11 になるところが 1 つでもあれば白、なければ黒です。どの桁から調べても結果は同じなので、下の桁から 33 で割った余りを見ていけば、11 クエリあたり O(n)O(n) で判定できます。

Python
for _ in range(int(input())):
N, R, C = map(int, input().split())
R -= 1
C -= 1
for _ in range(N):
if R % 3 == C % 3 == 1:
print(".")
break
R //= 3
C //= 3
else:
print("#")

for の else は、break せずにループが終わったとき、つまり両方 11 の桁がなかったときに実行されます。