[中譯] Projecteuler (287) Quadtree

[LPH66 ((short)(-15074))]

ProjectEuler (287) Quadtree

http://projecteuler.net/index.php?section=problems&id=287

所謂的 Quadtree 編碼可以將一個 2^N x 2^N 的黑白影像編成一系列的位元。

這個序列如下解讀:

* 第一個位元表示整個 2^N x 2^N 影像：
  * 若它是 0 則表示分割，將整個 2^N x 2^N 切成相等的 2^(N-1) x 2^(N-1) 四塊，
    接下來的序列依序為左上、右上、左下、右下的編碼；
  * 若它是 10 則表示這整塊是黑色；
  * 若它是 11 則表示這整塊是白色。

例如下面的圖案:

■■■□
■■□■
□□■■
□□■■

它可以由不只一個序列描述，像是: (見右圖分割)
                                                        ■■■□
001010101001011111011010101010，長度為30，或是          ■■□■
                                                        □□■■
0100101111101110，長度是16，也是這個圖案的最短長度。    □□■■


對一個正整數 N，定義 D_N 是以下描述的 2^N x 2^N 圖案：

* 座標 x=0, y=0 代表左下角的點；
* 對某點 (x,y) 若 (x-2^(N-1))^2 + (y-2^(N-1))^2 ≦ 2^(2N-2) 則該點是黑色；
  否則該點是白色。

求出 D_24 的最短長度。

--
既然這才是本週的題目就一起貼吧

是說我和 utomaya 在上一題的推文中討論這一題還討論得頗開心 XDrz

--
'Oh, Harry, dont't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
                      ---'Harry Potter and the order of the phoenix', P513

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.28.92
推 puzzlez:XDDD 感謝翻譯  雖然完全無法 follow ..........囧rz
推 cutemens:最短是 9 吧
推 utomaya:是9位數吧
推 cutemens:是 2...全黑或全白
→ LPH66:它要求的是 D_24 這個圖案喔  不是任意 2^24 x 2^24 圖案
→ utomaya:全黑或全白? 題目要是那麼簡單 就不用玩了
→ utomaya:不過那些西歐玩家真是太厲害了 我才剛看懂題目 就一堆人已
→ utomaya:經解出來了 而且竟然有人十幾分鐘就解出來了
→ utomaya:我都還沒看懂題目咧@@ 果然一堆怪物級的人
推 cutemens:所以重點是D_24到底長什麼樣子?
→ cutemens:有圖就有長度了
→ LPH66:題目中已經給描述啦  把 N 代入 24 就是了
推 isnoneval:這個東西可以把它想像成一個馬賽克與解析度的問題 XD
推 utomaya:仔細想想 不太對 全黑或全白只要2bit吧
→ utomaya:就算題目改成任意圖形 答案也應該是2而不是9
→ LPH66:所以他在四樓"更正"啦
→ utomaya:我漏看4樓 抱歉