11737.ヒルベルト曲線

質問する

説明:

ヒルバート曲線は、次のように再定義されます.
∙最初のヒルバート曲線は、2×2メッシュ内のすべての点にアクセスする曲線で、(0,0)から右/下/左に順に移動します.
∙n≧2の場合、n次ヒルバート曲線は、2 n×2 nメッシュのすべての点にアクセスする曲線であり、(0,0)では、各2 n−1×2 n−1ローカルメッシュが右/下/左の順に移動する.グリッドの一部を移動するルールは次のとおりです.
左上隅メッシュは、n-1号ヒルバート曲線を右下角を基準に対称な形状です.右上隅のメッシュはn-1次ヒルバート曲線です.下部メッシュは、上部メッシュを水平軸対称に塗りつぶします.

入力

第1行は、試験例の数TCを与える.その後、TC個の試験例が新しい行に分割される.各テストケースは、次のように構成されています.
∙最初の行は整数n,a,bを与える.これは、n番目のヒルバート曲線で、a号家とb号家の距離を計算することを意味します.(1≤n≤15, 1≤a,b≤22n)

しゅつりょく

各テストボックスは1行、2点間の距離をメートル単位で出力します.整数でない場合は、最も近い整数を四捨五入する必要があります.

アイデア

順序を指定すると、座標の問題が規則的に表示されます.
一見鬼を利用して解決する問題ですが、アプローチは思ったより難しいです.
一般的にこのような時、私は手で例題を打ち込みます.
便宜上、ゼロから家の順番を表示させていただきます.
ex1. n=3 a = 16
まず、n=3の場合、0軒目から63軒目まで、16軒目を基準に除算する
左上隅グリッド0、
右上隅のグリッド1、
右下のグリッド2、
左下端グリッド3
に分けることができます.
16-32は右上コーナーグリッドなので、yに4を加えてn=2に移動します.
次の問題はn=2からa%16社の問題を検索することになります.
a=16なら
n=2~0家なので[0,0]を加えると,家の座標値は[0,4]となる.
ただし、aが0次グリッド、3次グリッドの場合、座標値は順次変更されます.
便宜上,最初のnを2として近づけた.
ex2-1. n = 2, a = 1

△悪筆ではすまない.
問題は、0番グリッドの最初の家を見つける方法です.
0番グリッドを無視すると、最初のセットは(0,1)になりますが、実際には(1,0)です.右上隅のグリッドを標準グリッドと呼ぶと、0番グリッドのxとyの座標値が変化する可能性があります.
ex2-2. n = 2, a = 12
3番グリッドの0番面の家を探しています.
0番目のセットは、標準では(0,0)ですが、この場合は(1,1)です.
3番目のグリッド(1-0,1-0)でいいです.もっと正確に言えば
標準(x,y)であれば(1−y,1−x)である.

整理する

n=nの場合,集合総数は2(2 N)2^{(2 N)}2(2 N)個である.
座標系は[2 N 2^{N}2 N,2 N 2^{N}2 Nとすることができる.
K=2(N√1)2^{(2(N−1)}2(N√1)は、1つのグリッドの家の数です.
a番目の家を探すとき、a/kは1番目の家がグリッドにある位置です.
a%Kはn=N−1で新たに検索されるaとなる.
n=Nにおけるaセットの位置が0番目のグリッドである場合、
n=n-1 a%kセット位置の標準座標値[x,y]を[y,x]に戻せばよい.
a家の位置が3番目のグリッドであれば、
まずxに2 N/22^N/22 N/2位置決めを加えます.
n=n-1、a%kセットの標準座標値を表す[x,y]
N−1は、最大座標[xmax,y max]−[y,x]を返します.
ちょっと混乱していますが、これはルールのようですね?そして何とかする.
手拍子の例を使って検証して、効果はとても良いです...

インプリメンテーション

def coor(n,a):
    if n == 0:
        return [0,0]
    k = 2**(2*(n-1))
    tmp_anw = [0,0]

    tmp_anw[0] += (a // k) // 2 * (k ** (1 / 2))
    if (a//k) == 1 or a//k == 2:
        tmp_anw[1] += (k**(1/2))

    y = coor(n-1,a%k)

    if a//k == 0:
        return [tmp_anw[0]+y[1],tmp_anw[1]+y[0]]
    elif a//k == 3:
        return [tmp_anw[0]+(k**(1/2)-1)-y[1],tmp_anw[1]+(k**(1/2)-1)-y[0]]
    else:
        return [tmp_anw[0]+y[0],tmp_anw[1]+y[1]]

def dis(a,b):
    return 10*((a[0]-b[0])**2 + (a[1]-b[1])**2)**(1/2)


T = int(input())
for t in range(1,1+T):
    n, a, b = map(int,input().split())

    # n = 1일떄 몇번째인가?
    a -= 1
    b -= 1

    coor_a = coor(n,a)
    coor_b = coor(n,b)

    print(f'#{t} {round(dis(coor_a,coor_b))}')

実行

入力

2 # Test Case Number
2 3 8 # N A번째 집 B번째 집
3 63 48 

しゅつりょく

[1.0, 1.0] [1.0, 2.0] # N=2에서 A번째 집, B번째 집 좌표
[7.0, 1.0] [7.0, 4.0]

よくわかりませんがよく撮れました

に感銘を与える

鬼を作るとき、n=Nからn=0までの鬼を思うと頭が痛い.
適当なN-N-1とNの間の規則(点火式を見つける)を見つけるだけです.
再帰が実現し,出力結果にエラーが表示された場合,どこでエラーが発生し,どのように修復されるかを考えることができる.