Puzzleup 2012 (19) Palindromic Number - 拼圖

※ 引述《LPH66 (杇瑣)》之銘言：
: 題目網址: http://www.puzzleup.com/2012/?home
: http://www.puzzleup.com/2012/puzzle/?260
: 答題時限: 11月29日７ＰＭ－比賽結束（約１２月１２日）
: 加分時限: 11月29日７ＰＭ－12月４日６：５９ＰＭ
: 答對可得基本分１００分。答案可上傳５次，每改１次答案從基本分扣２０分。
: 另有兩種加分： １. 加分時限內答對。例：第Ｎ天答對，可加（６－Ｎ）分。
: ２. 題目越困難，加分越多。例：這題有ｎ％的人答錯，答對者加ｎ分。
: ◆Palindromic Number
: Using all 10 digits (0-9) only once, one 1-digit, one 2-digit, one 3-digit,
: and one 4-digit numbers are formed. When these four numbers are multiplied
: the result is a palindromic number. What can be the maximum value for this
: palindromic number?
: 使用 0 到 9 十個數字各一次，構成一位數、兩位數、三位數及四位數各一個。
: 當這四個數相乘會得到一個迴文數(譯註)。問這個迴文數最大多少？
: 譯註：迴文數是指正讀反讀都相同的數，如 12321。

落落長的一行解 <<<<這叫哪門子一行

f = (1000 #1 + 100 #2 + 10 #3 + #4) (100 #5 +10 #6 + #7) (10 #8 + #9) #10 &;
Max[
f@@@Select[
Cases[Permutations[Range[0, 9]],
{Except[0], _, _, Except[0 | 5],
Except[0], _, Except[0 | 5],
Except[0], Except[0 | 5],
Except[0 | 5]}],
Reverse[IntegerDigits[f @@ #]] == IntegerDigits[f @@ #] &
]]

好我承認說不上是一行解決 = = 總之起碼有個辦法(雖然稱為暴力解)可確知答案了

再回頭來揣摩一下，能不能別跑10!次判別多麼醜陋的方法啊。

- - - - 洞洞手洞洞腦的分隔線 - - - -

乘積最大是十位數9xxx*8xx*7x*6 = 3 xxx xxx xxx，

我決定起初要很樂觀的假設結果的乘積是十位數，絕不是因為偷看答案
而是因為十位數又是回文數，它一定是11的倍數多了這個線索。

排列出的 一位與兩位不可能是11倍數，因此 四位數 或 三位數是11的倍數。
此線索保留

10位數的乘積以1,2,3開頭，但1,3不合，因為{1,3,5,7,9}挑四個在個位，不可能變出1或3
故只有2可能

滿足 2 xxx xxx xxx 開頭數字 = 9*8*7*5 或 9*8*6*5

因此9和8絕對會被開頭用掉

滿足 x xxx xxx xx2 結尾數字 = 1*2*3*7 或 1*3*4*6 或 2*3*6*7(同時用掉6,7不合)

所以

9 x y 1 9 x y 1
8 z 2 8 z 3
5 3 5 4
x 7 剩 0 4 6 x 6 剩 0 2 7
__________ ____________

(9,8,5) (1,2,3) 可替換 (9,8,5) (1,3,4) 可替換

看似有 3!*3!*3! *2 = 432 種情況，但其實更少，因為有11倍數這條件可以用

9**1 以左式為例 ,
8*2
53 若8** 11倍數，是803
7 9** .. 902
5** .. 561

xyyz*803*xz*7 x \in {9,5} && y \in {4,6} && z \in{1,2} 八種

xyyz*902*xz*7 x \in {8,5} && y \in {4,6} && z \in{1,3} 八種

xyyz*561*xz*7 x \in {9,8} && y \in {4,6} && z \in{2,3} 八種

若三位數非11被數，則四位數必須是

11|abcd -> (a-d) ± (b-c) = 0 或 11

因b,c \in {0,4,6} -> b-c \in ±{2,4,6}

總之四位數只可能是 9042, 8041,8063, 5401, 5203

9042*x6y*xy*7 四種
8041*x6y*xy*7 ..
8063*x3y*xy*7 ..
5401*x6y*xy*7 ..
5023*x4y*xy*7 ..

- - - -

9**1 剩 0 2 7
8*3
54
6

xzzy*803*xy*6 八種
xzzy*924*xy*6 ..

9724*x0y*xy*6 四種
8701*x2y*xy*6 ..
8723*x0y*xy*6 ..
5203*x7y*xy*6 ..
5027*x7y*xy*6 ..


OAO，削減到8*2+4*5+8*2+4*5 = 72 種情況了


問題是答案不在裡面，所以不做了，掯。

因為首位數是 9*8*7*5 或 9*8*6*5 的假定是錯的，因為這兩個只是

首位數必定是2的情況。5*6*7*8 和 5*6*7*9 都差一點點適當的排列也是個2字頭


結論是答案在5 6 7 9開頭 <-----怎麼可能用這種方法篩出來，一定是

Program-Up

Program-Up

Program-Up

不用它的優雅方式難道沒有嗎

--