PTT遊戲區 / puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)

[中譯] PuzzleUp 2009 (10) Coins

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者 (烏托馬雅)時間16年前 (2009/09/23 21:48), 編輯推噓43(43推 0噓 25→)
留言68則, 13人參與, 最新討論串1/1
首頁：http://www.puzzleup.com/2009/?home 時限：2009/09/17（四）19:00～09/22（二）18:59 答案可上傳５次，但每改１次扣２０分（基本分為１００分） 在比賽期間內可隨時回答，但只有在時限內回答者有額外加分 ◆Coins 某個國家中，只要最多2枚硬幣，就可以表達出1至50元的數值(1和50皆包含在內) 在這個國家中，所有種類的硬幣幣值，其總和的最小可能值為何？ 假設題目要求的是可以表達1~8元的數值 硬幣最小總和為8元，分別是1元, 3元, 和4元 1元 = 1個1元硬幣 2元 = 2個1元硬幣 3元 = 1個3元硬幣 4元 = 1個4元硬幣 5元 = 1個1元硬幣 + 1個4元硬幣 6元 = 2個3元硬幣 7元 = 1個3元硬幣 + 1個4元硬幣 8元 = 2個4元硬幣 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 219.70.180.112 ※ 編輯: utomaya 來自: 219.70.180.112 (09/23 22:21)
推
09/24 09:51, , 1F
1.3.9.27?
09/24 09:51, 1F
推
09/24 10:02, , 2F
樓上在說答案？0.0" 不過那不可能是正解 因為最多是36元
09/24 10:02, 2F
推
09/24 10:09, , 3F
哦 不對 最多是 54元......湊不出50....
09/24 10:09, 3F
推
09/24 10:32, , 4F
3的平方數列, 5塊就要超過2枚了...
09/24 10:32, 4F
推
09/24 10:46, , 5F
聯想到「所有的偶數都是兩質數的和」的「猜想」。
09/24 10:46, 5F
推
09/24 10:46, , 6F
反正可以肯定答案小於200...(廢話)...( ￣ c￣)y▂ξ
09/24 10:46, 6F
推
09/24 10:47, , 7F
turing的猜想，可惜奇數沒有照顧到:-(如果是三枚就好了
09/24 10:47, 7F
推
09/24 10:50, , 8F
啊，突然想到一件事@@" 來驗算看看...
09/24 10:50, 8F
推
09/24 10:53, , 9F
這不是「turing的猜想」，這是數論界急於證明的事情。
09/24 10:53, 9F
→
09/24 10:54, , 10F
在數學界尚未證明及未找到反證前都稱之為「猜想」。
09/24 10:54, 10F
推
09/24 10:55, , 11F
我是指你說的猜想啦=.=" 不過真的讓我靈光一閃....
09/24 10:55, 11F
→
09/24 10:57, , 12F
費馬最後的定理在Andrew Wiles證明之前其實應稱為「猜想」
09/24 10:57, 12F
推
09/24 10:59, , 13F
可惜...用「50之前的質數」還是太多了....
09/24 10:59, 13F
→
09/24 16:01, , 14F
我可以說直覺猜的答案嗎?感覺這寫個程式就能解出來?!
09/24 16:01, 14F
推
09/24 16:02, , 15F
還是不要吧...因為我靠直覺之後...後來的答案都比它大@@"
09/24 16:02, 15F
推
09/24 16:03, , 16F
所以搞不好那個直覺...真的是對的@@"...有那麼簡單嗎？
09/24 16:03, 16F
推
09/24 16:55, , 17F
----
09/24 16:55, 17F
不好意思，為了競賽的樂趣，請不要寫出答案，不管你的答案是錯或是對 幫你mark掉，請不要介意
推
09/24 18:33, , 18F
在小一點
09/24 18:33, 18F
※ 編輯: utomaya 來自: 219.70.180.112 (09/24 18:53)
→
09/24 19:48, , 19F
我提供一個想法，假設有n種幣值的硬幣
09/24 19:48, 19F
→
09/24 19:50, , 20F
那麼 一個硬幣的值有n種，2個硬幣的值最多有n^2種
09/24 19:50, 20F
→
09/24 19:51, , 21F
假設他們都剛好不重覆，那麼最多可形成n+n^2個值
09/24 19:51, 21F
→
09/24 19:53, , 22F
n+n^2 ≧50, n的最小值為7，小於7種幣值的，根本不用考慮
09/24 19:53, 22F
推
09/24 20:29, , 23F
還要再除二，因為可以交換
09/24 20:29, 23F
→
09/24 21:02, , 24F
喔 對喔! 那應該是n+n^2/2 ≧ 50, n的最小值是9
09/24 21:02, 24F
→
09/24 21:04, , 25F
寫錯...是n的最小值是10才對 10+10^2/2=60≧50
09/24 21:04, 25F
推
09/24 21:37, , 26F
C(n,2) + n + n ≧ 50
09/24 21:37, 26F
→
09/24 21:37, , 27F
兩枚不重覆、兩枚相同、只有一枚 => n≧9 應該這樣?!
09/24 21:37, 27F
推
09/24 23:17, , 28F
9個點一共只能連45條線，所以n不會等於9，至少是10....
09/24 23:17, 28F
→
09/25 00:04, , 29F
P大寫得才是對的 我剛才也發現自己少考慮了一種
09/25 00:04, 29F
→
09/25 00:06, , 30F
所以應該是(n^2+3n)/2 ≧ 50 n最小是9
09/25 00:06, 30F
推
09/25 01:26, , 31F
不過 n=9 時一共只有54種拿法 要選到不重覆有點難...
09/25 01:26, 31F
推
09/25 14:14, , 32F
嗯Poggle說的沒錯，如果有N種幣值，則3種組合方式為：
09/25 14:14, 32F
推
09/25 14:15, , 33F
1.只付一枚：N種 2.付兩枚相同幣值：N種 3.付兩枚不同幣
09/25 14:15, 33F
推
09/25 14:18, , 34F
N(N+1)/2種 所以一共有N+N+N(N+1)/2 種=N(2+(N+1)/2)
09/25 14:18, 34F
推
09/25 14:20, , 35F
當N=8時，共有8(2+4.5)=52 就已經超過50了....
09/25 14:20, 35F
推
09/25 14:26, , 36F
=.= 我打錯公式了 是 N(N-1)/2......
09/25 14:26, 36F
推
09/25 14:27, , 37F
N(2+(N-1)/2)種 所以N=9時, 9(2+4)=54...是9沒錯...
09/25 14:27, 37F
推
09/25 14:30, , 38F
我猜答案不會超過15種吧....
09/25 14:30, 38F
推
09/25 16:24, , 39F
題目問的是總和最少，而不是數量最少
09/25 16:24, 39F
推
09/25 17:25, , 40F
15種的最小組合是120 離 150 很接近 猜15種左右很合理
09/25 17:25, 40F
推
09/25 21:52, , 41F
其實量多不一定是不好 (如果能讓其他硬幣運用更有效率的話)
09/25 21:52, 41F
→
09/25 21:52, , 42F
也許數列上你捨棄了某個數，會讓之後一個更大的數產生需求
09/25 21:52, 42F
→
09/25 21:52, , 43F
而一個25可是輸給三個8的，盡可能減少大數才是正途 :)
09/25 21:52, 43F
推
09/25 22:08, , 44F
最簡單的方法就已經不超過150了，15種的最小答案是120...
09/25 22:08, 44F
推
09/25 22:08, , 45F
就算想取超過15種也很難吧...難道你們目前的答案有超過嗎
09/25 22:08, 45F
→
09/25 22:12, , 46F
有耶 我超過120了
09/25 22:12, 46F
→
09/25 22:13, , 47F
你有驗算嗎? 最多2枚硬幣可以組成1到50 一一驗算之
09/25 22:13, 47F
推
09/25 22:14, , 48F
=.=" 超過120很正常啊...我是說難道你們都超過15種？
09/25 22:14, 48F
推
09/25 22:15, , 49F
120基本上一定會超過的吧 那是取1~15的總和...
09/25 22:15, 49F
→
09/25 22:15, , 50F
沒超過15種
09/25 22:15, 50F
推
09/25 22:16, , 51F
取15種最小的方式是取1~15（當然這不可能是答案）總和120
09/25 22:16, 51F
推
09/25 22:17, , 52F
所以你取15種的話 基本上總和一定會超過120
09/25 22:17, 52F
推
09/25 22:19, , 53F
已知最笨的方法 其總和為 145 所以總和絕不能超過它
09/25 22:19, 53F
→
09/25 22:22, , 54F
我有一個直覺的方法 14種 但總和是193...超大的值
09/25 22:22, 54F
推
09/25 22:25, , 55F
咦？我以為145的答案還滿直覺的耶...真的很難想另一種
09/25 22:25, 55F
推
09/26 00:38, , 56F
我寫了一個程式，目前已經跑了半天了，還跑不出來。
09/26 00:38, 56F
→
09/26 00:40, , 57F
不過我也想到了p大的145的解答。
09/26 00:40, 57F
→
09/26 00:42, , 58F
經過一番推導和stimim的提醒找到了比tp大「少一點」的答案
09/26 00:42, 58F
→
09/26 00:43, , 59F
趕在第一天的期限到之前上傳答案...
09/26 00:43, 59F
推
09/26 04:36, , 60F
剛寫了個程式跑完了，找出比之前上傳還少2的答案…orz
09/26 04:36, 60F
推
09/26 06:59, , 61F
這題的難度還真高啊.....:-(
09/26 06:59, 61F
→
09/26 10:06, , 62F
我忽然發覺這題的意義了 這題其實是第2題運水問題的延伸
09/26 10:06, 62F
→
09/26 11:31, , 63F
一樣有2個中繼點 要把水運到終點(50)
09/26 11:31, 63F
推
09/26 21:24, , 64F
好難@@
09/26 21:24, 64F
推
09/26 22:17, , 65F
我想到----
09/26 22:17, 65F
→
09/26 22:19, , 66F
再----
09/26 22:19, 66F
sorry，幫你把答案mark掉
→
09/26 22:31, , 67F
大家都好厲害唷 我都沒想法Q.Q
09/26 22:31, 67F
※ 編輯: utomaya 來自: 219.70.180.112 (09/26 23:29)
推
09/27 16:01, , 68F
我大概知道"少一點"是少哪裡了
09/27 16:01, 68F
‣ 更多 utomaya 的文章
文章代碼(AID): #1AkYSWdB (puzzle)
puzzle 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
15
17
[實況] 超負荷
[ LoL ]
NPttnoob
7小時前, 12/31
更多 即時熱門文章 >>
‣ 更多 utomaya 的文章
文章代碼(AID): #1AkYSWdB (puzzle)