作者LPH66 ((short)(-15074))
看板puzzle
标题[中译] Projecteuler (287) Quadtree
时间Sun Apr 11 09:51:41 2010
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
1F：推 puzzlez:XDDD 感谢翻译 虽然完全无法 follow ..........囧rz 04/11 09:59
2F：推 cutemens:最短是 9 吧 04/11 10:20
3F：推 utomaya:是9位数吧 04/11 10:24
4F：推 cutemens:是 2...全黑或全白 04/11 10:26
5F：→ LPH66:它要求的是 D_24 这个图案喔 不是任意 2^24 x 2^24 图案 04/11 10:29
6F：→ utomaya:全黑或全白? 题目要是那麽简单 就不用玩了 04/11 10:33
7F：→ utomaya:不过那些西欧玩家真是太厉害了 我才刚看懂题目 就一堆人已 04/11 10:34
8F：→ utomaya:经解出来了 而且竟然有人十几分钟就解出来了 04/11 10:35
9F：→ utomaya:我都还没看懂题目咧@@ 果然一堆怪物级的人 04/11 10:36
10F：推 cutemens:所以重点是D_24到底长什麽样子? 04/11 11:18
11F：→ cutemens:有图就有长度了 04/11 11:19
12F：→ LPH66:题目中已经给描述啦 把 N 代入 24 就是了 04/11 11:30
13F：推 isnoneval:这个东西可以把它想像成一个马赛克与解析度的问题 XD 04/11 16:28
14F：推 utomaya:仔细想想 不太对 全黑或全白只要2bit吧 04/12 13:54
15F：→ utomaya:就算题目改成任意图形 答案也应该是2而不是9 04/12 16:59
16F：→ LPH66:所以他在四楼"更正"啦 04/12 21:06
17F：→ utomaya:我漏看4楼 抱歉 04/12 21:28