作者LPH66 ((short)(-15074))
看板puzzle
標題[中譯] PuzzleUp 2009 (5) Pattern
時間Wed Aug 19 20:31:53 2009
首頁：
http://www.puzzleup.com/2009/?home
時限：2009/08/20（四）19:00～08/26（三）18:59
答案可上傳５次，但每改１次扣２０分（基本分為１００分）
在比賽期間內可隨時回答，但只有在時限內回答者有額外加分
◆Pattern
在一個５Ｘ５的格子裡任意塗黑三格共有幾種塗法？
注意：若一個塗法可以由另一個塗法經旋轉(且不鏡射)而得到，
則兩者就認為是相同的塗法。
--
'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.30.84
1F：→ LPH66:就不等帕索大了 自己先貼 XD (其實是解的差不多了...(逃 08/19 20:32
※ 編輯: LPH66 來自: 140.112.30.84 (08/19 20:33)
2F：推 northkk:如果題目是 4x4 或 6x6 的格子會比較簡單... 08/19 20:57
3F：→ northkk:題目長得就是一付有陷阱的臉... 08/19 20:58
4F：推 xphacker:只用乘跟除的答案會對嗎 08/19 21:09
5F：推 northkk:不曉得耶, 我在想有沒有解法是可以用到開根號的....:P 08/19 21:17
6F：推 werul:5*5的關鍵就是中間這格 08/19 21:27
7F：推 northkk:沒錯, 陷阱臉.... 08/19 21:30
8F：推 ars1an:同意，掌握關鍵後剩下的就是排列組合啦 08/19 23:34
9F：→ ars1an:怎麼用根號解我也想不到… :P 08/19 23:35
10F：推 puzzlez:算完之後，我得到一個驚人的結果…… 08/20 08:25
11F：推 xphacker:什麼!! Σ(⊙▽⊙"a 08/20 08:39
12F：→ xphacker:咦!閒聊區不見了 08/20 08:42
13F：推 FACE90006:哇嗚~這樣就不能玩帕索了ＱＱ。。。 08/20 20:29
14F：推 JimAbbott:他故意的 08/20 20:40
15F：推 FACE90006:帕索大真殘忍...唯一的樂趣也被硬生生地剝奪ＱＱ。。。 08/20 20:49
16F：推 xphacker:為了這題 我翻出了塵封以久的五子棋來排 08/20 20:50
17F：推 werul:要牌很久喔 08/20 21:01
18F：推 puzzlez:只排三階就很快...而且會發現一件奇怪的事... 08/20 21:36
19F：推 xphacker:也是只排3 冥冥中有個巧合....難不成... 08/20 21:42
20F：推 puzzlez:只要確定是21或22 我就能確定5階的答案了... 08/20 21:43
21F：推 puzzlez:嗯 是22種 我能確定5階的答案了！ 08/20 21:55
22F：推 puzzlez:22種是3階的答案...別誤會了....... 08/20 21:56
23F：推 northkk:我可以確定1階的答案是0種.... 08/20 22:03
24F：→ northkk:提供大家做參考.. 08/20 22:03
25F：推 xphacker:2階是1種 肯定! 08/20 22:10
26F：推 puzzlez:我經過2天不眠不休，再用微積分，終於算出4階有140種... 08/20 22:13
27F：推 puzzlez:解數列 0, 1, 22, 140, ? 天啊...這個提示真大..... 08/20 22:15
28F：推 xphacker:不眠不休 0口0"" 08/20 22:23
29F：推 turing:這不是應該用5x5格子中塗1個格子有幾種、塗兩個格子有幾種 08/20 22:34
30F：→ turing:進而算出塗三個格子有幾種？ 08/20 22:35
31F：推 puzzlez:樓上一語驚醒夢中人！我本來還想用線性迴歸法去分析說.... 08/20 23:14
32F：推 werul:有尾數@@ 08/21 01:12
33F：推 JimAbbott:帕索不眠不休，那來的夢中人 = = 08/21 01:41
34F：推 puzzlez:啊我就不能做白日夢哦-.- 真愛計較... 08/21 06:40
35F：推 puzzlez:TO werul: 什麼尾數來著？你之前是算 XXX0 嗎？ 08/21 06:42
36F：推 werul:我算的是有尾數 而且沒超過1000@@ 尾數就是不是5或0的數字 08/21 16:28
37F：推 JimAbbott:愛做白日夢的帕索大 08/21 17:28
38F：推 puzzlez:我是故意打四位數說 被你破梗XDDDD 我的尾數也不是5或0... 08/21 18:24
39F：推 utomaya:答案個位數是8嗎? 想確認一下 講個位數應該不算洩露答案! 08/21 20:51
40F：推 utomaya:寫了2個小時的程式 讓程式去跑出答案 哈哈! 我真懶惰 08/21 20:53
41F：→ utomaya:但不知道答案對不對? 但4X4的話 我的程式跑出來是140種 08/21 20:54
42F：→ utomaya:6x6跑來出是1785種 08/21 21:34
43F：推 werul:我算出來尾數是3.. 08/21 23:18
44F：推 utomaya:應該是奇數格才要考慮對稱情形 如3X3 5X5 7X7 08/21 23:22
45F：推 werul:我算出來是5X3...Q口Q 08/21 23:24
46F：→ utomaya:偶數格沒有對稱情形 直接除以四 ex: C(2^2,3)/4 =1 08/21 23:24
47F：→ utomaya:c(4^2,3)/4 = 140 C(6^2,3)/4 = 1785 08/21 23:25
48F：→ utomaya:除以4的原因是因為可以旋轉4個角度 都視為一種 08/21 23:26
49F：推 werul:對 08/21 23:27
50F：→ utomaya:奇數格則會圖形對稱的情況 需另外考慮 不能直接除以4 08/21 23:28
51F：推 werul:直接除答案是575..不過當然不對XD 08/21 23:29
52F：推 werul:想知道程式怎麼寫的 08/21 23:32
53F：推 FACE90006:我也想知道QQ...我最近好像變笨了... 08/22 10:32
54F：推 utomaya:就是把三格數字化 例如(1,1),(4,1),(5,5)記為114155 08/23 21:59
55F：→ utomaya:然後開始排列，把每一個三格翻轉4次得到的數字丟到陣列去 08/23 22:00
56F：→ utomaya:然後下一個排列的三格，看看數字有沒有已經在陣列裡? 08/23 22:01
57F：→ utomaya:有的話 不予計數，免得得到同樣的圖形而重覆計數了! 08/23 22:03
58F：→ utomaya:我的程式沒有很長 大概200行左右 用c++寫的 08/23 22:13
59F：推 turing:借用utomaya的想法，如果我以中間(3,3)的格子當作原點。 08/24 22:05
60F：→ turing:向右為實數1,2;向左為-1,-2;向上為虛數i,2i向下為-i,-2i 08/24 22:06
61F：→ turing:則(1,1)以數字表示為-2+2i;(4,1)=1+2i;(5,5)=2-2i 08/24 22:07
62F：→ turing:逆時針旋轉90度，相當於數字乘上i。 08/24 22:09
63F：→ turing:例如 (1,1)=-2+2i 乘上i = -2-2i = (1,5) 08/24 22:10
64F：→ turing:經過這樣轉換，是否有什麼定理可以用原題的解題上？ 08/24 22:12
65F：推 puzzlez:還滿有創意，但至今我還想不出有什麼應用解題的方式.... 08/25 10:06
66F：推 stimim:在旋轉的時候把中間的格子當做(0,0)， 08/25 11:20
67F：→ stimim:在做運算的時候把左上角的格子當做(0,0)， 08/25 11:20
68F：→ stimim:如果可以，就代表重覆，否則計數器加一 08/25 11:21
69F：→ stimim:唔...連推失敗 08/25 11:21
70F：→ stimim:在旋轉的時候把中間的格子當做(0,0)， 08/25 11:21
71F：→ stimim:在做運算的時候把左上角的格子當做(0,0)， 08/25 11:21
72F：→ stimim:整個盤面有25個格子，一個integer佔32個bit 08/25 11:22
73F：→ stimim:所以用右邊的25個bit來代表那些格子， 08/25 11:22
74F：→ stimim:(x,y)用第(x*5+y)個bit來表示，如果有放東西 08/25 11:22
75F：→ stimim:就是1，否則是0， 08/25 11:22
76F：→ stimim:所以每一個盤面會有三個bit不為零，可用一個整數代表 08/25 11:22
77F：→ stimim:，假設為k，對於每一個k，檢查是否可以轉換成一個更小的k' 08/25 11:22
78F：→ stimim:如果可以，就代表重覆，否則計數器加一 08/25 11:22
79F：→ stimim:這樣枚舉完所有可能之後就可以算出有幾種方法 08/25 11:23
80F：→ stimim:這樣寫的話大概50行就夠了 08/25 11:24
81F：推 puzzlez:嗯，看懂了...好像真的不難耶...... 08/25 14:38
82F：推 puzzlez:這麼一來就不用把查過的位置，記錄下來了..... 08/25 14:39
83F：推 stimim:找到奇數項的公式了，可是不知道為什麼長這樣 >.< 08/25 21:05
84F：推 puzzlez:哇，我知道為什麼耶～突然覺得自己好優秀～XDDDDD 08/25 21:35
85F：推 stimim:哇!！！我懂了，原來我忘了某一項～XDD 08/25 21:40
86F：推 puzzlez:結果我只優秀了35分鐘....=.=" 08/26 06:51
87F：推 yhong:我3X3的只排出19個 = = 08/27 14:00
88F：推 yhong:對不起我錯了 <(_ _)> 重算後是21，不知道少哪一個 ^^" 08/27 14:05