Re: [中譯] Puzzleup 2012 (19) Palindromic Number

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者jurian0101 (Hysterisis)時間13年前 (2012/11/30 21:52)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/3 (看更多)

※ 引述《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 不用它的優雅方式難道沒有嗎 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.213.88 ※ 編輯: jurian0101 來自: 140.112.213.88 (11/30 21:55)