Puzzleup 2012 (19) Palindromic Number - 拼圖

我先自首，
1. 在這個版學到program-up這個字
2. 這題我分析了一下沒突破口後就先program-up了
3. 看到j大的文，先是在心裡按了個讚著實感嘆了一下，然後噗哧

====================== 以上廢話，以下嘗試用分析的方式解這題 =================

令答案所需要的最大回文數為N

1. N < 9 * 83 * 741 * 6520 = 3608996040 (最多為十位數)
上面選定開頭的9876後，小的會被後面的百位數拉高比例較多所以9是個位
剩下的543210優先把大的放在最重要的位數，依第幾位數開頭小的優先
2. 以下假設N為10位數
(1) N最前後兩端的位數可能為1, 2, 3 (注意回文數的最高位數 = 最低位數)
a. 若四個結尾有偶數 => N的開頭結尾只能是2
b. 若四個結尾有0 => 不可能是十位回文數 (個位數為零)
c. 若四個結尾有5 => 不可能是十位回文數 (搭偶數如b, 不搭偶數前後會是5)
d. 若結尾是1,3,7,9 => 不可能是十位回文數 (開頭結尾會是9)
所以N為十位數，N的前後兩端位數一定要是2
(2) 十位回文數一定是11的倍數，
且這一定是從百位數來(1位的顯然不可能，偶位數的11倍數是回文一定重複)
百位數中，每個位數不重複、後兩位沒用到9，開頭是3~9，結尾不是0或5有:
308, 341, 352, 374
407, 418, 451, 462, 473
506, 517, 528, 561, 572, 583
627, 638 ,671 ,682
704, 726, 748, 781
803, 814, 836, 847
902, 913, 924, 946, 957, 968
(3) 海巡開頭可能的四個數字，檢查[個位數;{結尾}](結尾0,5都拿掉)
a. {9,8,7,6} => min = 6 * 72 * 814 * 9035 = 3177139680 出局

b. {9,8,7,5} => min = 5 * 72 * 814 * 9036 = 2647909440
結尾{1,2,3,4,6}取三依乘積分類:
2: {1,2,6}, {1,3,4}, {3,4,6}
4: {1,4,6}, {2,3,4} --> 配個位數"8"
6: {1,2,3}, {2,3,6} --> 配個位數"7"
8: {1,2,4}, {1,3,6}, {2,4,6} --> 配個位數"9"
(a) 個位數為8，其他配{1,4,6}結尾，依三位數可能選擇做分類(用過數字排除)
[8,XY,924,XZZY], X:{5,7}, Y:{1,6}, Z:{0,3}
[8,XY,704,XZZY], X:{5,9}, Y:{1,6}, Z:{2,3}
[8,XY,726,XZZY], X:{5,9}, Y:{1,4}, Z:{0,3}
[8,XY,506,XZZY], X:{7,9}, Y:{1,4}, Z:{2,3}
(b) 個位數為8，其他配{2,3,4}結尾
[8,XY,902,XZZY], X:{5,7}, Y:{3,4}, Z:{1,6}
[8,XY,913,XZZY], X:{5,7}, Y:{2,4}, Z:{0,6}
[8,XY,704,XZZY], X:{5,9}, Y:{2,3}, Z:{1,6}
(c) 個位數為7，其他配{1,2,3}結尾 (略)
(d) {2,3,6}
(e) 9 {1,2,4}
(f) {1,3,6}
(g) {2,4,6}
由以上(a)~(g)乘開可知，沒有回文數

c. {9,8,7,4} => max = 9 * 83 * 751 * 4620 = 2591806140
結尾{1,2,3,6}取三依乘積分類:
2: {1,2,6}
6: {1,2,3}, {2,3,6} --> 配個位數"7"
8: {1,3,6} --> 配個位數"9"或"4"

d. {9,8,7,3} => max = 9 * 84 * 751 * 3620 = 2055276720
結尾{1,2,4,6}取三依乘積分類:
2: {1,2,6}
4: {1,4,6} --> 配個位數"8"或"3"(3太小)
8: {1,2,4}, {2,4,6} --> 配個位數"9"

e. {9,8,7,2} => max = 9 * 84 * 751 * 2630 = 1493198280 出局

f. {9,8,6,5} => max = 9 * 83 * 641 * 5720 = 2738890440
結尾{1,2,3,4,7}取三依乘積分類:
1: {1,3,7}
2: {1,3,4}, {2,3,7} --> 配個位數"6"
4: {1,2,7}, {2,3,4} --> 配個位數"8"
6: {1,2,3}, {2,4,7}
8: {1,2,4}, {1,4,7}, {3,4,7} --> 配個位數"9"

g. {9,8,6,4} => max = 9 * 83 * 651 * 4720 = 2295321840
結尾{1,2,3,7}取三依乘積分類:
1: {1,3,7}
2: {2,3,7} --> 配個位數"6"
4: {1,2,7} --> 配個位數"8"
6: {1,2,3}

h. {9,8,6,3} => max = 9 * 84 * 651 * 3720 = 1830820320 出局

i. {9,8,5,4} => max = 9 * 83 * 561 * 4720 = 1977996240 出局

j. {9,7,6,5} => max = 9 * 73 * 641 * 5820 = 2451017340
結尾{1,2,3,4,8}取三依乘積分類:
2: {1,3,4}, {1,4,8} --> 配個位數"6"
4: {1,3,8}, {2,3,4}, {2,4,8}
6: {1,2,3}, {1,2,8}, {3,4,8} --> 配個位數"7"
8: {1,2,4}, {2,3,8} --> 配個位數"9"

k. {9,7,6,4} => max = 9 * 73 * 651 * 4820 = 2061547740
結尾{1,2,3,8}取三依乘積分類:
4: {1,3,8}
6: {1,2,3}, {1,2,8} --> 配個位數"7"
8: {2,3,8} --> 配個位數"9"或"4"(4太小)

l. {9,7,6,3} => max = 9 * 74 * 651 * 3820 = 1656222120 出局

m. {9,7,5,4} => max = 9 * 73 * 561 * 4820 = 1776541140 出局

以上c, d, f, g, j, k仿照b的作法應該可以用紙筆在一兩天內爆完...
粗估大約需要乘開8 * 4 * 33 ~ 1000個組合在其中尋找最大的回文數

※ 引述《jurian0101 (Hysterisis)》之銘言：
: ※ 引述《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
: 不用它的優雅方式難道沒有嗎

--