作者buffalobill (水牛比爾)
看板puzzle
標題[問題] 組裝三角
時間Mon Aug 31 09:02:34 2020
puzzleUp風味題 Vol.5
【組裝三角】
給予50個線段，長度分別為1~50。
組成任意數量的直角三角形。
問這些直角三角形的最大總合面積為？
線段不能裁接凹折
三角形之間不能共線
若題目給1~20的線段，則答案為162
(3,4,5)(8,15,17)(12,16,20)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.148.94 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/puzzle/M.1598835756.A.5D3.html
1F：→ buffalobill: 長度1跟2是不可能組成直角三角形的，無視就好:) 08/31 09:03
※ 編輯: buffalobill (60.251.148.94 臺灣), 08/31/2020 09:43:14
2F：推 arthurduh1: 程式列出畢氏三元數，再用紙筆初步湊出 1932 08/31 09:45
3F：→ arthurduh1: 如果不考慮畢氏三元數可能出現的潛在關係 08/31 09:47
4F：→ arthurduh1: programUp 起來是個 weighted independent set 問題 08/31 09:47
6F：→ buffalobill: 1932還差一點點哦 08/31 14:09
7F：推 arthurduh1: 上面那張圖多算了 (20, 48, 52)，不過跑起來結果一樣 08/31 14:44
8F：→ arthurduh1: 因為沒有用到那組 08/31 14:45
9F：→ arthurduh1: 是有沒考慮到的組裝方式嗎(思 08/31 14:45
10F：推 arthurduh1: 找到問題了，1944 08/31 15:01
11F：→ buffalobill: 1944正解 08/31 15:05
12F：推 arthurduh1: 新的圖要手算感覺麻煩許多 08/31 15:13
13F：推 LPH66: 我找到 1944, 還不確定是不是最大 08/31 15:13
14F：→ LPH66: hmmmm 08/31 15:13
15F：推 LPH66: 啊, 找到 1932 了...還在想這種 local max 應該要出現的 08/31 15:35
16F：→ LPH66: 我是整理出 (9,12,15) (12,16,20) (15,20,25) 最多取其一 08/31 15:36
17F：→ LPH66: 從這裡去找, 1944 是選 (15,20,25) 得到的最大值 08/31 15:36
18F：→ LPH66: 1932 則是都不選的 local max 08/31 15:36
19F：→ LPH66: 主要是 (30,40,50) 的位置太尷尬, 取和不取的條件不夠多 08/31 15:40
20F：→ LPH66: 又被 (14,48,50) (18,24,30) (24,32,40) 兩邊夾 08/31 15:41
21F：→ LPH66: 從那邊出發的分支完全動不到上五樓提到的那一團 08/31 15:42
22F：推 arthurduh1: 我是用 (m^2-n^2, 2mn, m^2+n^2) 找畢氏三元數 08/31 15:43
23F：→ arthurduh1: 沒注意到這只保證可以找出互質的，所以才算出 1932 XD 08/31 15:43
24F：→ arthurduh1: 那張圖裡列的是用這個公式可以找出的那些 08/31 15:44
25F：推 LPH66: 哦, 你是找所有 (m, n) 而不是用基本三元數乘 k 倍... 08/31 15:46
26F：→ arthurduh1: 對XD 08/31 15:46
27F：→ LPH66: 所以就正好漏掉了包含 (15,20,25) 的幾個這樣嗎 XD 08/31 15:47
28F：推 arthurduh1: 有包含 (12,16,20)，不過找最大值的時候不會取到 08/31 15:53